Skip to content
Gallery
Data Structures and Algorithms
Data Structures and Algorithms
Share
Explore
Stack & Queue

Implementing a Min Stack

Before diving into the specifics of a Min Stack, let's understand what a stack is. A stack is a fundamental data structure in computer science, known for its simplicity and efficiency. It operates on the principle of Last In, First Out (LIFO), meaning the last item added is the first one to be removed. Imagine a stack of plates; you always take from the top and add to the top. The basic operations in a stack are:
Push: Add an item to the top of the stack.
Pop: Remove the top item from the stack.
Peek: View the top item without removing it.

What is a Min Stack?

A Min Stack is an extension of the regular stack that allows you to access the smallest element in the stack quickly and efficiently. This is particularly useful in various algorithmic problems where you need to keep track of the minimum element as you add or remove items.

Implementing a Min Stack in Java

In our implementation, we'll use two stacks: one to hold the actual stack elements and another to hold the minimum elements.
Class Structure
We will create a class named MinStack with two private properties - a stack to store the elements (stack) and another stack to store the minimum elements (minStack).
Method Implementations
push(int x): This method adds an element x to the stack. If x is smaller than or equal to the current minimum, we also push it to the min stack.
pop(): This method removes the top element of the stack. If the top element is the current minimum, we also pop it from the min stack.
top(): Returns the top element of the stack.
getMin(): Returns the minimum element in the stack.

Example Code

Here is a simple Java implementation:
import java.util.Stack;

public class MinStack {
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();

public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}

public void pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}

public int top() {
return stack.peek();
}

public int getMin() {
return minStack.peek();
}
}

Explanation of Code

Push Method: When a new element is pushed, it's always added to the stack. If this element is smaller than or equal to the top element of min stack, it's also pushed to min stack.
Pop Method: When popping, if the top element of the stack is the same as the top element of the min stack, we pop from both stacks. This keeps our min stack updated with the next minimum element.
Top and GetMin Methods: top() gives the top element of the stack without removing it, while getMin() returns the current minimum element, which is the top element of minStack.

Conclusion

The Min Stack is a clever twist on a simple data structure that provides efficient access to the minimum element. This implementation in Java is straightforward once you understand the basics of stacks and Java's Stack class. Experiment with this code, try adding new methods, or apply these concepts to other data structures to deepen your understanding.
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.