Stacks & Queues - Comprehensive Study Guide

🔥 Stacks - LIFO (Last In, First Out)

What is a Stack?

A Stack is an Abstract Data Type (ADT) that stores arbitrary objects following the Last-In First-Out (LIFO) principle. Think of it like a spring-loaded plate dispenser - the last plate you put on top is the first one you take off!

Stack Visualization

d (top)

↓

a (bottom)

LIFO: Element 'd' was inserted last, so it will be removed first

                    🔑 Key Characteristics:
                    LIFO Ordering: Last element inserted is the first to be removed
Restricted Access: Can only access the top element
Dynamic Size: Grows and shrinks with push/pop operations

                

⚙️ Stack Operations

Main Operations

1. push(object) - Insert Element

Adds an element to the top of the stack

void push(E element);
// Inserts element at the top
// Updates size
                    

2. pop() - Remove and Return Element

Removes and returns the element at the top of the stack

E pop();
// Removes top element
// Returns the removed element
// Returns null if stack is empty
// Decrements size
                    

Auxiliary Operations

3. top() - Peek at Top Element

Returns the top element without removing it

E top();
// Returns top element without removing
// Returns null if empty
                    

4. size() - Get Stack Size

Returns the number of elements in the stack

int size();
// Returns number of elements
                    

5. isEmpty() - Check if Empty

Checks whether the stack contains any elements

boolean isEmpty();
// Returns true if stack is empty
                    

Stack Interface in Java

public interface Stack<E> {
    int size();
    boolean isEmpty();
    E top();
    void push(E element);
    E pop();
}
                

📊 Operation Example Walkthrough

Operation	Return Value	Stack Contents	Size
push(5)	-	(5)	1
push(3)	-	(5, 3)	2
size()	2	(5, 3)	2
pop()	3	(5)	1
isEmpty()	false	(5)	1
pop()	5	()	0
isEmpty()	true	()	0
pop()	null	()	0
push(7)	-	(7)	1
push(9)	-	(7, 9)	2
top()	9	(7, 9)	2
push(4)	-	(7, 9, 4)	3
pop()	4	(7, 9)	2

💻 Stack Implementation

Array-Based Stack Implementation

Concept

A simple implementation using an array where:

Elements are added from left to right
Variable t tracks the index of the top element
Initially, t = -1 (no elements yet)

Array Stack Structure

t = 2 (pointing to 'c', the top element)

Key Algorithms

size() Algorithm

Algorithm size()
    return t + 1
// Add 1 because index starts at 0
                    

pop() Algorithm

Algorithm pop()
    if isEmpty() then
        return null
    else
        t ← t − 1
        return S[t + 1]
// Decrement top pointer first
// Return element that was at top
                    

push(o) Algorithm

Algorithm push(o)
    if t = S.length − 1 then
        throw IllegalStateException
    else
        t ← t + 1
        S[t] ← o
// Check if array is full
// Increment top pointer
// Store element at new top
                    

Java Implementation

public class ArrayStack<E> implements Stack<E> {
    // Instance variables
    private E[] S;                  // Array for storage
    private int top = -1;         // Index of top element
    
    // Constructor
    public ArrayStack(int capacity) {
        S = (E[]) new Object[capacity];
    }
    
    public E pop() {
        if (isEmpty())
            return null;
        E temp = S[top];
        S[top] = null;           // Help garbage collection
        top = top - 1;
        return temp;
    }
}
                

⚠️ Limitations of Array-Based Stack

Fixed Size: Maximum size must be defined in advance
Space Waste: May allocate more space than needed
FullStackException: Throws exception when trying to push to full stack

🎯 Applications of Stacks

Direct Applications

🌐 Web Browser History

Browser's back button uses a stack to track visited pages. Most recent page is on top!

↩️ Undo Operations

Text editors use stacks to implement undo. Each action is pushed; undo pops the last action.

☕ JVM Method Calls

Java Virtual Machine uses a call stack to manage method invocations and returns.

🔄 Expression Evaluation

Evaluating arithmetic expressions and handling operator precedence.

Parentheses Matching Example

Problem: Check if parentheses are balanced

Each opening bracket "(", "{", "[" must pair with matching closing bracket ")", "}", "]"

Expression	Valid?
( )(( )){([( )])}	✅ Correct
((( )(( )){([( )])})	✅ Correct
)(( )){([( )])}	❌ Incorrect (starts with closing)
({[ ])}	❌ Incorrect (mismatched)
(	❌ Incorrect (unclosed)

// Algorithm: Push opening brackets, pop and match closing brackets
public static boolean isMatched(String expression) {
    Stack<Character> buffer = new LinkedStack<>();
    
    for (char c : expression.toCharArray()) {
        if (opening.indexOf(c) != -1)    // Opening delimiter
            buffer.push(c);
        else if (closing.indexOf(c) != -1) { // Closing delimiter
            if (buffer.isEmpty())
                return false;           // Nothing to match
            if (closing.indexOf(c) != opening.indexOf(buffer.pop()))
                return false;           // Mismatched
        }
    }
    return buffer.isEmpty();        // All matched?
}
                

Arithmetic Expression Evaluation

Example: 14 - 3 * 2 + 7

Using operator precedence (* before +/-) and left-to-right evaluation:

Evaluate: 3 * 2 = 6
Evaluate: 14 - 6 = 8
Evaluate: 8 + 7 = 15

Result: 15

Using Two Stacks:

opStk: Holds operators (+, -, *, /)
valStk: Holds operand values

Strategy: Push operators, but first pop and perform higher/equal precedence operations

🚶 Queues - FIFO (First In, First Out)

What is a Queue?

A Queue is an Abstract Data Type (ADT) that stores arbitrary objects following the First-In First-Out (FIFO) principle. Think of it like a waiting line - the first person to arrive is the first to be served!

Queue Visualization

→

Front (a) ← → Rear (d)

Element 'a' was inserted first, so it will be removed first

                    🔑 Key Characteristics:
                    FIFO Ordering: First element inserted is the first to be removed
Two-Ended Access: Insert at rear, remove from front
Fair Processing: Elements processed in order of arrival

                

⚙️ Queue Operations

Main Operations

1. enqueue(object) - Insert at Rear

Adds an element to the rear (end) of the queue

void enqueue(E element);
// Inserts element at the rear
// Updates size
                    

2. dequeue() - Remove from Front

Removes and returns the element at the front of the queue

E dequeue();
// Removes front element
// Returns the removed element
// Returns null if queue is empty
                    

Auxiliary Operations

3. first() - Peek at Front

Returns the front element without removing it

E first();
// Returns front element without removing
// Returns null if empty
                    

4. size() - Get Queue Size

int size();
// Returns number of elements
                    

5. isEmpty() - Check if Empty

boolean isEmpty();
// Returns true if queue is empty
                    

Queue Interface in Java

public interface Queue<E> {
    int size();
    boolean isEmpty();
    E first();
    void enqueue(E element);
    E dequeue();
}
                

📊 Operation Example Walkthrough

Operation	Return Value	Queue Contents	Size
enqueue(5)	-	(5)	1
enqueue(3)	-	(5, 3)	2
dequeue()	5	(3)	1
enqueue(7)	-	(3, 7)	2
dequeue()	3	(7)	1
first()	7	(7)	1
dequeue()	7	()	0
dequeue()	null	()	0
isEmpty()	true	()	0
enqueue(9)	-	(9)	1
enqueue(7)	-	(9, 7)	2
size()	2	(9, 7)	2
enqueue(3)	-	(9, 7, 3)	3
enqueue(5)	-	(9, 7, 3, 5)	4
dequeue()	9	(7, 3, 5)	3

💻 Queue Implementation

Array-Based Circular Queue

Concept

Uses an array of size N in a circular fashion:

f = index of the front element
sz = number of stored elements
r = (f + sz) mod N = first empty slot past rear

Normal Configuration

Wrapped-Around Configuration

Queue wraps around using modulo arithmetic

Key Algorithms

enqueue(o) Algorithm

Algorithm enqueue(o)
    if size() = N − 1 then
        throw IllegalStateException
    else
        r ← (f + sz) mod N
        Q[r] ← o
        sz ← sz + 1
// Calculate rear position using modulo
// Insert at rear
// Increment size
                    

dequeue() Algorithm

Algorithm dequeue()
    if isEmpty() then
        return null
    else
        o ← Q[f]
        f ← (f + 1) mod N
        sz ← sz − 1
        return o
// Get front element
// Move front pointer forward (circular)
// Decrement size
                    

Java Implementation

public class ArrayQueue<E> implements Queue<E> {
    private E[] data;
    private int f = 0;              // Front index
    private int sz = 0;             // Current size
    
    public ArrayQueue(int capacity) {
        data = (E[]) new Object[capacity];
    }
    
    public void enqueue(E e) throws IllegalStateException {
        if (sz == data.length)
            throw new IllegalStateException("Queue is full");
        int avail = (f + sz) % data.length;
        data[avail] = e;
        sz++;
    }
    
    public E dequeue() {
        if (isEmpty())
            return null;
        E answer = data[f];
        data[f] = null;                // Help garbage collection
        f = (f + 1) % data.length;
        sz--;
        return answer;
    }
}
                

Queue Applications

📋 Waiting Lists

Customer service queues, print job queues, task scheduling

🖨️ Resource Sharing

Printer queues, CPU scheduling, shared resource access

🔄 Round Robin Scheduling

Fair time-sharing systems, process scheduling

🌐 BFS Algorithm

Breadth-First Search in graphs and trees

Round Robin Scheduler

Implement fair resource sharing by repeatedly:

e = Q.dequeue() - Get next task
Service element e - Process the task
Q.enqueue(e) - Return to back of queue

⚡ Performance & Complexity Analysis

Stack Performance

Operation	Array Implementation	Linked List Implementation
push()	O(1)	O(1)
pop()	O(1)	O(1)
top()	O(1)	O(1)
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)
Space	O(N) - fixed size	O(n) - dynamic

Queue Performance

Operation	Array Implementation	Linked List Implementation
enqueue()	O(1)	O(1)
dequeue()	O(1)	O(1)
first()	O(1)	O(1)
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)
Space	O(N) - fixed size	O(n) - dynamic

                    ✅ Key Takeaways:
                    All primary operations run in constant time O(1)
Array-based: Fixed size, potential space waste, may throw exceptions when full
Linked List-based: Dynamic size, more memory overhead per element
Space complexity is O(n) where n is number of elements

                

Stack vs Queue Comparison

Stack (LIFO)

Order: Last In, First Out
Access: One end (top only)
Operations: push, pop, top
Use Cases: Undo, recursion, parsing
Analogy: Stack of plates

Queue (FIFO)

Order: First In, First Out
Access: Two ends (front & rear)
Operations: enqueue, dequeue, first
Use Cases: Scheduling, BFS, buffering
Analogy: Waiting line

📝 Study Summary

Essential Concepts to Remember

Stack Essentials:

LIFO principle - last in, first out
Main operations: push(add), pop(remove), top(peek)
All operations are O(1) constant time
Array implementation uses index variable for top
Used for: undo operations, expression evaluation, recursive algorithms

Queue Essentials:

FIFO principle - first in, first out
Main operations: enqueue(add to rear), dequeue(remove from front), first(peek)
All operations are O(1) constant time
Array implementation uses circular buffer with modulo arithmetic
Used for: scheduling, BFS, resource sharing, buffering

🎓 Exam Tips

Understand the difference between LIFO and FIFO
Be able to trace through push/pop and enqueue/dequeue operations
Know the time complexity of all operations (O(1))
Understand circular queue implementation with modulo
Be familiar with practical applications of each structure
Practice parentheses matching and expression evaluation
Know when to use a stack vs. a queue

🎓 Practice Questions

Question 1: LIFO vs. FIFO

Q: Explain the difference between LIFO and FIFO ordering. Give one real-world analogy for each and name the data structure that implements each principle.

A: LIFO (Last In, First Out) — the most recently added item is the first removed. Real-world analogy: a stack of plates; you take from the top (the last plate placed). Data structure: Stack.
FIFO (First In, First Out) — the earliest added item is the first removed. Real-world analogy: a queue at a ticket counter; the first person in line is the first served. Data structure: Queue.
The key distinction is where removal happens: a stack removes from the same end as insertion (top), while a queue removes from the opposite end (front) from where insertion occurs (rear).

Question 2: Trace Stack Operations

Q: Starting with an empty stack, trace the following operations and give the return value and stack contents after each: push(10), push(20), push(30), pop(), top(), push(40), pop(), pop(), isEmpty().

A: 1. push(10) → stack: (10), size: 1
2. push(20) → stack: (10, 20), size: 2
3. push(30) → stack: (10, 20, 30), size: 3
4. pop() → returns 30, stack: (10, 20), size: 2
5. top() → returns 20, stack: (10, 20), size: 2 (unchanged)
6. push(40) → stack: (10, 20, 40), size: 3
7. pop() → returns 40, stack: (10, 20), size: 2
8. pop() → returns 20, stack: (10), size: 1
9. isEmpty() → returns false

Question 3: Balanced Brackets Algorithm

Q: Trace the balanced-brackets algorithm on the input ({[]}). Show the stack state after each character is processed.

A: - Read '(' → opening → push '('. Stack: ['(']
- Read '{' → opening → push '{'. Stack: ['(', '{']
- Read '[' → opening → push '['. Stack: ['(', '{', '[']
- Read ']' → closing, pop '[' → opening.indexOf('[') == closing.indexOf(']') == 2 → match! Stack: ['(', '{']
- Read '}' → closing, pop '{' → match! Stack: ['(']
- Read ')' → closing, pop '(' → match! Stack: []
Stack is empty → return true (balanced).
Note: if the stack were non-empty at the end, it would mean unclosed opening brackets → return false.

Question 4: Circular Queue Modulo Arithmetic

Q: A circular array queue has capacity 5, f=3, sz=2. What is the rear index r? Perform enqueue(X), then dequeue(). Give the values of f, sz, and r after each operation.

A: Initial state: capacity=5, f=3, sz=2.
r = (f + sz) % N = (3 + 2) % 5 = 0 (first empty slot, wrapping around).
After enqueue(X): Insert X at index r=0, then sz becomes 3. New r = (3 + 3) % 5 = 1. State: f=3, sz=3, r=1.
After dequeue(): Remove element at index f=3, f = (3+1) % 5 = 4, sz becomes 2. State: f=4, sz=2, r = (4 + 2) % 5 = 1.
The modulo ensures the front and rear pointers wrap around the end of the array, enabling reuse of space without shifting elements.

Question 5: Array vs. Linked-List Stack

Q: Compare array-based and linked-list-based stack implementations on three dimensions: time complexity, space usage, and handling overflow. Which is better?

A: - Time complexity: Both achieve O(1) for push, pop, top, size, and isEmpty. No difference.
- Space usage: Array allocates a fixed block of N cells regardless of how many elements are stored (may waste space). A linked list allocates exactly one node per element (no waste) but has extra memory overhead for the node's "next" pointer and object header.
- Overflow: Array stack throws an exception when full (fixed capacity). A linked list never overflows (except system memory).
Neither is universally better: Array stacks are preferable when N is known in advance and cache performance matters. Linked-list stacks are preferable when the maximum size is unpredictable or very large, requiring dynamic growth without reallocation.

Question 6: Applications — Stack vs. Queue

Q: For each scenario, state whether a stack or a queue is more appropriate and justify why: (a) browser back button, (b) print job scheduler, (c) BFS graph traversal, (d) undo/redo in a text editor.

A: (a) Browser back button → Stack. You want to return to the most recently visited page first (LIFO).
(b) Print job scheduler → Queue. Jobs should be printed in the order they were submitted (FIFO — fair scheduling).
(c) BFS graph traversal → Queue. BFS explores all nodes at distance k before nodes at distance k+1, which requires FIFO order. (DFS, by contrast, uses a stack.)
(d) Undo/redo → Two Stacks. Undo pops from the undo stack and pushes to the redo stack (LIFO). Redo pops from the redo stack and pushes back to the undo stack. This is the classic two-stack approach.

Question 7: Exam Trap — pop() on an Empty Stack

Q: What does pop() return on an empty stack in the array-based implementation shown in this guide? What would happen in a stricter implementation? What is the difference between returning null vs. throwing an exception?

A: The array-based implementation shown returns null when pop() is called on an empty stack (if (isEmpty()) return null;). In a stricter implementation, you might throw an EmptyStackException (or NoSuchElementException).
Returning null: Caller must check the return value. If the caller forgets to check, they get a NullPointerException later — the bug is hard to trace.
Throwing an exception: The error is surfaced immediately at the point of misuse, making bugs easier to find. Java's built-in java.util.Stack throws EmptyStackException. In competitive programming or interviews, returning null is often accepted for simplicity.

Question 8: Implementing a Queue Using Two Stacks

Q: Describe how to implement a queue using two stacks (stack1 for enqueue, stack2 for dequeue). What is the amortized time complexity of each operation?

A: Enqueue: Always push onto stack1. O(1).
Dequeue: If stack2 is empty, pop all elements from stack1 and push them onto stack2 (this reverses the order). Then pop the top of stack2. If stack2 is not empty, just pop its top directly.
Why this works: The first element pushed onto stack1 ends up at the bottom. When stack1 is flipped into stack2, that element is now at the top of stack2 — it will be dequeued first (FIFO).
Amortized complexity: Each element is pushed onto stack1 once (O(1)) and pushed onto stack2 at most once (O(1)). Averaged over N operations, each dequeue is O(1) amortized, even though the transfer step is O(N) in the worst case for a single operation.