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)\$.