Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wrote a method that will return the minimum element in a linked-list that operates in O(1) time. I tested and everything works fine. However, I was wondering if there is anything that I can do to make my code more efficient or cleaner.

public class Node {

    //private Object item;
    Node next;
    Object item;

    // constructor
    public Node(Object item) {
        this.item = item;
        next = null;
    }

}

public class MinElementInStack {

    static Node stack;
    static Node minStack;

    public void push(int data) {

        // push nodes into stack
        Node last = new Node(data);
        last.next = stack;
        stack = last;

        // check if node being pushed is new min
        // if it is then push into minStack
        if(minStack == null) { // for first node 
            Node toBePushed = new Node(data);
            toBePushed.next = minStack;
            minStack = toBePushed;
        } else { // if int to be pushed is less than current min on stack
                // then push it onto the stack, otherwise push the same min value from previous 
            int toBePushedInt = data;
            if(toBePushedInt < (Integer)minStack.item) {
                Node toBePushed = new Node(data);
                toBePushed.next = minStack;
                minStack = toBePushed;
            } else {
                Node toBePushed = new Node((Integer)minStack.item);
                toBePushed.next = minStack;
                minStack = toBePushed;
            }
        }

    }

    public void pop() {
        if (stack != null && minStack != null) {
            stack = stack.next;
            minStack = minStack.next;
        }
    }

    public int min() {

        int min = (int) minStack.item;
        return min;

    }

    public void print(Node node) {
        Node temp = node;
        while (temp != null) {
            System.out.println(temp.item);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {

        MinElementInStack s = new MinElementInStack();

        s.push(5);
        s.push(-28);
        s.push(8);
        s.push(-50);
        s.push(-4);
        s.push(-38);
        s.push(100);

        System.out.println("Original Stack: ");
        s.print(stack);
        System.out.println();
        System.out.println("Min Stack: ");
        s.print(minStack);
        System.out.println();
        System.out.println("Minimum element in current stack: " + s.min());
    }

}
share|improve this question
    
Oops your totally right. I actually didn't know who to make it constant time so hence the O(n). – Stackimus Prime Apr 22 at 5:39
up vote 4 down vote accepted
  1. Since your min() in your implementation returns an int, I would modify the type of Node.item to int.

  2. Since we are dealing with a stack of (primitive) integers, I would rename MinElementInStack to IntStack.

  3. Next, why not rename Node to IntStackNode?

  4. Both the fields in Node can be specified as private final + you could add getters for the two fields.

  5. You could define Node as an inner static class in your actual stack class.

  6. pop() should return the integer datum associated with the popped node.

  7. Both pop() and min() should throw EmptyStackException whenever the stack is empty.

  8. I would add the field size to the stack, and the methods size() and isEmpty() which rely on the field size.

  9. Instead of print(), I would override public String toString().

  10. You are overkilling it in the push, mainly due to the fact that you create the new node more than once, and rename data to toBePushedInt.

Summa summarum

All in all, I had this in mind:

import java.util.EmptyStackException;
import java.util.Scanner;

public class IntStack {

    private static final String STRING_BEGIN = "[";
    private static final String STRING_END   = "]";
    private static final String SEPARATOR    = ", ";

    private static final class IntStackNode {

        private final int datum;
        private final IntStackNode previous;
        private IntStackNode previousMinimum;

        IntStackNode(final int datum, final IntStackNode previous) {
            this.datum = datum;
            this.previous = previous;
        }

        int getDatum() {
            return datum;
        }

        IntStackNode getPreviousNode() {
            return previous;
        }

        IntStackNode getPreviousMinimum() {
            return previousMinimum;
        }

        void setPreviousMinimum(final IntStackNode previousMinimum) {
            this.previousMinimum = previousMinimum;
        }
    }

    private IntStackNode top;
    private IntStackNode minimum;
    private int size;

    public void push(final int datum) {
        IntStackNode newnode = new IntStackNode(datum, top);

        if (isEmpty()) {
            minimum = newnode;
        } else if (minimum.getDatum() > datum) {
            newnode.setPreviousMinimum(minimum);
            minimum = newnode;
        }

        top = newnode;
        ++size;
    }

    public int pop() {
        if (top == null) {
            throw new EmptyStackException();
        }

        final IntStackNode ret = top;

        if (minimum == ret) {
            minimum = ret.getPreviousMinimum();
        }

        top = top.getPreviousNode();
        --size;
        return ret.datum;
    }

    public int min() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return minimum.getDatum();
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0; 
    }

    @Override
    public String toString() {
        IntStackNode node = top;

        if (top == null) {
            return STRING_BEGIN + STRING_END;
        }

        final StringBuilder sb = new StringBuilder(STRING_BEGIN);
        sb.append(top.getDatum());
        node = top.getPreviousNode();

        for (int i = 1; i < size; ++i) {
            sb.append(SEPARATOR).append(node.getDatum());
            node = node.getPreviousNode();
        }

        return sb.append(STRING_END).toString();
    }

    public static void main(final String[] args) {
        final IntStack stack = new IntStack();
        final Scanner scanner = new Scanner(System.in);

        loop:
        while (true) {
            System.out.print("> ");

            final String command = scanner.next().trim().toLowerCase();

            switch (command) {
                case "push":
                    doPush(stack, scanner);
                    break;

                case "pop":
                    doPop(stack);
                    break;

                case "print":
                    System.out.println(stack);
                    break;

                case "min":
                    doMin(stack);
                    break;

                case "quit":
                case "exit":
                    break loop;

                default:
                    System.out.println("Unknown command: \"" + command + "\"");
            }
        }
    }

    private static void doPush(IntStack stack, Scanner scanner) {
        int datum;

        try {
            datum = scanner.nextInt();
        } catch (NumberFormatException ex) {
            System.out.println("ERROR: An integer is required.");
            return;
        }

        stack.push(datum);
    }

    private static void doPop(IntStack stack) {
        try {
            stack.pop();
        } catch (EmptyStackException ex) {
            System.out.println("ERROR: Popping from an empty stack.");
        }
    }

    private static void doMin(IntStack stack) {
        try {
            System.out.println(stack.min());
        } catch (EmptyStackException ex) {
            System.out.println(
                    "ERROR: Asking for minimum element from an empty stack.");
        }
    }
}

Hope that helps.

share|improve this answer
    
Hey thanks for much for your suggestions. It was definitely really useful and thus helped me a lot! – Stackimus Prime Apr 23 at 23:58

I would define a function like this:

private Node addNumberToStack(Node stack, int number){
  Node newNode = new Node(number);
  newNode.next = stack;
  return newNode;
}

And then use the following function

 public void push(int data) {
   stack = addNumberToStack(stack, data);
   if(minStack == null){
     minStack = addNumberToStack(minStack, data); // can avoid it by initializing minStack with some dummy value
   } else{
     minStack = addNumberToStack(minStack, min(data, (Integer)minStack.item));
   }
 }

min just returns the minimum of the two numbers.

Rest of the code looks pretty good to me. Maybe rename stack to userInputStack.

Plus, if its just integer inputs, make Node.item an int

EDIT: Whenever thinking about refactoring code, the easiest way (IMO) to get started is

  1. Figure out whichever parts are being duplicated and then abstract them out into smaller functions. These functions if well named, reduce the effort of reading your code and also, reduce the number of place you need change if you update your logic later.

    The addToStack function is such an utility function which abstracts out the common code, and provides you with an easy way to change the logic for adding new nodes on the stack in the future.

  2. Once, you've refactored out all the common parts, think about names and their relevance in your current context.

    You're making a stack which can also, return the minimum element it has at any point of time. So is MinElementInStack really a good name for the stack itself? MinStack/ IntStack or even MinNumberFinderStack seem better options IMO.

  3. Finally, checkout all the function modifiers and declarations and review them for exactness. String which are same across all instances should be declared static final and so on.

By following these rules you will generally end up with clean code.

share|improve this answer
1  
Wouldn't addNumberToStack be better off private? And then, stack seems like a confusing name for a Node - you could also mention that in your review, and perhaps expand a bit about why this method would be useful; otherwise, good job on your first post! – Mat's Mug Apr 22 at 20:36
1  
Indeed, it should be a private function. Thanks for pointing it out :) Just getting started on this site, hoping to improve as a developer and assist others too. – sudshekhar Apr 23 at 7:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.