Stacks & Queues
Arrays, Lists & Data Structures · Coding Fundamentals track
6 min read
In this module
Restricted Access Structures
Arrays and linked lists let you reach any element. Sometimes, though, you want a data structure that deliberately limits how you interact with it. That sounds like a downgrade, but the restriction is the point — it enforces a discipline that prevents misuse.
Stacks and queues are the two most important restricted-access structures. You've already met stacks while studying the call stack. Time to formalise the concept.
Stacks: Last In, First Out
A stack is a collection where you can only add or remove elements from the top. The last element added is the first one removed. That's Last In, First Out (LIFO).
The two fundamental operations:
- Push — add an element to the top.
- Pop — remove and return the element from the top.
stack = emptypush(stack, "A") // stack: [A]push(stack, "B") // stack: [A, B]push(stack, "C") // stack: [A, B, C]
pop(stack) // returns "C", stack: [A, B]pop(stack) // returns "B", stack: [A]A stack enforces LIFO ordering: the most recently pushed element is the first one popped. Both push and pop are O(1) operations. Stacks are the natural structure for anything that needs to "undo" or "go back" - the call stack, undo history, expression parsing, and depth-first search.
Stacks You Already Know
The call stack is the most important stack in all of computing. Every function call pushes a stack frame; every return pops one. It earned the name "stack" precisely because it's LIFO — the most recently called function is the first to return.
The processor has push and pop built in. In the simulator below, step through the program and watch the stack pointer, SP, drop by one on each PUSH as the value lands in memory, then climb back on each POP. The three values come back out in reverse order.
For the best simulation experience, use a desktop browser.
Assembly
Registers
ALU
Memory
| Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 10 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 20 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 30 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 40 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 50 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 60 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 70 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 80 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| 90 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| A0 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| B0 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| C0 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| D0 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| E0 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
| F0 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 | 00 |
Pipeline
Cycle 0Your browser's back button is also a stack: each page visit pushes onto the history stack, and clicking back pops the most recent page.
Undo in a text editor follows the same shape. Each action pushes onto the undo stack, and Ctrl+Z pops the most recent action to reverse it.
Compilers use a stack to check that brackets match. Every opener gets pushed; every closer must match whatever's on top. Predict which of the test strings pass, then add a few of your own.
Queues: First In, First Out
A queue is a collection where elements are added at the back and removed from the front. The first element in is the first one out. That's First In, First Out (FIFO).
The two fundamental operations:
- Enqueue — add an element to the back.
- Dequeue — remove and return the element from the front.
queue = emptyenqueue(queue, "A") // queue: [A]enqueue(queue, "B") // queue: [A, B]enqueue(queue, "C") // queue: [A, B, C]
dequeue(queue) // returns "A", queue: [B, C]dequeue(queue) // returns "B", queue: [C]Queues model anything that involves waiting in line: print jobs, network packets, task scheduling, breadth-first search.
Implementation Choices
You can build stacks and queues out of either arrays or linked lists.
Stack with an array: keep a pointer to the top index. Push increments the pointer and writes the value. Pop reads the value and decrements the pointer. Both O(1).
Stack with a linked list: push inserts at the head, pop removes from the head. Both O(1).
Queue with an array: use a circular buffer — maintain a front index and a back index that wrap around the end of the array. That avoids the cost of shifting everything down each time you remove from index 0.
Queue with a linked list: enqueue appends at the tail, dequeue removes from the head. Both O(1), provided you keep both head and tail pointers.
Here's a circular buffer with room for four items. Watch the front and back indices wrap past the end of the array instead of shifting anything.
Here's the same sequence of calls run on an array-backed stack and on the circular-buffer queue at the same time, both with four slots. Grey cells hold values that have been removed but not yet overwritten. Watch which value each structure hands back at steps 5 and 6.
Same calls, stack against queue (4 slots each)
Priority Queues
A priority queue is a variation where each element carries a priority. The element with the highest priority comes out first, no matter when it went in.
enqueue(pq, "low priority task", priority=1)enqueue(pq, "urgent task", priority=10)enqueue(pq, "medium task", priority=5)
dequeue(pq) // returns "urgent task" (highest priority)Priority queues are typically built on a heap (a specialised tree structure), not a plain array or linked list. They turn up in Dijkstra's shortest path, operating system task scheduling, and event-driven simulations.
Stacks and Queues in Systems
Zoom out to the systems level and stacks and queues are everywhere:
- The CPU call stack is a stack that manages function calls and local variables.
- Interrupt handling uses a stack to save and restore processor state.
- Network buffers are queues holding incoming packets until the application is ready.
- Process scheduling in operating systems uses queues (and priority queues) to decide which process runs next.
- Keyboard input buffers are queues — keystrokes get processed in the order you typed them.
Once you've internalised these abstract structures, you start to spot the same patterns underlying the concrete systems you use every day.
The Discipline of Restriction
Choosing a data structure that limits what you can do sounds counterintuitive at first. Why bother with a stack when an array gives you access to any element? Because the restriction is the feature. A stack guarantees you process the most recent item first — exactly what function calls, undo operations, and parsing need. A queue guarantees arrival-order processing, which is what task scheduling and message handling demand. Constraining access makes intent explicit and shuts the door on accidental misuse. Reaching for a stack or queue instead of a generic array tells both the compiler and the next reader exactly how the data is meant to be used.