Stacks and queues are two of the simplest data structures I’ve ever worked with, and yet I keep running into them everywhere — function call management, undo systems, breadth-first search, task scheduling, you name it. Both are, at their core, restricted versions of a general list: instead of allowing insertion and deletion at any position, each one only allows access at specific ends, and it’s exactly that restriction that makes them so predictable and easy to reason about.
I want to walk through both structures together because they make an interesting contrast: a stack follows Last-In-First-Out (LIFO) order, while a queue follows First-In-First-Out (FIFO) order. Understanding both, and how each can be implemented using either an array or a linked list, gives me a solid foundation for recognizing when each one is the right tool.
History and Background
The stack as an abstract concept in computing traces back to the early 1950s, with foundational work often attributed to Friedrich L. Bauer and Klaus Samelson, German computer scientists who patented the concept of a stack-based mechanism (the “Keller” principle, German for “cellar”) for expression evaluation and subroutine call management around 1957. Their work heavily influenced the design of stack-based programming languages and the widespread use of the call stack in virtually all modern programming language runtimes.
Queues, as a concept, are much older in the general mathematical and operations-research sense — “queueing theory” was pioneered by Agner Krarup Erlang starting in 1909 for analyzing telephone traffic — but their formalization as a computer science data structure, alongside stacks, became standard through the growth of algorithms and data structures curricula in the 1960s and 70s, and both are treated as fundamental building blocks in essentially every algorithms textbook since, including Cormen, Leiserson, Rivest, and Stein’s “Introduction to Algorithms.”
Problem Statement
I want two related but distinct abstract data types for managing an ordered collection of elements with restricted access patterns:
- A stack, which supports inserting an element (
PUSH) and removing the most recently inserted element (POP), following Last-In-First-Out order — the last element added is the first one removed. - A queue, which supports inserting an element (
ENQUEUE) at one end and removing the oldest element (DEQUEUE) from the other end, following First-In-First-Out order — the first element added is the first one removed.
Both need to support these core operations, ideally in $O(1)$ time, along with checking whether the structure is empty (and, for array-based implementations, whether it’s full).
Core Concepts
- LIFO (Last-In-First-Out): The ordering discipline of a stack — think of a physical stack of plates, where I can only add or remove from the top.
- FIFO (First-In-First-Out): The ordering discipline of a queue — think of a line of people waiting, where the first person to join is the first to be served.
- Top: The position in a stack where
PUSHandPOPboth operate. - Head / Front and Tail / Rear: In a queue, the front is where elements are removed (
DEQUEUE), and the rear (or tail) is where new elements are added (ENQUEUE). - Underflow: An error condition when attempting to remove an element from an empty stack or queue.
- Overflow: An error condition when attempting to insert into a fixed-capacity array-based stack or queue that’s already full.
- Circular buffer (circular array): A technique for implementing an array-based queue efficiently, wrapping the front and rear indices around using modular arithmetic so the array’s unused front space (left behind after dequeues) can be reused without shifting elements.
How It Works
A stack implemented with an array maintains a single index, top, marking the position of the most recently pushed element. PUSH increments top and places the new element there; POP reads the element at top and then decrements top. Both operations only ever touch one end of the array, making them naturally $O(1)$.
A queue implemented with a plain array is trickier, because insertion happens at one end (tail) and removal happens at the other (head), and if I don’t wrap around, the “used” region of the array would just keep sliding forward until it runs off the end, wasting the space at the front that earlier dequeues freed up. The standard fix is a circular array: I track both head and tail indices, and whenever either would go past the end of the array, I wrap it back to index 0 using modular arithmetic, effectively treating the array as a ring.
Both structures can alternatively be implemented using a linked list — a stack maps naturally onto inserting and removing at the head of a singly linked list, while a queue needs pointers to both the head (for dequeue) and the tail (for enqueue) to keep both ends $O(1)$.
Working Principle
What makes stacks and queues efficient is that, unlike a general list, they never need to search for an insertion or deletion point — the access point is always fixed and already known (top for a stack; head/tail for a queue), so every operation is a direct, constant-time manipulation of a known position, with no traversal required.
For the array-based queue specifically, the circular-buffer technique works because addition modulo the array’s capacity naturally “wraps” an index back to the beginning once it would otherwise run past the end, letting the queue’s logical window of occupied slots slide endlessly around the fixed-size array without ever needing to physically shift elements — the only bookkeeping needed is tracking how many elements are currently stored, to distinguish a completely full circular buffer from a completely empty one (since both can otherwise look identical, with head == tail).
Mathematical Foundation
Capacity and occupancy invariant for a circular array queue. If the array has capacity $n$, and I track a count of currently stored elements $s$, then:
$$ 0 \le s \le n $$
The queue is empty when $s = 0$, and full when $s = n$. Using the head and tail indices directly (without a separate count), the same information can be recovered, but requires being careful about distinguishing full from empty, since both cases can result in head == tail unless I explicitly track a count or always deliberately leave one slot empty.
Circular index update. Given capacity $n$, inserting at the tail and advancing it is computed as:
$$ tail = (tail + 1) \bmod n $$
and similarly for advancing the head after a dequeue:
$$ head = (head + 1) \bmod n $$
Amortized cost of dynamic array resizing. If a stack or queue is implemented with a dynamically growing array (doubling capacity whenever full), the amortized cost per PUSH/ENQUEUE operation, accounting for the occasional $O(n)$-time resize, is:
$$ T_{amortized} = O(1) $$
This follows from the standard aggregate analysis of dynamic array doubling: across $n$ insertions, the total cost of all resizing operations combined is $O(n)$ (since resize costs form a geometric series $1 + 2 + 4 + \dots + n = O(n)$), so the average cost per insertion is $O(n)/n = O(1)$.
Diagrams
flowchart TD
subgraph Stack [Stack - LIFO]
S1[PUSH adds here: top] --> S2[Middle elements]
S2 --> S3[Bottom - oldest element]
end
subgraph Queue [Queue - FIFO]
Q1[ENQUEUE adds here: tail/rear] --> Q2[Middle elements]
Q2 --> Q3[DEQUEUE removes here: head/front]
endPseudocode
Array-based stack:
STACK-EMPTY(S)
if S.top == 0
return TRUE
else
return FALSE
PUSH(S, x)
if S.top == S.capacity
error "overflow"
S.top = S.top + 1
S[S.top] = x
POP(S)
if STACK-EMPTY(S)
error "underflow"
else
S.top = S.top - 1
return S[S.top + 1]
Circular array-based queue:
ENQUEUE(Q, x)
if Q.size == Q.capacity
error "overflow"
Q[Q.tail] = x
if Q.tail == Q.capacity - 1
Q.tail = 0
else
Q.tail = Q.tail + 1
Q.size = Q.size + 1
DEQUEUE(Q)
if Q.size == 0
error "underflow"
x = Q[Q.head]
if Q.head == Q.capacity - 1
Q.head = 0
else
Q.head = Q.head + 1
Q.size = Q.size - 1
return x
Step-by-Step Example
Stack example. Starting empty (top = 0), I PUSH(10), PUSH(20), PUSH(30), then POP() twice.
PUSH(10):top = 1,S[1] = 10. Stack (bottom to top):[10].PUSH(20):top = 2,S[2] = 20. Stack:[10, 20].PUSH(30):top = 3,S[3] = 30. Stack:[10, 20, 30].POP(): returnsS[3] = 30,top = 2. Stack:[10, 20].POP(): returnsS[2] = 20,top = 1. Stack:[10].
The order of removal, 30 then 20, confirms LIFO behavior — the most recently pushed elements come off first.
Queue example (circular array, capacity 4). Starting empty (head = 0, tail = 0, size = 0), I ENQUEUE(10), ENQUEUE(20), ENQUEUE(30), then DEQUEUE() twice, then ENQUEUE(40).
ENQUEUE(10):Q[0] = 10,tail = 1,size = 1.ENQUEUE(20):Q[1] = 20,tail = 2,size = 2.ENQUEUE(30):Q[2] = 30,tail = 3,size = 3.DEQUEUE(): returnsQ[0] = 10,head = 1,size = 2.DEQUEUE(): returnsQ[1] = 20,head = 2,size = 1.ENQUEUE(40):Q[3] = 40,tail = (3+1) mod 4 = 0(wraps around!),size = 2.
At this point, head = 2 and tail = 0, with the queue logically containing 30 (at index 2) and 40 (at index 3), demonstrating how the circular wraparound lets the array reuse the space freed up by the earlier dequeues at indices 0 and 1.
Time Complexity
| Operation | Stack (array or linked list) | Queue (circular array or linked list) |
|---|---|---|
Insert (PUSH / ENQUEUE) | $O(1)$ | $O(1)$ |
Remove (POP / DEQUEUE) | $O(1)$ | $O(1)$ |
| Peek (view top/front without removing) | $O(1)$ | $O(1)$ |
| Check empty | $O(1)$ | $O(1)$ |
| Dynamic resize (amortized, growable array version) | $O(1)$ amortized | $O(1)$ amortized |
Both structures achieve constant-time operations because, as discussed, they only ever touch a fixed, known position — no traversal or searching is ever required for the core operations.
Space Complexity
Both array-based and linked-list-based implementations use $\Theta(n)$ space for $n$ stored elements. An array-based implementation with a fixed capacity $c$ uses $\Theta(c)$ space regardless of how many elements are actually stored, potentially wasting space if $c$ is much larger than needed; a dynamically resized array amortizes this better but can still temporarily use up to roughly double the space actually needed right after a resize. A linked-list-based implementation uses exactly $\Theta(n)$ space for the elements actually present, plus pointer overhead per node, with no wasted pre-allocated capacity, but with the general tradeoffs of pointer-based structures discussed elsewhere (worse cache locality, per-allocation overhead).
Correctness Analysis
For the array-based stack, correctness follows directly from the invariant that S[1..top] always contains exactly the currently-pushed elements, in the order they were pushed, with S[top] always being the most recently pushed (and therefore next to be popped) element. PUSH and POP each modify top by exactly one and correspondingly write or read S[top], preserving this invariant by construction.
For the circular array queue, correctness depends on the invariant that the size elements currently in the queue occupy exactly the circular range of indices starting at head and extending forward (with wraparound) for size positions, ending just before tail. ENQUEUE writes at tail and then advances it (with wraparound via modulo), while DEQUEUE reads at head and then advances it the same way, both consistently maintaining this invariant. Explicitly tracking size (rather than relying solely on comparing head and tail) is what correctly disambiguates the full case from the empty case, since both would otherwise present identically as head == tail.
Advantages
- Extremely simple and predictable operations, all $O(1)$, with minimal room for algorithmic subtlety once implemented correctly.
- Natural fit for a wide range of real problems: undo functionality, expression parsing, task scheduling, breadth-first and depth-first traversal.
- Array-based implementations offer excellent cache locality and low per-element memory overhead compared to pointer-based structures.
- Linked-list-based implementations avoid the need to predict a maximum capacity in advance and avoid overflow errors (aside from running out of memory generally).
Disadvantages
- Restricted access pattern means stacks and queues can’t efficiently support arbitrary-position insertion, deletion, or search — for that, a different structure (like a plain linked list, deque, or balanced tree) is needed.
- Fixed-capacity array implementations risk overflow if not sized generously enough, or waste memory if sized too generously.
- Circular array queues require slightly more careful bookkeeping (tracking
sizeor an equivalent) to correctly distinguish full from empty states, a common source of subtle bugs. - Linked-list-based implementations incur pointer overhead and generally worse cache performance compared to array-based versions.
Applications
- Stacks: Function call management (the “call stack”) in essentially every programming language runtime; expression evaluation and syntax parsing (matching parentheses, evaluating postfix expressions); undo/redo functionality in editors; depth-first search and backtracking algorithms.
- Queues: Task scheduling in operating systems (ready queues, print queues); breadth-first search in graph algorithms; buffering data between producers and consumers at different processing speeds (I/O buffers, message queues); simulation of real-world waiting-line systems.
- Both structures also serve as building blocks for more advanced structures: a deque (double-ended queue) generalizes both, and priority queues (often implemented with heaps) generalize the queue concept further by adding priority-based ordering instead of pure FIFO order.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define CAPACITY 5
/* ---------- Array-based Stack ---------- */
typedef struct {
int data[CAPACITY];
int top; /* number of elements currently in the stack */
} Stack;
void stackInit(Stack* s) {
s->top = 0;
}
int stackIsEmpty(Stack* s) {
return s->top == 0;
}
void push(Stack* s, int x) {
if (s->top == CAPACITY) {
printf("Stack overflow\n");
return;
}
s->data[s->top] = x;
s->top++;
}
int pop(Stack* s) {
if (stackIsEmpty(s)) {
printf("Stack underflow\n");
return -1;
}
s->top--;
return s->data[s->top];
}
/* ---------- Circular Array-based Queue ---------- */
typedef struct {
int data[CAPACITY];
int head;
int tail;
int size; /* tracks occupancy to disambiguate full vs. empty */
} Queue;
void queueInit(Queue* q) {
q->head = 0;
q->tail = 0;
q->size = 0;
}
int queueIsEmpty(Queue* q) {
return q->size == 0;
}
void enqueue(Queue* q, int x) {
if (q->size == CAPACITY) {
printf("Queue overflow\n");
return;
}
q->data[q->tail] = x;
q->tail = (q->tail + 1) % CAPACITY;
q->size++;
}
int dequeue(Queue* q) {
if (queueIsEmpty(q)) {
printf("Queue underflow\n");
return -1;
}
int x = q->data[q->head];
q->head = (q->head + 1) % CAPACITY;
q->size--;
return x;
}
int main(void) {
/* --- Stack demo --- */
Stack s;
stackInit(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("Stack pops: ");
printf("%d ", pop(&s));
printf("%d ", pop(&s));
printf("\n");
/* --- Queue demo (matches the circular wraparound example) --- */
Queue q;
queueInit(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("Queue dequeues: ");
printf("%d ", dequeue(&q));
printf("%d ", dequeue(&q));
printf("\n");
enqueue(&q, 40); /* this will wrap around within the circular array */
printf("Remaining queue elements (front to back): ");
while (!queueIsEmpty(&q)) {
printf("%d ", dequeue(&q));
}
printf("\n");
return 0;
}
I chose to track size explicitly in the Queue struct rather than relying only on comparing head and tail, precisely because of the full-versus-empty ambiguity discussed earlier — this is a small design decision, but it meaningfully simplifies the correctness of queueIsEmpty and the overflow check in enqueue.
Sample Input and Output
Input:
Stack: push 10, 20, 30, then pop twice
Queue: enqueue 10, 20, 30, then dequeue twice, then enqueue 40, then drain
Output:
Stack pops: 30 20
Queue dequeues: 10 20
Remaining queue elements (front to back): 30 40
The stack output confirms LIFO order (30 then 20, the two most recently pushed). The queue output confirms FIFO order throughout, and the final drain correctly shows 30 followed by 40, exactly matching my hand-traced circular buffer example.
Optimization Techniques
- Dynamic array growth (amortized doubling): For both stacks and queues, replacing a fixed capacity with a dynamically growing array (doubling capacity on overflow) achieves $O(1)$ amortized insertion while removing the fixed-capacity limitation.
- Using a linked list to avoid capacity limits entirely: Trades some cache locality and per-node memory overhead for a structure that never needs an explicit “overflow” check.
- Two-stack queue trick: A queue can be implemented using two stacks (one for enqueuing, one for dequeuing, transferring elements between them only when the dequeue stack is empty), achieving amortized $O(1)$ per operation — a classic technique worth knowing even though a circular array or linked list is usually simpler in practice.
- Avoiding modulo for performance: In very performance-sensitive code, replacing
% CAPACITYwith a conditional check-and-wrap (if (index == CAPACITY) index = 0;) can be faster than a true modulo operation, especially whenCAPACITYisn’t a compile-time power of two. - Power-of-two capacities: Choosing a queue’s capacity to be a power of two allows replacing the modulo operation with a fast bitwise AND (
index & (CAPACITY - 1)), a common low-level optimization in performance-critical queue implementations.
Common Mistakes
- Confusing full and empty states in a circular array queue when relying only on
head == tailwithout a separatesize(or equivalent) field — this is probably the single most common bug in queue implementations. - Off-by-one errors in
topindexing for array-based stacks, particularly confusion between whethertoprepresents “the index of the top element” versus “the number of elements currently in the stack” (I used the latter convention above, which simplifiesstackIsEmptyto a simple zero-check). - Not checking for overflow/underflow, leading to writing past array bounds or reading from an empty structure, both of which produce undefined behavior in C.
- Forgetting the wraparound in circular queue index updates, incorrectly incrementing
headortailwithout the modulo (or equivalent conditional), which causes an out-of-bounds array access once the index reaches the array’s capacity. - Memory leaks in linked-list-based implementations, forgetting to
free()nodes as they’re popped or dequeued. - Assuming a queue implemented naively with a plain (non-circular) array and simple index shifting is efficient — shifting all remaining elements forward after every dequeue silently turns an intended $O(1)$ operation into $O(n)$, a mistake I’ve seen even experienced programmers make when they don’t realize a circular buffer (or linked list) is needed.
Further Reading
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Chapter 10: “Elementary Data Structures,” MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Knuth, Donald E., The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- Bauer, Friedrich L., and Klaus Samelson, historical overview of stack-based computation (Stanford Encyclopedia summary): https://plato.stanford.edu/entries/computing-history/
- GeeksforGeeks, “Stack Data Structure”: https://www.geeksforgeeks.org/dsa/stack-data-structure/
- GeeksforGeeks, “Queue Data Structure”: https://www.geeksforgeeks.org/dsa/queue-data-structure/
- Sedgewick, Robert, and Kevin Wayne, Algorithms, 4th Edition, Addison-Wesley: https://algs4.cs.princeton.edu/13stacks/
