Skip to main content
Be Bitwise

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.
text
stack = empty
push(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]
Key Concept

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

200ms

Registers

R00
0x0000
R10
0x0000
R20
0x0000
R30
0x0000
R40
0x0000
R50
0x0000
R60
0x0000
R70
0x0000
PC0
0x0000
SP255
0x00FF
FLAGS0x00
ZCVN

ALU

Idle

Memory

PCSPWatched
Memory contents — rows indexed by base address, columns by hex offset
Address0123456789ABCDEF
0000000000000000000000000000000000
1000000000000000000000000000000000
2000000000000000000000000000000000
3000000000000000000000000000000000
4000000000000000000000000000000000
5000000000000000000000000000000000
6000000000000000000000000000000000
7000000000000000000000000000000000
8000000000000000000000000000000000
9000000000000000000000000000000000
A000000000000000000000000000000000
B000000000000000000000000000000000
C000000000000000000000000000000000
D000000000000000000000000000000000
E000000000000000000000000000000000
F000000000000000000000000000000000

Pipeline

Cycle 0
Fetch
Decode
Execute
Writeback
→
→
→
No instruction loaded

Your 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.

Try itAdd your own test strings, such as an unclosed bracket or a closer with nothing open.
C (GCC 9.2.0)

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.
text
queue = empty
enqueue(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.

Try itChange CAP to 3 or add more calls, and predict which slot each value lands in before you run it.
C (GCC 9.2.0)

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)

stack (top = last filled slot)
[0]
[1]
[2]
[3]
queue (circular buffer)
[0]↑ front
[1]
[2]
[3]
stack size = 0queue count = 0stack returned = -queue returned = -
Both start empty. The stack's next push goes into slot 0; so does the queue's next enqueue.
Step 1/10

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.

text
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.