Data structures: stacks & queues
15 min lesson
- A stack and a queue are two simple ways to store items with strict rules about the order they come out: a stack is last-in, first-out (LIFO), and a queue is first-in, first-out (FIFO).
- They matter because many real problems follow these rules: undo history, function calls, print jobs and task scheduling.
- Think of a stack as a pile of plates: you add and remove from the top only. A queue is like a line at a counter: the first person in is the first served.
- A stack has push (add to top) and pop (remove from top); the most recent item comes out first.
- A queue has enqueue (add to back) and dequeue (remove from front); the oldest item comes out first.
- Both can be built on an array or a linked list; the array version needs a capacity and a top or front/back index.
- The computer keeps a top index for a stack and front/back indices for a queue, updating them on each operation.
- The syntax for a simple array stack is: int stack[N]; int top = -1; then stack[++top] = x; and x = stack[top--];.
- A realistic use: a stack for matching brackets or undo, and a queue for handling tasks in the order they arrive.
- A surprising detail: a naive array queue wastes space as front advances; a circular buffer reuses the slots and is the standard trick.
- The example program implements a small array stack and a small array queue, pushes and enqueues values, then pops and dequeues them in order.
- Use a stack when the most recent item should come out first; use a queue for first-in, first-out.
- Always check for empty before popping or dequeuing, and for full before pushing or enqueuing.
- Use a circular buffer for array-based queues to avoid wasting slots.
- These structures appear everywhere; learn them well.
- You are building real algorithmic intuition. Excellent work!
#include <stdio.h>
#define CAP 4
int main(void) {
// Array-based stack with top index starting at -1 (empty)
int stack[CAP];
int top = -1;
// Push three values onto the stack
stack[++top] = 1;
stack[++top] = 2;
stack[++top] = 3;
// Pop them: last in, first out
while (top >= 0) {
printf("pop: %d\n", stack[top--]);
}
// Array-based queue with front and back indices
int queue[CAP];
int front = 0;
int back = 0;
// Enqueue three values at the back
queue[back++] = 10;
queue[back++] = 20;
queue[back++] = 30;
// Dequeue from the front: first in, first out
while (front < back) {
printf("dequeue: %d\n", queue[front++]);
}
return 0;
}What happens: pop: 3 pop: 2 pop: 1 dequeue: 10 dequeue: 20 dequeue: 30
Breaking it down
Stack array
int stack[CAP]; int top = -1;The array holds the items and top marks the last used index. -1 means the stack is empty.
Push
stack[++top] = 1;Increments top first, then stores the value at the new top. This adds to the top of the stack.
Pop
stack[top--]Reads the value at top, then decrements top. This removes the most recent item.
Queue indices
int front = 0; int back = 0;front points to the next item to dequeue and back points to the next free slot. Empty when front == back.
Dequeue
queue[front++]Reads the item at front, then moves front forward. This removes the oldest item.
Stack vs queue
| Feature | Stack | Queue |
|---|---|---|
| Order | LIFO | FIFO |
| Add | push (top) | enqueue (back) |
| Remove | pop (top) | dequeue (front) |
| Empty check | top == -1 | front == back |
| Example use | Undo, brackets | Print jobs, tasks |
A helpful analogy
A stack is like a pile of plates: you add and remove from the top, so the last plate placed is the first one taken. A queue is like a line at a counter: the first person in is the first one served, and new people join at the back.
Nesting rules
- 1.Check for empty before pop or dequeue; reading from an empty structure is a bug.
- 2.Check for full before push or enqueue in an array-based version.
- 3.For a stack, increment top before storing and decrement after reading.
- 4.For a circular queue, wrap indices with modulo: back = (back + 1) % CAP.
Common mistakes
Popping an empty stack
Avoid
int x = stack[top--]; // top may be -1Use instead
if (top >= 0) { int x = stack[top--]; }When top is -1 the stack is empty and reading stack[-1] is undefined behavior.
Using a linear queue until it fills
Avoid
queue[back++] = x; // back keeps growingUse instead
queue[back] = x; back = (back + 1) % CAP;A linear queue wastes space as front advances. A circular buffer reuses the freed slots.
Confusing push and enqueue order
Avoid
expecting a stack to be FIFOUse instead
use a queue for FIFO behaviorA stack removes the most recent item; a queue removes the oldest. Choose the structure that matches the rule you need.
Quick tips
- •Write is_empty and is_full helpers to keep the checks in one place.
- •Draw the top, front and back indices while tracing small examples.
- •Try filling the stack past CAP to see the need for a full check.
- •Implement a circular queue next; it is a common interview topic.
- •Use a linked list for unbounded stacks and queues when CAP is unknown.