Stack vs Queue Explained With Real-Life Examples + Code
Stack and Queue are two of the most fundamental data structures — and understanding the difference (LIFO vs FIFO) unlocks dozens of algorithms. This guide explains both with real-world analogies, implementations in multiple languages, interview problems, and the advanced monotonic stack pattern.
LIFO
Stack — Last In, First Out
FIFO
Queue — First In, First Out
O(1)
push/pop/enqueue/dequeue for both
DFS/BFS
Stack enables DFS, Queue enables BFS
Stack — Last In, First Out (LIFO)
The stack of plates analogy
A stack is like a stack of plates. You add to the top (push), and you take from the top (pop). The last plate you put on is the first one you take off — LIFO. The plate at the bottom was the first added but is the last removed.
Undo/Redo (Text Editor)
Every edit pushed to the undo stack. Ctrl+Z pops the last edit. Ctrl+Y pops from the redo stack. This is a direct stack application — the most recent action undone first.
Browser Back Button
Visiting pages pushes to history stack. Back button pops. The most recently visited page is returned to first. This is LIFO in everyday use.
Function Call Stack
Every function call pushes a frame. Return pops it. "Maximum call stack size exceeded" is literally a stack overflow — the stack ran out of memory from deep recursion.
Parentheses Matching
Opening brackets pushed, closing brackets trigger a pop and match check. If the popped bracket matches, continue. If not, or stack is empty, invalid expression.
// In JavaScript, use an array as a stack
const stack = [];
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.pop(); // → 3, stack: [1, 2]
stack[stack.length - 1]; // peek at top: 2 (no removal)
stack.length; // 2
// Custom Stack class with explicit interface
class Stack {
#items = [];
push(item) { this.#items.push(item); }
pop() { return this.#items.pop(); }
peek() { return this.#items[this.#items.length - 1]; }
isEmpty() { return this.#items.length === 0; }
get size() { return this.#items.length; }
toArray() { return [...this.#items]; }
}
const s = new Stack();
s.push('a'); s.push('b'); s.push('c');
s.pop(); // → 'c'
s.peek(); // → 'b' (still in stack)
s.size; // 2# Python list as stack — simple and idiomatic
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
stack.pop() # → 3 (LIFO) — O(1)
stack[-1] # peek: 2 — no removal
# collections.deque — more efficient for large stacks (deque vs list)
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.pop() # → 2 — O(1) guaranteed (list.pop() is also O(1) but deque is cleaner)
# Python's call stack is accessible:
import traceback
traceback.print_stack() # prints the current call stack (top = current frame)Queue — First In, First Out (FIFO)
The coffee shop line analogy
A queue is like a line at a coffee shop. The first person to arrive is the first to be served. You add to the back (enqueue) and remove from the front (dequeue) — FIFO. Fair ordering, unlike a stack which always favors the latest addition.
Print Queue
Documents added to back, printed from front. First document submitted is first printed. Multiple users share one printer through FIFO ordering.
BFS Tree/Graph Traversal
Queue processes nodes level by level. Enqueue children as you process each node. Dequeue from front to always process the shallowest node first.
Message Queues (Kafka, RabbitMQ)
Messages published to back of queue, consumed from front. FIFO guarantees messages processed in order within a partition/queue.
Task Schedulers
OS process scheduler uses priority queues (variation of FIFO). Web server request queues process connections in order of arrival.
// ⚠️ Array.shift() is O(n) — avoid for large queues (shifts all elements)
const queue = [];
queue.push(1); // enqueue: [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.shift(); // dequeue: → 1, queue: [2, 3] ← O(n)!
// ✅ O(1) Queue using two stacks (amortized O(1) dequeue)
class Queue {
#inbox = []; // enqueue here
#outbox = []; // dequeue here
enqueue(item) {
this.#inbox.push(item); // O(1)
}
dequeue() {
if (this.#outbox.length === 0) {
// Transfer all — amortized O(1) per operation
while (this.#inbox.length) {
this.#outbox.push(this.#inbox.pop());
}
}
return this.#outbox.pop(); // O(1)
}
peek() {
return this.#outbox.length > 0
? this.#outbox[this.#outbox.length - 1]
: this.#inbox[0];
}
isEmpty() {
return this.#inbox.length === 0 && this.#outbox.length === 0;
}
}from collections import deque
# deque is the right choice — O(1) both ends (list.pop(0) is O(n))
q = deque()
q.append(1) # enqueue to right O(1)
q.append(2)
q.append(3)
q.popleft() # dequeue from left → 1 (FIFO) O(1)
q[0] # peek front: 2
# For thread-safe queues (producer/consumer pattern):
import queue
q = queue.Queue(maxsize=100)
q.put(item) # enqueue (blocks if full)
q.get() # dequeue (blocks if empty)
q.put_nowait(item) # raises queue.Full if fullStack vs Queue Comparison
| Item | Stack (LIFO) | Queue (FIFO) |
|---|---|---|
| Order | Last in, first out | First in, first out |
| Add operation | push (to top) | enqueue (to back) |
| Remove operation | pop (from top) | dequeue (from front) |
| Traversal algorithm | DFS (Depth-First Search) | BFS (Breadth-First Search) |
| Real-world use | Undo, call stack, backtracking, expression parsing | Task queue, print queue, BFS, message passing |
| Interview frequency | Very high — parentheses, calculator, DFS | Very high — BFS, level-order tree, sliding window |
Classic Interview: Valid Parentheses (Stack)
function isValid(s) {
const stack = [];
const pairs = { ')': '(', '}': '{', ']': '[' };
for (const char of s) {
if ('([{'.includes(char)) {
stack.push(char); // push opening bracket
} else {
// Closing bracket: check if top of stack matches
if (stack.pop() !== pairs[char]) return false;
}
}
return stack.length === 0; // unmatched opening brackets remain
}
isValid("()[]{}"); // → true
isValid("([)]"); // → false (mismatched)
isValid("{[]}"); // → true
// Variation: Minimum Add to Make Parentheses Valid
function minAddToMakeValid(s) {
let open = 0; // unmatched '('
let close = 0; // unmatched ')'
for (const c of s) {
if (c === '(') open++;
else if (open > 0) open--; // match with existing open
else close++; // unmatched close
}
return open + close;
}BFS with a Queue
function bfsLevelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root]; // Start with root
while (queue.length > 0) {
const levelSize = queue.length; // snapshot — ALL nodes at current level
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift(); // dequeue from front (FIFO)
level.push(node.val);
if (node.left) queue.push(node.left); // enqueue children
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
// Tree: [3,9,20,null,null,15,7]
// Result: [[3],[9,20],[15,7]]
// Variation: Level Order Zigzag (LeetCode 103)
// Same but alternate left-to-right and right-to-left using a flag
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length) {
const size = queue.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
leftToRight ? level.push(node.val) : level.unshift(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
leftToRight = !leftToRight;
}
return result;
}Monotonic Stack — Advanced Pattern
Monotonic Stack — used in many hard problems
// Next Greater Element — LeetCode 496
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices (monotonically decreasing values)
for (let i = 0; i < nums.length; i++) {
// Pop elements that nums[i] is greater than
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i]; // found their next greater element
}
stack.push(i);
}
return result;
}
nextGreaterElement([4,1,2,3]); // → [-1,2,3,-1]
// 4: no greater → -1
// 1: 2 is next greater → 2
// 2: 3 is next greater → 3
// 3: no greater → -1
// Daily Temperatures — LeetCode 739 (same pattern, track days)
function dailyTemperatures(temps) {
const result = new Array(temps.length).fill(0);
const stack = []; // indices of days waiting for warmer temperature
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
const prevDay = stack.pop();
result[prevDay] = i - prevDay; // days until warmer
}
stack.push(i);
}
return result;
}
dailyTemperatures([73,74,75,71,69,72,76,73]);
// → [1,1,4,2,1,1,0,0]Choose Stack for LIFO problems
Undo/redo operations, parsing nested structures (brackets, HTML tags), DFS traversal, evaluating expressions, and problems where the most recent element is most relevant.
Choose Queue for FIFO problems
BFS traversal, level-by-level processing, task scheduling where order matters, and any problem where fairness (first-come-first-served) is required.
Use deque for both ends
Python collections.deque and JavaScript implementations that support O(1) push/pop from both ends. Use for sliding window maximum, palindrome check, and any problem mixing stack and queue behavior.
Monotonic stack for next greater/smaller
When the problem asks "for each element, find the next element greater/smaller than it" — that's a monotonic stack. Template: iterate, pop elements that violate monotonic property, record answers for popped elements.
Priority queue for by-value ordering
When you need FIFO but by priority (not insertion order) — use a heap-based priority queue. Python: heapq module. Used in Dijkstra, A*, k-way merge, and task scheduling.