Stacks and Queues Deep Dive
Master stacks (LIFO) and queues (FIFO): implementations, applications, and monotonic variants.
What you'll learn
- LIFO vs FIFO semantics and use cases
- Stack-based algorithms: parsing, backtracking, DFS
- Queue-based algorithms: BFS, scheduling
- Monotonic stacks for next-greater-element
Concept
Stacks and Queues Deep Dive
Stacks and queues are the two most fundamental linear data structures, distinguished by their removal order.
Stack (LIFO)
A stack removes the most recently added element (Last In, First Out). Think of a stack of plates. Stacks are natural for: function call management (the call stack), expression parsing (matching brackets), undo/redo, backtracking algorithms, and depth-first search.
Queue (FIFO)
A queue removes the oldest element (First In, First Out). Think of a line at a store. Queues are natural for: breadth-first search, task scheduling, buffering (producer-consumer), and level-order traversal.
Implementations
Both can be implemented with arrays or linked lists. Array-based stacks are simplest (push/pop at the end). Array-based queues need a circular buffer to avoid O(n) shifts.
Monotonic Stack
A monotonic stack maintains elements in sorted order, enabling efficient next greater element queries. For each element, we pop smaller elements off the stack (they found their next greater), then push the current element. This solves problems in O(n) that would be O(n^2) naively.
Deque
A double-ended queue (deque) allows insertion and removal at both ends. It generalizes both stacks and queues and is the backbone of sliding window algorithms.
Example
// Stack: balanced parentheses checker
function isBalanced(s) {
const stack = [];
const pairs = {')': '(', ']': '[', '}': '{'};
for (const ch of s) {
if ('([{'.includes(ch)) stack.push(ch);
else if (')]}'.includes(ch)) { if (stack.pop() !== pairs[ch]) return false; }
}
return stack.length === 0;
}
// Monotonic stack: next greater element
function nextGreater(arr) {
const result = new Array(arr.length).fill(-1);
const stack = [];
for (let i = 0; i < arr.length; i++) {
while (stack.length && arr[stack[stack.length-1]] < arr[i]) result[stack.pop()] = arr[i];
stack.push(i);
}
return result;
}
console.log(isBalanced('{[()]}'));
console.log(isBalanced('{[(])}'));
console.log(nextGreater([2, 1, 3, 5, 4]));
The stack-based parser pushes opening brackets and pops on closing brackets, checking they match. The monotonic stack pops indices whose value is less than the current.
Try it
- Code Minifier
Code parsing uses stacks for bracket matching and operator precedence - see it in action.
Common mistakes
The mistake
Using shift() on an array-based queue, causing O(n) per operation.
The fix
Array shift() moves every element. Use a circular buffer index or a linked list for O(1) dequeue.
The mistake
Forgetting to check stack underflow.
The fix
Calling pop() on an empty stack returns undefined. Always check length before popping.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.