Topic 37 of 78
Stack
Overview
A Stack is a linear data structure that operates on the LIFO principle: Last In, First Out. Think of a stack of plates in a cafeteria; the last plate you put on top is the first one you pick up. Stacks are mathematically critical for managing state, reversing data, and parsing recursive structures (like verifying if parentheses are balanced in a code editor).
Syntax
Array implementations are extremely fast but have a fixed size limit (Stack Overflow!). In Java, `java.util.Stack` is legacy; modern Java uses `Deque<Integer> stack = new ArrayDeque<>();`.
Stack using an Array
java
public class ArrayStack {
private int[] stack;
private int top; // Index of the top element
public ArrayStack(int capacity) {
stack = new int[capacity];
top = -1; // -1 means empty
}
// O(1) Push (Add to top)
public void push(int value) {
if (top == stack.length - 1) throw new StackOverflowError();
stack[++top] = value;
}
// O(1) Pop (Remove from top)
public int pop() {
if (isEmpty()) throw new EmptyStackException();
return stack[top--];
}
public boolean isEmpty() { return top == -1; }
}Common Pitfalls
- Stack Overflow: Pushing too many elements into a fixed-size stack (or making too many recursive function calls).
- Using the legacy `java.util.Stack` class instead of the modern, faster `ArrayDeque`.
Interview Tips
- Stacks follow the LIFO (Last In, First Out) principle. It's heavily used in parsing algorithms and backtracking.
Real-World Example
The JVM (Java Virtual Machine) literally uses a Stack to execute methods. Every time you call a method, its variables are pushed onto the Call Stack. When it returns, it is popped off.
example
java
public boolean isValidParentheses(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '{') stack.push('}');
else if (c == '[') stack.push(']');
else if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
return stack.isEmpty();
}