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

PDF page 4A worked example of stack operations.

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

PDF page 9The array-based stack, continued.

PDF page 11The array-based stack in Java.

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

PDF page 17Evaluating arithmetic expressions.

PDF page 18The algorithm for evaluating expressions.

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

PDF page 24A worked example of queue operations.

PDF page 28Queue operations with the modulo operator.

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

PDF page 27The array-based queue, wrapped around.

PDF page 33The array-based implementation in Java.

PDF page 35Our Queue ADT beside java.util.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

PDF page 10Performance and limitations of the array-based stack.

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.