Make a new design of Stack with a new function

Question

I am doing some coding exercise, and I am not sure if I have met the requirement. Can someone help me to figure it out?

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

public class Question {
private Node top;
private Node min;

public void push(int data) {
    Node newNode = new Node(data);
    Node newMin = new Node(data);
    if (top == null) {
        this.top = newNode;
        this.min = newMin;
    } else {
        newNode.next = this.top;
        this.top = newNode;
        if (newMin.data < this.min.data) {
            newMin.next = this.min;
            this.min = newMin;
        }
    }
}

public int pop() {
    if (top == null) {
        return -1;
    }
    int tempInt = this.top.data;
    if (this.top.data == this.min.data) {
        this.min = this.min.next;
    }
    this.top = this.top.next;
    return tempInt;
}

public int min() {
    return this.min.data;
}
public String toString(){
    return "Current top is: " + this.top.data + ", current min is: " + this.min();
}

class Node {
    Node next;
    int data;

    public Node(int data) {
        this.data = data;
    }
}

public static void main(String[] args){
    Question tempQue = new Question();
    for(int i = 100; i > 0; i--){
        tempQue.push(i);
        System.out.println(tempQue);
    }
    for(int i = 0 ; i < 99; i++){
        tempQue.pop();
        System.out.println(tempQue);
    }
}
}

I have tested this code but I am not sure if the Operating time meets the requirement \$O(1)\$.

Answer 1

It's O(1) no loops or recursion that I can see.

You shouldn't have to keep 2 stacks though. You can instead a second minNext field in the Node. It should be null except for when it contains the minimum of all subsequent elements (or it would be the top if the min stack).

public void push(int data) {
    Node newNode = new Node(data);
    if (top == null) {
        this.top = newNode;
        this.min = newMin;
    } else {
        newNode.next = this.top;
        this.top = newNode;
        if (newMin.data < this.min.data) {
            newNode.nextMin = this.min;
            this.min = newNode;
        }
    }
}

public int pop() {
    if (top == null) {
        return -1;
    }
    int tempInt = this.top.data;
    if (this.top == this.min) { // check for equality of the nodes themselves
        this.min = this.top.nextMin;
    }
    this.top = this.top.next;
    return tempInt;
}