Stacks & Queues
🎯 Explain Like I'm 5...
Imagine you have special ways to organize your toys! Let's learn about two different ways:
📚 Stack - Like Stacking Plates:
- • Put a red plate on the table 🔴
- • Put a blue plate on top 🔵
- • Put a yellow plate on top 🟡
When you want a plate, you take the TOP one first (yellow, then blue, then red). Last one in, first one out! This is called LIFO! ⚡
🚶 Queue - Like Waiting in Line:
A queue is like waiting in line at a store or ice cream truck!
- • First kid: Alice joins the line 👧
- • Second kid: Bob joins behind Alice 👦
- • Third kid: Charlie joins at the back 🧒
Alice gets served first (she came first!), then Bob, then Charlie. First come, first served! This is called FIFO! ⚡
🚀 Why Are They Useful?
- • Stacks help with undo/redo (like in drawing apps!), checking parentheses, and going back in browser history!
- • Queues help with waiting lists, printing documents in order, and handling tasks fairly!
- • Both are super important for organizing things in the right order!
🔧 Basic Operations
Stack Operations (LIFO - Last In First Out)
Stack Using Array
public class StackArray { private int[] arr; private int top; // Points to the top element private int capacity; // Constructor - create empty stack public StackArray(int size) { arr = new int[size]; capacity = size; top = -1; // Empty stack } // Push - add element to top (like putting a plate on top!) public void push(int item) { if (isFull()) { System.out.println("Stack Overflow! Can't add more plates!"); return; } arr[++top] = item; // Increment top and add item System.out.println(item + " pushed to stack"); } // Pop - remove and return top element (take top plate!) public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! No plates to remove!"); return -1; } return arr[top--]; // Return item and decrement top } // Peek - see top element without removing (what's on top?) public int peek() { if (isEmpty()) { System.out.println("Stack is empty!"); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } // Check if stack is full public boolean isFull() { return top == capacity - 1; } // Get current size public int size() { return top + 1; } public static void main(String[] args) { StackArray stack = new StackArray(5); stack.push(10); // Stack: [10] stack.push(20); // Stack: [10, 20] stack.push(30); // Stack: [10, 20, 30] System.out.println("Top element: " + stack.peek()); // 30 System.out.println("Popped: " + stack.pop()); // 30 System.out.println("Popped: " + stack.pop()); // 20 System.out.println("Stack size: " + stack.size()); // 1 System.out.println("Is empty? " + stack.isEmpty()); // false }}Stack Using LinkedList
// Node class for the linked listclass Node { int data; Node next; Node(int data) { this.data = data; this.next = null; }}public class StackLinkedList { private Node top; // Points to top of stack private int size; // Constructor - create empty stack public StackLinkedList() { this.top = null; this.size = 0; } // Push - add element to top (create new node at front!) public void push(int item) { Node newNode = new Node(item); newNode.next = top; // New node points to old top top = newNode; // New node becomes top size++; System.out.println(item + " pushed to stack"); } // Pop - remove and return top element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow!"); return -1; } int item = top.data; top = top.next; // Move top to next node size--; return item; } // Peek - see top element without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty!"); return -1; } return top.data; } // Check if stack is empty public boolean isEmpty() { return top == null; } // Get current size public int size() { return size; } // Display all elements (from top to bottom) public void display() { if (isEmpty()) { System.out.println("Stack is empty!"); return; } System.out.print("Stack (top to bottom): "); Node current = top; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { StackLinkedList stack = new StackLinkedList(); stack.push(10); // Stack: 10 stack.push(20); // Stack: 20 -> 10 stack.push(30); // Stack: 30 -> 20 -> 10 stack.display(); // 30 20 10 System.out.println("Popped: " + stack.pop()); // 30 stack.display(); // 20 10 }}Queue Operations (FIFO - First In First Out)
Queue Using Array
public class QueueArray { private int[] arr; private int front; // Points to front element private int rear; // Points to last element private int capacity; private int count; // Current number of elements // Constructor - create empty queue public QueueArray(int size) { arr = new int[size]; capacity = size; front = 0; rear = -1; count = 0; } // Enqueue - add element to rear (join the line at back!) public void enqueue(int item) { if (isFull()) { System.out.println("Queue Overflow! Line is full!"); return; } rear = (rear + 1) % capacity; // Circular increment arr[rear] = item; count++; System.out.println(item + " joined the queue"); } // Dequeue - remove and return front element (serve first person!) public int dequeue() { if (isEmpty()) { System.out.println("Queue Underflow! No one in line!"); return -1; } int item = arr[front]; front = (front + 1) % capacity; // Circular increment count--; return item; } // Peek - see front element without removing (who's first?) public int peek() { if (isEmpty()) { System.out.println("Queue is empty!"); return -1; } return arr[front]; } // Check if queue is empty public boolean isEmpty() { return count == 0; } // Check if queue is full public boolean isFull() { return count == capacity; } // Get current size public int size() { return count; } public static void main(String[] args) { QueueArray queue = new QueueArray(5); queue.enqueue(10); // Queue: [10] queue.enqueue(20); // Queue: [10, 20] queue.enqueue(30); // Queue: [10, 20, 30] System.out.println("Front element: " + queue.peek()); // 10 System.out.println("Dequeued: " + queue.dequeue()); // 10 System.out.println("Dequeued: " + queue.dequeue()); // 20 System.out.println("Queue size: " + queue.size()); // 1 System.out.println("Is empty? " + queue.isEmpty()); // false queue.enqueue(40); // Queue: [30, 40] queue.enqueue(50); // Queue: [30, 40, 50] }}Queue Using LinkedList
// Node class for the linked listclass QueueNode { int data; QueueNode next; QueueNode(int data) { this.data = data; this.next = null; }}public class QueueLinkedList { private QueueNode front; // Points to front of queue private QueueNode rear; // Points to rear of queue private int size; // Constructor - create empty queue public QueueLinkedList() { this.front = null; this.rear = null; this.size = 0; } // Enqueue - add element to rear (join at back of line!) public void enqueue(int item) { QueueNode newNode = new QueueNode(item); // If queue is empty, new node is both front and rear if (rear == null) { front = rear = newNode; } else { // Add new node at end and update rear rear.next = newNode; rear = newNode; } size++; System.out.println(item + " joined the queue"); } // Dequeue - remove and return front element (serve first!) public int dequeue() { if (isEmpty()) { System.out.println("Queue Underflow!"); return -1; } int item = front.data; front = front.next; // Move front to next node // If front becomes null, rear should also be null if (front == null) { rear = null; } size--; return item; } // Peek - see front element without removing public int peek() { if (isEmpty()) { System.out.println("Queue is empty!"); return -1; } return front.data; } // Check if queue is empty public boolean isEmpty() { return front == null; } // Get current size public int size() { return size; } // Display all elements (from front to rear) public void display() { if (isEmpty()) { System.out.println("Queue is empty!"); return; } System.out.print("Queue (front to rear): "); QueueNode current = front; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { QueueLinkedList queue = new QueueLinkedList(); queue.enqueue(10); // Queue: 10 queue.enqueue(20); // Queue: 10 -> 20 queue.enqueue(30); // Queue: 10 -> 20 -> 30 queue.display(); // 10 20 30 System.out.println("Dequeued: " + queue.dequeue()); // 10 queue.display(); // 20 30 queue.enqueue(40); // Queue: 20 -> 30 -> 40 queue.display(); // 20 30 40 }}💡 Common Problems & Solutions
Problem 1: Valid Parentheses
Check if brackets are balanced - like making sure every opening ( has a closing )!
💡 How it works (Stack Matching Technique):
The Challenge: Every opening bracket needs a matching closing bracket in the right order
The Smart Solution (Use a Stack!):
1. When you see an opening bracket ( [ {: Push it onto the stack (remember it for later)
2. When you see a closing bracket ) ] }:
• Check if stack is empty (if yes, no matching opening bracket → invalid)
• Pop from stack and check if it matches the closing bracket
• If doesn't match → invalid
3. After processing all characters: Stack should be empty (all brackets matched)
Visual Example:
Input: "( [ { } ] )"
Step 1: '(' → push '(' to stack → Stack: ['(']
Step 2: '[' → push '[' to stack → Stack: ['(', '[']
Step 3: '{' → push '{' to stack → Stack: ['(', '[', '{']
Step 4: '}' → pop '{', matches! → Stack: ['(', '[']
Step 5: ']' → pop '[', matches! → Stack: ['(']
Step 6: ')' → pop '(', matches! → Stack: []
Result: Stack is empty → Valid! ✅
Example Invalid: "( [ )"
After ')', pop '[', doesn't match '(' → Invalid! ❌
⏱️ Time Complexity: O(n) - check each character once
💾 Space Complexity: O(n) - stack stores opening brackets
import java.util.Stack;public class ValidParentheses { public static boolean isValid(String s) { Stack<Character> stack = new Stack<>(); // Go through each character for (char c : s.toCharArray()) { // If opening bracket, push to stack if (c == '(' || c == '[' || c == '{') { stack.push(c); } // If closing bracket, check if it matches else { // If stack is empty, no matching opening bracket if (stack.isEmpty()) { return false; } char top = stack.pop(); // Check if brackets match if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } // Stack should be empty if all brackets matched return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isValid("()")); // true System.out.println(isValid("()[]{}")); // true System.out.println(isValid("(]")); // false System.out.println(isValid("([)]")); // false System.out.println(isValid("{[]}")); // true System.out.println(isValid("((")); // false }}Problem 2: Evaluate Postfix Expression
Calculate math expressions written in postfix notation (like '2 3 +' means 2+3)!
💡 How it works (Stack Evaluation):
The Challenge: Evaluate math expressions in postfix notation (operators come after operands)
What is Postfix?
• Normal (Infix): 2 + 3
• Postfix: 2 3 +
• The operator comes AFTER the numbers
The Solution (Use a Stack!):
1. Read tokens from left to right:
2. If token is a number: Push it onto the stack
3. If token is an operator (+, -, *, /):
• Pop two numbers from stack
• Apply the operator
• Push the result back onto stack
4. Final answer: The only number left in the stack
Visual Example:
Expression: "2 3 + 4 *" (means: (2+3) * 4)
Step 1: Read '2' → push 2 → Stack: [2]
Step 2: Read '3' → push 3 → Stack: [2, 3]
Step 3: Read '+' → pop 3 and 2 → calculate 2+3=5 → push 5 → Stack: [5]
Step 4: Read '4' → push 4 → Stack: [5, 4]
Step 5: Read '*' → pop 4 and 5 → calculate 5*4=20 → push 20 → Stack: [20]
Final Result: 20 ✅
Another Example: "5 1 2 + 4 * + 3 -"
= 5 + ((1+2)*4) - 3
= 5 + (3*4) - 3
= 5 + 12 - 3
= 14 ✅
⏱️ Time Complexity: O(n) - process each token once
💾 Space Complexity: O(n) - stack stores numbers
import java.util.Stack;public class EvaluatePostfix { public static int evaluatePostfix(String expression) { Stack<Integer> stack = new Stack<>(); // Split expression by spaces String[] tokens = expression.split(" "); for (String token : tokens) { // If token is a number, push to stack if (isNumber(token)) { stack.push(Integer.parseInt(token)); } // If token is an operator, pop two numbers and compute else { int num2 = stack.pop(); // Second operand int num1 = stack.pop(); // First operand int result = 0; switch (token) { case "+": result = num1 + num2; break; case "-": result = num1 - num2; break; case "*": result = num1 * num2; break; case "/": result = num1 / num2; break; } // Push result back to stack stack.push(result); } } // Final result is the only element left in stack return stack.pop(); } private static boolean isNumber(String token) { try { Integer.parseInt(token); return true; } catch (NumberFormatException e) { return false; } } public static void main(String[] args) { // Postfix: "2 3 +" means 2 + 3 = 5 System.out.println(evaluatePostfix("2 3 +")); // 5 // Postfix: "2 3 * 4 +" means (2*3) + 4 = 10 System.out.println(evaluatePostfix("2 3 * 4 +")); // 10 // Postfix: "5 1 2 + 4 * + 3 -" means 5 + ((1+2)*4) - 3 = 14 System.out.println(evaluatePostfix("5 1 2 + 4 * + 3 -")); // 14 }}Problem 3: Implement Queue Using Stacks
Build a queue using two stacks - a clever trick!
💡 How it works (Two-Stack Trick):
The Challenge: Build a Queue (FIFO) using only Stacks (LIFO)
Key Idea: Use two stacks to reverse the order twice!
The Solution:
1. Use two stacks:
• Stack 1: For enqueue operations (adding)
• Stack 2: For dequeue operations (removing)
2. Enqueue (add): Simply push to Stack 1
3. Dequeue (remove):
• If Stack 2 is empty, move all elements from Stack 1 to Stack 2
• This reverses the order! (LIFO twice = FIFO)
• Pop from Stack 2
Why does this work?
• Stack 1 reverses the order: [1, 2, 3] → top is 3
• Moving to Stack 2 reverses again: top becomes 1
• Now we can pop in FIFO order!
Visual Example:
Operations: enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue()
1. enqueue(1): Stack1: [1] Stack2: []
2. enqueue(2): Stack1: [1,2] Stack2: []
3. enqueue(3): Stack1: [1,2,3] Stack2: []
4. dequeue():
Stack2 is empty! Move all from Stack1 to Stack2:
Pop 3 from Stack1 → push to Stack2
Pop 2 from Stack1 → push to Stack2
Pop 1 from Stack1 → push to Stack2
Result: Stack1: [] Stack2: [3,2,1] (top=1)
Now pop from Stack2 → returns 1 ✅ (FIFO!)
5. dequeue():
Stack2 still has elements!
Pop from Stack2 → returns 2 ✅
Result: Stack1: [] Stack2: [3] (top=3)
⏱️ Time Complexity: O(1) amortized - each element moved at most once
💾 Space Complexity: O(n) - two stacks store elements
import java.util.Stack;public class QueueUsingStacks { private Stack<Integer> stack1; // For enqueue private Stack<Integer> stack2; // For dequeue public QueueUsingStacks() { stack1 = new Stack<>(); stack2 = new Stack<>(); } // Enqueue - add to queue (push to stack1) public void enqueue(int item) { stack1.push(item); System.out.println(item + " enqueued"); } // Dequeue - remove from queue public int dequeue() { // If both stacks are empty, queue is empty if (stack1.isEmpty() && stack2.isEmpty()) { System.out.println("Queue is empty!"); return -1; } // If stack2 is empty, move all elements from stack1 to stack2 // This reverses the order (LIFO -> FIFO) if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } // Pop from stack2 (this is the front of queue) return stack2.pop(); } // Peek - see front element public int peek() { if (stack1.isEmpty() && stack2.isEmpty()) { System.out.println("Queue is empty!"); return -1; } if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.peek(); } // Check if queue is empty public boolean isEmpty() { return stack1.isEmpty() && stack2.isEmpty(); } public static void main(String[] args) { QueueUsingStacks queue = new QueueUsingStacks(); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); System.out.println("Front: " + queue.peek()); // 10 System.out.println("Dequeued: " + queue.dequeue()); // 10 System.out.println("Dequeued: " + queue.dequeue()); // 20 queue.enqueue(40); System.out.println("Dequeued: " + queue.dequeue()); // 30 System.out.println("Dequeued: " + queue.dequeue()); // 40 }}Problem 4: Stack with Min/Max
Keep track of the minimum or maximum element while maintaining stack operations!
💡 How it works (Two-Stack Technique):
The Challenge: Get minimum element in O(1) time while maintaining normal stack operations
The Clever Solution (Use Two Stacks!):
1. Use two stacks:
• Main stack: stores all elements normally
• Min stack: tracks minimum at each level
2. Push operation:
• Always push to main stack
• Push to min stack only if value ≤ current minimum
3. Pop operation:
• Pop from main stack
• If popped value equals min stack's top, pop from min stack too
4. Get minimum: Just peek at min stack's top! (O(1))
Visual Example:
Operations: push(5), push(2), push(8), push(1), pop(), getMin()
1. push(5):
Main Stack: [5] Min Stack: [5]
(5 is first element, so it's the minimum)
2. push(2):
Main Stack: [5,2] Min Stack: [5,2]
(2 ≤ 5, so push to min stack)
3. push(8):
Main Stack: [5,2,8] Min Stack: [5,2]
(8 > 2, so DON'T push to min stack)
4. push(1):
Main Stack: [5,2,8,1] Min Stack: [5,2,1]
(1 ≤ 2, so push to min stack)
getMin() = 1 ✅ (peek at min stack)
5. pop(): removes 1
Main Stack: [5,2,8] Min Stack: [5,2]
(1 equals min stack top, so pop from min stack too)
getMin() = 2 ✅ (peek at min stack)
⏱️ Time Complexity: O(1) for all operations (push, pop, getMin)
💾 Space Complexity: O(n) - min stack stores minimums
import java.util.Stack;public class MinStack { private Stack<Integer> stack; // Main stack private Stack<Integer> minStack; // Stack to track minimum public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } // Push element to stack public void push(int val) { stack.push(val); // Update minimum stack // Push val if minStack is empty OR val is smaller than current min if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } // Pop element from stack public void pop() { if (stack.isEmpty()) { return; } int val = stack.pop(); // If popped value is minimum, pop from minStack too if (val == minStack.peek()) { minStack.pop(); } } // Get top element public int top() { if (stack.isEmpty()) { return -1; } return stack.peek(); } // Get minimum element in O(1) time! public int getMin() { if (minStack.isEmpty()) { return -1; } return minStack.peek(); } public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(5); minStack.push(2); minStack.push(8); minStack.push(1); System.out.println("Top: " + minStack.top()); // 1 System.out.println("Min: " + minStack.getMin()); // 1 minStack.pop(); // Remove 1 System.out.println("Top: " + minStack.top()); // 8 System.out.println("Min: " + minStack.getMin()); // 2 minStack.pop(); // Remove 8 System.out.println("Top: " + minStack.top()); // 2 System.out.println("Min: " + minStack.getMin()); // 2 }}🔑 Key Points to Remember
- 1️⃣Stack is LIFO (Last In First Out) - like a stack of plates!
- 2️⃣Queue is FIFO (First In First Out) - like waiting in line!
- 3️⃣Both push/pop for stack and enqueue/dequeue for queue are O(1) operations!
- 4️⃣Use Stack for undo/redo, recursion, backtracking. Use Queue for level-order traversal, scheduling!
- 5️⃣Java has built-in Stack class and Queue interface (use LinkedList or ArrayDeque)!
💪 Practice Problems
- • Next Greater Element
- • Min Stack (stack that supports getMin in O(1))
- • Implement Circular Queue
- • Reverse a queue using stack
- • Daily Temperatures (monotonic stack)
- • Design Browser History (using stacks)