- Stack Fundamentals
A stack is a linear data structure that adheres to the Last-In, First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Operations on a stack are restricted to a single end, known as the top. The other end is called the bottom.
Think of a stack like a stack of plates. You can only add a new plate to the top or remove the top plate. You cannot access the plates underneath without first removing the ones above them.
Push (or Push Operation): The process of adding an element to the top of the stack.
Pop (or Pop Operation): The process of removing the element from the top of the stack.
It's important to note that push and pop operations can be interleaved. You can push an element, then pop another, and then push again.
- Stack Implementation
A stack can be implemented using either an array or a linked list.
2.1 Array-Based Implementation
Here is an implementation using a dynamic array. The stack automatically resizes when it reaches capacity.
public class ArrayStack {
private int[] storage;
private int capacity;
private int topIndex;
public ArrayStack(int initialCapacity) {
this.capacity = initialCapacity;
this.storage = new int[initialCapacity];
this.topIndex = -1; // Indicates an empty stack
}
// Adds an element to the top of the stack
public void push(int value) {
if (isFull()) {
// Double the capacity of the array
capacity *= 2;
int[] newStorage = new int[capacity];
System.arraycopy(storage, 0, newStorage, 0, storage.length);
storage = newStorage;
}
storage[++topIndex] = value;
}
public boolean isFull() {
return topIndex == capacity - 1;
}
// Removes and returns the top element of the stack
public int pop() {
if (isEmpty()) {
throw new StackUnderflowException("Cannot pop from an empty stack.");
}
return storage[topIndex--];
}
// Returns the top element without removing it
public int peek() {
if (isEmpty()) {
throw new StackUnderflowException("Cannot peek on an empty stack.");
}
return storage[topIndex];
}
public boolean isEmpty() {
return topIndex == -1;
}
}
// Custom exception for stack underflow scenarios
class StackUnderflowException extends RuntimeException {
public StackUnderflowException() {
super();
}
public StackUnderflowException(String message) {
super(message);
}
}
2.2 Linked List-Based Implementation
For a linked list implementation, a singly linked list is sufficient. The most efficient approach is to perform insertions and deletions at the head of the list, as these operations are O(1).
class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
}
public class LinkedListStack {
private Node top;
public LinkedListStack() {
this.top = null;
}
// Adds a new node to the top of the stack
public void push(int value) {
Node newNode = new Node(value);
newNode.next = top;
top = newNode;
}
// Removes and returns the top node's value
public int pop() {
if (isEmpty()) {
throw new StackUnderflowException("Cannot pop from an empty stack.");
}
int poppedValue = top.value;
top = top.next;
return poppedValue;
}
// Returns the value of the top node
public int peek() {
if (isEmpty()) {
throw new StackUnderflowException("Cannot peek on an empty stack.");
}
return top.value;
}
public boolean isEmpty() {
return top == null;
}
}
- Solving Problems with Stacks
3.1 Valid Parentheses
Problem: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Solution: Use a stack to keep track of opening brackets. When a closing bracket is encountered, check if it matches the top of the stack.
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Map<character character=""> bracketPairs = new HashMap<>();
bracketPairs.put(')', '(');
bracketPairs.put('}', '{');
bracketPairs.put(']', '[');
Stack<character> bracketStack = new Stack<>();
for (char currentChar : s.toCharArray()) {
if (bracketPairs.containsValue(currentChar)) {
// If it's an opening bracket, push to stack
bracketStack.push(currentChar);
} else if (bracketPairs.containsKey(currentChar)) {
// If it's a closing bracket, check for a match
if (bracketStack.isEmpty() || bracketStack.pop() != bracketPairs.get(currentChar)) {
return false;
}
}
}
// If stack is empty, all brackets were matched
return bracketStack.isEmpty();
}
}
</character></character>
3.2 Validate Stack Sequences
Problem: Given two integer arrays pushed and popped, return true if they could represent the push and pop sequences of a stack, respectively.
Solution: Simulate the push and pop process. Push elements from pushed onto a temporary stack and try to pop them according to the popped sequence.
import java.util.Stack;
public class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<integer> tempStack = new Stack<>();
int popIndex = 0;
for (int value : pushed) {
tempStack.push(value);
// Try to pop while the top of the stack matches the next element in popped
while (!tempStack.isEmpty() && popIndex < popped.length && tempStack.peek() == popped[popIndex]) {
tempStack.pop();
popIndex++;
}
}
// If all elements were popped correctly, the stack should be empty
return tempStack.isEmpty();
}
}
</integer>
3.3 Evaluate Reverse Polish Notation
Problem: Evaluate the value of an arithmetic expression in Reverse Polish Notation (postfix notation).
Solution: Use a stack to store operends. When an operator is encountered, pop the top two operands, apply the operator, and push the result back onto the stack.
import java.util.Set;
import java.util.HashSet;
import java.util.Stack;
class Solution {
public int evalRPN(String[] tokens) {
Set<string> operators = new HashSet<>();
operators.add("+");
operators.add("-");
operators.add("*");
operators.add("/");
Stack<integer> valueStack = new Stack<>();
for (String token : tokens) {
if (operators.contains(token)) {
int operand2 = valueStack.pop();
int operand1 = valueStack.pop();
int result = 0;
switch (token) {
case "+":
result = operand1 + operand2;
break;
case "-":
result = operand1 - operand2;
break;
case "*":
result = operand1 * operand2;
break;
case "/":
result = operand1 / operand2;
break;
}
valueStack.push(result);
} else {
valueStack.push(Integer.parseInt(token));
}
}
return valueStack.pop();
}
}
</integer></string>
3.4 Min Stack
Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Solution: Maintain a secondary stack that keeps track of the minimum value at each level of the main stack.
import java.util.Stack;
class MinStack {
private Stack<integer> mainStack;
private Stack<integer> minStack;
public MinStack() {
mainStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
mainStack.push(val);
// Push to minStack if it's empty or the new value is less than or equal to the current minimum
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (mainStack.isEmpty()) {
return;
}
int poppedValue = mainStack.pop();
// If the popped value is the current minimum, pop it from the minStack as well
if (poppedValue == minStack.peek()) {
minStack.pop();
}
}
public int top() {
if (mainStack.isEmpty()) {
throw new StackUnderflowException("Stack is empty.");
}
return mainStack.peek();
}
public int getMin() {
if (minStack.isEmpty()) {
throw new StackUnderflowException("Stack is empty.");
}
return minStack.peek();
}
}
</integer></integer>
- Distinguishing Between Stack Concepts
Data Structure Stack: The abstract data type we've been discussing, a collection with LIFO behavior.
JVM Stack: A region of memory in the Java Virtual Machine (JVM) used for method execution. Each thread has its own JVM stack.
Stack Frame: A memory block within the JVM stack that is allocated for each method call. It stores local variables, operand stack, and other method-specific data.