Min Stack Java Design a stack that supports push, pop, top, and retrieving the m
ID: 3908394 • Letter: M
Question
Min Stack Java
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
Hint: Consider each node in the stack having a minimum value.
Include a lot of code comments in your source code. I don't understand the logic behind push(int x), pop() , top(), and getMin(). I know the hint told us to consider each node in the stack having a minimum value, but I am still confused.?
Source Code
//A class Element that has data and minimum
class Element {
public int data;
public int minimum;
public Element next;
public Element(int value, int minimum) {
this.data = value;
this.minimum = minimum;
}
}
//Our class MinStack
public class MinStack {
//Top element of Stack of Type element
public Element top;
public MinStack() {
}
//Push element at Top of stack and keep minimum in minimum
public void push(int x) {
if (top == null) {
top = new Element(x, x);
} else {
Element e = new Element(x, Math.min(x, top.minimum));
e.next = top;
top = e;
}
}
public void pop() {
if (top == null)
return;
Element temp = top.next;
top.next = null;
top = temp;
}
public int top() {
if (top == null)
return -1;
return top.data;
}
public int getMin() {
if (top == null)
return -1;
return top.minimum;
}
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
System.out.println(minStack.getMin()); // --> Returns -3.
minStack.pop();
System.out.println(minStack.top()); // --> Returns 0.
System.out.println(minStack.getMin()); // --> Returns -2.
}
}
Explanation / Answer
Hello, the concept here is simple. Don’t get it too confused. I’ll explain it.
Here, the node elements are defined to have a data value (the data it holds), the minimum value (the minimum value when the node is created) and the pointer to the next element. The push(), pop(), top() etc methods work exactly how a stack should work. The push operation pushes a value to the top of the stack, and the pop operation removes the top element from the stack (LIFO manner). The only additional concept here is the minimum value. It can be explained using below example.
Suppose the stack is empty, in that case the top element will be null, and there is no minimum element (will return -1 as it is a fixed value to return when the stack is empty)
Now we try to add an element 123. As this is the first value, the new Element object will have this value in both data and minimum fields. And this element is now assigned as the top Element .
Now we try to add an element 58. We first check if 58 is smaller than the current minimum value in the minimum field of top, which is 123. As 58 is smaller, we assign 58 as the minimum value in new node along with data, and make this node as the top node.
Now we try to add an element 72. We first check if 72 is smaller than the current minimum value in the minimum field of top, which is 58. As 72 is not smaller than 58, we assign 58 as the minimum value in new node along with data 72, and make this node as the top node.
In other words, whenever you are adding a new element, the top element will have the current minimum value in its minimum field
Top element
Next element
Next element
data: 72
data: 58
data: 123
minimum: 58
minimum: 58
minimum: 123
If you observe carefully, you can see that any moment, an element will have the minimum value in its minimum field compared to all the other elements following it. So when deletion takes place (only from top), the new top node will have the new minimum value in its minimum field. Hope you are all clear now.
//MinStack.java (with enough comments to understand the code)
//A class Element that has data and minimum
class Element {
public int data;// original data
public int minimum;// minimum value when this node is created
public Element next;
public Element(int value, int minimum) {
this.data = value;
this.minimum = minimum;
}
}
// Our class MinStack
public class MinStack {
// Top element of Stack of Type element
public Element top;
public MinStack() {
top=null;
}
// Push element at Top of stack and keep minimum in minimum
/**
* this method works like a normal stack push operation, only difference is
* that it assigns the current minimum value to the top node
*/
public void push(int x) {
if (top == null) {
/**
* This is the first entry, so we put this value as the original
* data and current minimum value. There is nothing more complex
* here.
*/
top = new Element(x, x);
} else {
/**
* This is the subsequent entry (any entry other than first). In
* this situation, we create a node (Element) which contains the
* original data and the new minimum. The new minimum value is found
* by comparing the value 'x' (the value to be inserted) and the
* minimum value at the current top element. the Math.min() method
* returns the minimum value among passed arguments. Note that the
* minimum value in other nodes are not replaced or changed, we just
* created a new element which contains the current minimum element
*/
Element e = new Element(x, Math.min(x, top.minimum));
e.next = top;
top = e;// updating the top
}
}
/**
* this method removes the top node from the stack
*/
public void pop() {
/**
* checking if the top is null, if it is null, it means the stack is
* empty, there is no element to delete
*/
if (top == null)
return;
/**
* stack is not empty.So we just remove the top node. The top element
* can be removed by making the top element point to the next element
*
* @example if the top -> A -> B -> C, we can remove top element A by
* pointing top to the next element of A, which is B
*/
Element temp = top.next;
top.next = null;
top = temp;
/**
* Note that as each element hold the minimum value until that element,
* we don't have to update the minimum value while deleting
*/
}
/**
* this method returns the value at the top without removing it
*/
public int top() {
/**
* checking if the top is null, if it is null, it means the stack is
* empty, there is no element. in this case we return -1
*/
if (top == null)
return -1;
/**
* in other cases, returning the data value at top
*/
return top.data;
}
/**
* this method returns the minimum element in the stack with maximum speed
*/
public int getMin() {
/**
* if the stack is empty, returning -1
*/
if (top == null)
return -1;
/**
* if the stack is not empty, at any moment the minimum value will be
* the minimum at top element
*/
return top.minimum;
}
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
System.out.println(minStack.getMin()); // --> Returns -3.
minStack.pop();
System.out.println(minStack.top()); // --> Returns 0.
System.out.println(minStack.getMin()); // --> Returns -2.
}
}
/*OUTPUT*/
-3
0
-2
Top element
Next element
Next element
data: 72
data: 58
data: 123
minimum: 58
minimum: 58
minimum: 123