Stack and Queue

Definition: Abstract data types representing ordered collections; Stack follows LIFO (Last-In, First-Out), while Queue follows FIFO (First-In, First-Out).

How It Works

Stack operations: Push (add to top), Pop (remove from top), Peek (view top without removing). All O(1) when backed by a dynamic array (pushing/popping the end) or a linked list with a head pointer.

Queue operations: Enqueue (add to back), Dequeue (remove from front). O(1) when backed by a doubly linked list or a circular buffer array. Naively removing from the front of a plain dynamic array is O(n), because every remaining element must shift left by one to fill the gap.

A circular buffer (ring buffer) implements a fixed-capacity queue in a flat array by wrapping the front/back indices modulo the array size:

buffer = [_, _, _, _], front=0, back=0, size=0, capacity=4
enqueue(a): buffer[0]=a, back=1, size=1
enqueue(b): buffer[1]=b, back=2, size=2
dequeue():  return buffer[0]=a, front=1, size=1
enqueue(c): buffer[2]=c, back=3, size=2
enqueue(d): buffer[3]=d, back=0 (wraps around), size=3

This avoids both the O(n) shift problem of a naive array queue and the unbounded growth of a dynamic structure, at the cost of a fixed maximum capacity.

Queue via Two Stacks, Traced

in_stack = [], out_stack = []

enqueue(1): in_stack=[1]
enqueue(2): in_stack=[1,2]
enqueue(3): in_stack=[1,2,3]

dequeue(): out_stack is empty -> transfer all of in_stack to out_stack, reversing order
           pop 3 -> out_stack=[3]; pop 2 -> out_stack=[3,2]; pop 1 -> out_stack=[3,2,1]
           in_stack=[]
           pop out_stack -> returns 1 (the oldest element, now on top)
           out_stack=[3,2]

enqueue(4): in_stack=[4]              # out_stack is left untouched
dequeue(): out_stack is not empty -> skip transfer -> pop out_stack -> returns 2
           out_stack=[3]

The transfer only happens when out_stack is empty, so each element is moved between stacks at most once across its entire lifetime (pushed to in_stack, later moved to out_stack, later popped), giving amortized O(1) per operation despite the occasional O(n) transfer burst.

A Deque (double-ended queue) generalizes both: O(1) push/pop from either end, which is why it’s often used to implement both a stack and a queue interchangeably, e.g. Python’s collections.deque.

A Monotonic Stack/Queue, elements kept in strictly increasing or decreasing order by discarding dominated elements on insert, is a specialized pattern used to solve “next greater element” and sliding-window-maximum problems in O(n) instead of the naive O(n^2).

Complexity Analysis

Operation	Stack (array/linked list)	Queue (naive array)	Queue (circular buffer / linked list)
Push/Enqueue	O(1)	O(1)	O(1)
Pop/Dequeue	O(1)	O(n) (shifting)	O(1)
Peek	O(1)	O(1)	O(1)
Space	O(n)	O(n)	O(n)

Why It Matters

Stacks govern function execution call stacks (see Recursion), expression evaluation (operator precedence parsing, matching parentheses), undo/redo history, and backtracking algorithms like Depth-First Search (DFS).
Queues manage asynchronous task buffering, request handling in web servers, print/job queues, and breadth-first traversal (see Breadth-First Search (BFS)).
Message queue systems (task queues, event buses) generalize the FIFO queue concept to distributed systems, decoupling producers from consumers at scale so that a slow consumer doesn’t block a fast producer.

Common Pitfalls

Stack overflow caused by uncapped or runaway recursion; each recursive call pushes a frame, and an unbounded recursive depth exhausts the call stack.
Using a naive array for a queue, shifting all elements left on every dequeue, instead of a circular buffer or linked list, leads to hidden O(n) dequeue operations that only show up as a performance problem at scale.
Implementing a queue with two stacks, a common interview pattern, but forgetting to transfer elements lazily; eagerly moving elements between the two stacks on every operation destroys the intended amortized O(1) per operation.
Assuming peek() is safe on an empty stack/queue without checking emptiness first, causing an underflow error or undefined behavior.
Confusing a queue’s FIFO order with a priority queue’s priority-based order; a plain queue has no concept of element priority, only arrival order.

Comparison

	Stack	Queue	Deque	Priority Queue
Order served	Last in, first out	First in, first out	Either end, caller’s choice	Highest priority first
Typical backing structure	Array or linked list	Circular buffer or linked list	Doubly linked list / dynamic array	Binary heap
Typical use	Recursion, undo, DFS	Task buffering, BFS	Sliding window problems	Scheduling, Dijkstra
Random access to middle elements	No	No	No	No
Underlying complexity for push/pop at the relevant end	O(1)	O(1) with right structure	O(1) both ends	O(log n)

Example

A browser’s back-button history uses a Stack; a printer job queue uses a Queue.

Stack (undo history): push(edit1) push(edit2) push(edit3) -> pop() returns edit3 first
Queue (print jobs):    enqueue(doc1) enqueue(doc2) enqueue(doc3) -> dequeue() returns doc1 first

Balanced-parentheses validation is the textbook stack use case: push ( on open, pop and compare on close. "(a(b)c)" pushes and pops cleanly down to empty, correctly validating as balanced, while "(a(b)c" leaves a ( on the stack at the end, correctly flagging the input as unbalanced.

Monotonic Stack Example

Finding the “next greater element” for every value in [2, 1, 2, 4, 3] using a monotonic (decreasing) stack:

push 2 -> stack: [2]
push 1 -> stack: [2,1]              (1 < 2, no pop needed)
push 2 -> pop 1 (2>1, next-greater[1]=2) -> stack: [2,2]
push 4 -> pop 2,2 (4>2 both) -> next-greater[2]=4 (both) -> stack: [4]
push 3 -> stack: [4,3]               (3 < 4, no pop needed)

Each element is pushed once and popped at most once, so despite the nested-looking pop loop, total work is O(n), not O(n^2) as a naive nested-loop comparison would require.

FAQ

Why does implementing a queue with two stacks work? Push new elements onto an “in” stack. When a dequeue is needed and the “out” stack is empty, pop everything from “in” onto “out,” reversing the order so the oldest element ends up on top of “out.” Each element moves between stacks at most once across its lifetime, giving amortized O(1) per operation despite the occasional O(n) transfer.

Is a stack just an array with restricted operations? Conceptually, a stack is defined entirely by its LIFO contract, not by any specific backing structure; both a dynamic array and a linked list satisfy that contract equally well, differing only in constant-factor performance and memory layout.

Real-World Systems

Every function call in every mainstream programming language runtime uses a call stack, an actual LIFO stack maintained by the runtime or hardware, to track return addresses and local variables.
Browsers implement back/forward navigation with two stacks (or a deque), pushing pages as you navigate and popping as you go back.
Message queue systems like RabbitMQ, Amazon SQS, and Kafka generalize the FIFO queue to a distributed setting, letting producers and consumers operate independently at different rates, with the queue absorbing bursts.
Undo/redo systems in editors (text editors, image editors, IDEs) are typically implemented with two stacks, one for undo history and one for redo history, cleared whenever a new action is taken after an undo.

Common Interview Questions

How would you implement a stack that also supports getMin() in O(1)? — maintain a second stack that tracks the running minimum at each push, pushing the new minimum (either the new element or the current min, whichever is smaller) alongside the main stack.
How do you validate balanced brackets with multiple bracket types ((), [], {})? — push opening brackets onto a stack; on a closing bracket, pop and check it matches the corresponding opening type, failing immediately on a mismatch or an empty stack.
Why is a circular buffer preferred over a naive array-shifting queue in performance-critical code? — it turns every enqueue/dequeue into O(1) index arithmetic instead of O(n) element shifting, which matters enormously in high-throughput systems like network buffers or audio/video streaming pipelines.

Referenced by

Dig deeper

Spot an error in this note?