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