Stack & Queue — Stack, Queue, Deque & Real-World Applications

Module 7 — Stack & Queue: Stack, Queue, Deque & Real-World Applications Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Stack

A stack is a LIFO (Last-In, First-Out) data structure — the last element pushed on is the first one popped off, exactly like a stack of plates: you add and remove from the top only. The two core operations are push (add to the top) and pop (remove from the top), both $O(1)$.

stack<int> s;
s.push(1); s.push(2); s.push(3);
cout << s.top(); // 3
s.pop();         // removes 3

• Used for: undo/redo functionality, matching brackets, and reversing sequences.
• The function call stack itself (Module 8) is a real stack in action.

2. Queue

A queue is a FIFO (First-In, First-Out) data structure — the first element added is the first one removed, exactly like a line of people waiting: you join at the back and leave from the front. The two core operations are enqueue (add to the back) and dequeue (remove from the front), both $O(1)$ with a proper implementation.

queue<int> q;
q.push(1); q.push(2); q.push(3);
cout << q.front(); // 1
q.pop();           // removes 1

3. Deque & Real-World Applications

A deque (double-ended queue) generalizes both stack and queue by allowing insertion and removal at both ends in $O(1)$. This flexibility makes it the go-to structure for sliding-window problems, where you need to add new elements at the back while discarding stale ones from the front or back depending on the algorithm.

• Stacks power: undo/redo, expression evaluation, and depth-first traversal.
• Queues power: task scheduling, printer job queues, and breadth-first traversal.
• Deques power: sliding-window maximum/minimum problems and browser history (forward/back).