Stacks and Queues

Learning Objectives

By the end of this page, you should be able to:

• Explain the LIFO principle of a stack and the FIFO principle of a queue, and tell them apart instantly.
• Implement a stack and a queue from scratch using both an array and a linked list.
• Explain why a naive array-based queue wastes space and how a circular queue fixes it.
• Describe when to use a deque or a priority queue instead of a plain stack or queue.
• State the time complexity of every core operation (push, pop, enqueue, dequeue, peek) for each implementation.
• Trace how a stack powers function call recursion and DFS, and how a queue powers BFS and task scheduling.

Quick Answer

A stack is a linear data structure where the last element added is the first one removed (LIFO) — think of a stack of plates. A queue is a linear data structure where the first element added is the first one removed (FIFO) — think of a line at a ticket counter. Both restrict how you access data (only from specific ends) rather than what data you store, which is exactly what makes them useful: that restriction gives predictable, efficient behavior for problems like undo history, function calls, task scheduling, and graph traversal. Stacks back DFS and recursion; queues back BFS and anything that must process items in arrival order. Variants like circular queues, deques, and priority queues exist because plain stacks/queues aren't flexible enough for every real-world need.

Introduction

Stacks and queues are the two simplest "restricted access" data structures you'll learn, and that's exactly their strength. An array lets you touch any element; a stack and a queue deliberately don't. By narrowing what you're allowed to do, they make certain problems — undo/redo, matching brackets, scheduling, graph traversal — dramatically simpler to reason about and implement.

Stacks (LIFO)

What is a Stack?

A stack is a linear data structure that follows Last-In-First-Out (LIFO): the last element pushed on is the first one popped off. Picture a stack of plates — you add a plate on top, and you take a plate off the top. You never grab one from the middle.

Key characteristics:

1. Insertions and deletions happen only at one end, called the top.
2. The element inserted most recently is the first one to leave.
3. You cannot directly access elements below the top without removing everything above them.

Stack Operations

Operation	Meaning
push(x)	Add element x to the top
pop()	Remove and return the top element
peek() / top()	Return the top element without removing it
is_empty()	Check whether the stack has any elements
size()	Return the number of elements

Array-Based Stack (Python)

class ArrayStack:
    def __init__(self):
        self._data = []

    def push(self, value):
        self._data.append(value)          # add at the end = "top"

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()           # remove from the end

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

# Trace:
s = ArrayStack()
s.push(10)   # stack: [10]
s.push(20)   # stack: [10, 20]
s.push(30)   # stack: [10, 20, 30]
s.pop()      # returns 30, stack: [10, 20]
s.peek()     # returns 20, stack unchanged

Note the trick: we treat the end of the Python list as the "top" of the stack, not the beginning. That's what makes push/pop O(1) — appending or removing from the end of a dynamic array doesn't require shifting anything.

Linked-List-Based Stack (Python)

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedStack:
    def __init__(self):
        self._head = None   # head of the list = top of the stack
        self._count = 0

    def push(self, value):
        self._head = Node(value, self._head)
        self._count += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node.next
        self._count -= 1
        return node.value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._head.value

    def is_empty(self):
        return self._head is None

    def size(self):
        return self._count

Pushing/popping at the head of a singly linked list is O(1) — no traversal needed. This is why a linked-list stack never needs resizing and never has an "amortized" cost like a dynamic array does.

Real-World Example: The Call Stack

Every time a function calls another function, the runtime pushes a new stack frame (local variables, return address) onto the call stack. When the function returns, its frame is popped. This is why deep recursion causes a "stack overflow" — you keep pushing frames without popping, until the call stack's memory limit is exceeded.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # each call pushes a new frame

Why Stacks Matter

Anywhere "undo the most recent action" or "backtrack to where you just were" applies, a stack is the natural fit: browser back button (sort of — see queues below for forward history), text editor undo, bracket matching ({[()]}), and Depth-First Search (DFS) on graphs and trees.

Common Misunderstanding

Students often think a stack must be implemented with an array. It doesn't — a linked list works just as well, and in languages without dynamic arrays, a linked-list stack avoids resizing costs entirely. The only defining property of a stack is LIFO access, not the underlying storage.

Queues (FIFO)

What is a Queue?

A queue is a linear data structure that follows First-In-First-Out (FIFO): the first element added is the first one removed. Think of a line at a coffee shop — whoever joined first gets served first.

Key characteristics:

1. Insertions happen at the rear; removals happen at the front.
2. Order of insertion is preserved and determines order of removal.
3. You cannot access the middle of the queue directly.

Queue Operations

Operation	Meaning
enqueue(x)	Add element x to the rear
dequeue()	Remove and return the front element
peek() / front()	Return the front element without removing it
is_empty()	Check whether the queue has any elements
size()	Return the number of elements

Naive Array-Based Queue — and Its Problem

class NaiveQueue:
    def __init__(self):
        self._data = []

    def enqueue(self, value):
        self._data.append(value)     # O(1): add at rear

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.pop(0)     # O(n): everything shifts left!

list.pop(0) in Python shifts every remaining element one slot to the left, so dequeue() here is O(n), not O(1). This is a genuine performance trap — fine for a toy example, but wrong for anything performance-sensitive. Python's own collections.deque avoids this by using a doubly linked structure internally.

Circular Queue (Fixing the Waste)

If you use a fixed-size array naively (front always moves forward, never wraps), the front of the array becomes "dead space" that's never reused once elements are dequeued — the queue looks full even when it has free slots at the start. A circular queue solves this by wrapping rear and front back to index 0 using modulo arithmetic.

class CircularQueue:
    def __init__(self, capacity):
        self._data = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._count = 0

    def enqueue(self, value):
        if self._count == self._capacity:
            raise OverflowError("queue is full")
        rear = (self._front + self._count) % self._capacity
        self._data[rear] = value
        self._count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._data[self._front]
        self._front = (self._front + 1) % self._capacity
        self._count -= 1
        return value

    def is_empty(self):
        return self._count == 0

    def size(self):
        return self._count

Both enqueue and dequeue are now true O(1) — no shifting, no wasted space, because the array wraps around like a clock face.

Linked-List-Based Queue (Python)

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedQueue:
    def __init__(self):
        self._front = None
        self._rear = None
        self._count = 0

    def enqueue(self, value):
        node = Node(value)
        if self._rear is None:      # empty queue
            self._front = self._rear = node
        else:
            self._rear.next = node
            self._rear = node
        self._count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        node = self._front
        self._front = node.next
        if self._front is None:     # queue became empty
            self._rear = None
        self._count -= 1
        return node.value

    def is_empty(self):
        return self._front is None

    def size(self):
        return self._count

Keeping a _rear pointer is what makes enqueue O(1) here — without it you'd have to walk the whole list to find the last node every time.

Deques (Double-Ended Queues)

A deque (pronounced "deck") allows insertion and removal from both ends in O(1). It's strictly more flexible than a stack or queue — you can use a deque as a stack or as a queue by only using one pair of ends.

from collections import deque

dq = deque()
dq.append(10)        # add to rear
dq.appendleft(5)      # add to front
dq.pop()               # remove from rear
dq.popleft()           # remove from front

Real use: a browser's history with both back and forward navigation, or a sliding-window algorithm that needs to drop elements from either end.

Priority Queues

A priority queue doesn't serve elements by arrival order — it serves the element with the highest (or lowest) priority first, regardless of when it was inserted. It's typically implemented with a binary heap, giving O(log n) insert and O(log n) remove-highest-priority, versus O(n) if you naively scanned a list each time.

import heapq

pq = []
heapq.heappush(pq, (2, "low-priority task"))
heapq.heappush(pq, (1, "high-priority task"))   # lower number = higher priority
print(heapq.heappop(pq))   # (1, "high-priority task") comes out first

Real use: OS process scheduling (run the most urgent process first), Dijkstra's shortest path, hospital emergency triage systems.

Real-World Example: The Print Queue

A shared office printer processes jobs FIFO: the first document sent is the first one printed. If it used a stack instead, the last person to hit "print" would always jump the line — clearly wrong for a "first come, first served" resource.

Real-World Example: Breadth-First Search (BFS)

BFS explores a graph level by level, and it needs a queue to do it: you enqueue a node's neighbors, and you always process nodes in the order they were discovered.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Swap that queue for a stack and you get DFS instead — a nice illustration of how the same traversal skeleton changes behavior entirely based on which restricted-access structure drives it.

Why Queues Matter

Anywhere "process in the order things arrived" matters — task schedulers, print spoolers, message queues (Kafka, RabbitMQ), request buffering in web servers, and BFS — a queue is the natural fit.

Common Misunderstanding

Students often assume dequeue() on a Python list (pop(0)) is O(1) because pop() (no argument) is O(1). It isn't — removing from the front of a dynamic array forces every other element to shift down, making it O(n). Always use collections.deque or a circular buffer for real queue behavior in Python.

Time Complexity Summary

Operation	Array-Based Stack	Linked-List Stack	Naive Array Queue	Circular Queue	Linked-List Queue	Deque (collections.deque)	Priority Queue (heap)
Insert	O(1) amortized	O(1)	O(1)	O(1)	O(1)	O(1)	O(log n)
Remove	O(1) amortized	O(1)	O(n)	O(1)	O(1)	O(1)	O(log n)
Peek	O(1)	O(1)	O(1)	O(1)	O(1)	O(1)	O(1)
Space	O(n)	O(n)	O(n)	O(n) (fixed capacity)	O(n)	O(n)	O(n)

"Amortized O(1)" for the array-based stack accounts for the occasional O(n) resize when the underlying array runs out of room and must be copied to a bigger one — this happens rarely enough that the average cost per push stays O(1).

Visualizing Push/Pop and Enqueue/Dequeue

Key Terms

Term	Definition
LIFO	"Last-In-First-Out" — the access rule that defines a stack.
FIFO	"First-In-First-Out" — the access rule that defines a queue.
Push / Pop	Add / remove the top element of a stack.
Enqueue / Dequeue	Add to the rear / remove from the front of a queue.
Top	The end of a stack where all insertions and removals happen.
Front / Rear	The removal end / insertion end of a queue.
Circular Queue	A fixed-size array queue that wraps indices with modulo arithmetic to reuse freed space.
Deque	A double-ended queue supporting O(1) insert/remove at both ends.
Priority Queue	A queue that serves elements by priority instead of arrival order, usually heap-backed.
Call Stack	The runtime stack that tracks active function calls and their local state.
Overflow / Underflow	Attempting to push onto a full fixed-size stack/queue, or pop/dequeue from an empty one.

Common Mistakes

Misconception	Why It's Wrong	Correct Understanding
"A stack must be an array."	LIFO is a behavioral contract, not a storage requirement.	A stack can be implemented with an array or a linked list — both give O(1) push/pop when done correctly (array end, or linked-list head).
"list.pop(0) is an O(1) way to dequeue in Python."	Removing the first element of a dynamic array requires shifting every remaining element left by one slot.	Use collections.deque (O(1) both ends) or a circular queue for real dequeue performance; list.pop(0) is O(n).
"A circular queue can hold unlimited elements like a regular queue."	A circular queue is backed by a fixed-size array; its capacity is set at creation.	Once count == capacity, you must resize (allocate a bigger array and copy) or reject the enqueue — it doesn't grow on its own like a Python list.

Comparison and Connections

Aspect	Stack	Queue
Access order	LIFO (last in, first out)	FIFO (first in, first out)
Ends used	One end (top)	Two ends (front for removal, rear for insertion)
Typical use	DFS, undo, call stack, bracket matching	BFS, scheduling, buffering, print spooling
Real-world analogy	Stack of plates	Line at a checkout counter

Aspect	Array-Based Implementation	Linked-List-Based Implementation
Memory layout	Contiguous block	Scattered nodes connected by pointers
Resizing	May need O(n) copy when full (dynamic array)	Never needs resizing; grows one node at a time
Memory overhead	Lower (no pointers per element)	Higher (each node stores a pointer)
Cache performance	Better (contiguous memory)	Worse (pointer chasing)
Fixed capacity option	Yes (e.g., circular queue)	Not typical

Practice Questions

Recall

1. What does LIFO stand for, and which data structure does it describe? Answer: "Last-In-First-Out" — describes a stack, where the most recently pushed element is the first one popped.
2. Name the four core operations common to both stacks and queues. Answer: Insert (push/enqueue), remove (pop/dequeue), peek (view without removing), and check-empty/size.

Understanding

3. Explain why a naive array-based queue's dequeue() is O(n) while its enqueue() is O(1). Answer: enqueue appends at the end of the array, which doesn't disturb other elements — O(1). dequeue removes from the front, forcing every remaining element to shift one index left to keep the array contiguous — O(n).
4. Why does a circular queue need a fixed capacity, and how does it reuse freed space? Answer: It's backed by a fixed-size array. Instead of always moving front and rear forward, it computes their positions modulo the capacity, so when front reaches the end of the array it wraps back to index 0, reusing slots freed by earlier dequeues.

Application

5. You're building an "undo" feature for a text editor. Which structure — stack or queue — should you use, and why? Answer: A stack. Undo must reverse the most recent action first (LIFO), so each edit is pushed, and "undo" pops the last one.
6. A ride-hailing app wants to match drivers to riders in the order riders requested a ride, but VIP riders should always be matched before regular riders regardless of when they requested. Which structure fits best? Answer: A priority queue, with VIP requests given higher priority than regular ones; among requests of equal priority, ties can be broken by arrival order (timestamp) to preserve fairness.

Analysis

7. Compare implementing a stack with a dynamic array versus a linked list. When would you prefer each? Answer: Array-based stacks have better cache locality and lower memory overhead, making them preferable when performance and memory matter and resizing is infrequent relative to usage. Linked-list stacks avoid resize costs entirely and are preferable when the maximum size is unpredictable or when O(1) worst-case (not amortized) push is required.
8. If you replace the queue in a BFS implementation with a stack, what traversal do you get instead, and why does the change in data structure cause that change in behavior? Answer: You get DFS. A queue processes nodes in the order they were discovered (breadth-first, level by level), while a stack processes the most recently discovered node next, driving the traversal deep along one path before backtracking — the traversal order is a direct consequence of the underlying structure's access rule, not the surrounding algorithm code.

FAQ

Is a stack just an array with rules? Not quite — a stack is defined by its behavior (LIFO access), not its storage. You can implement it with an array, a linked list, or even two queues. The rules are what make it a stack.

Why is a circular queue called "circular" if it's stored in a normal array? Because the logical movement of front and rear wraps around from the last index back to index 0, forming a conceptual circle, even though the underlying memory is a plain linear array.

When should I use a deque instead of a stack or a queue? When you need to add or remove from both ends efficiently — for example, a sliding window algorithm, or undo/redo history where you need to navigate both backward and forward.

Why does Python's collections.deque outperform a list for queue operations? deque is implemented as a doubly linked list of fixed-size blocks internally, giving O(1) appends and pops at both ends. A plain list only gives O(1) at the end; operations at the front require shifting all elements.

Is a priority queue really a queue? Only in name — it doesn't respect FIFO order at all. It's called a "queue" because you still enqueue/dequeue items, but the removal order is governed by priority, not arrival time.

What happens if I push to a full fixed-size stack, or pop from an empty one? Pushing to a full stack is called overflow; popping (or dequeuing) from an empty structure is called underflow. Well-written implementations raise an explicit error (as shown in the code above) instead of failing silently or crashing unpredictably.

Quick Revision

• Stack = LIFO (last in, first out); Queue = FIFO (first in, first out).
• Stack operations: push, pop, peek, is_empty, size — all O(1) with correct implementation.
• Queue operations: enqueue, dequeue, peek, is_empty, size.
• Array-based stack: push/pop at the end of the array for O(1); linked-list stack: push/pop at the head.
• Naive array queue's dequeue() (pop(0) in Python) is O(n) due to shifting — a common trap.
• Circular queue fixes wasted space by wrapping front/rear indices with modulo arithmetic; still O(1) but fixed capacity.
• Linked-list queue needs a rear pointer to keep enqueue O(1).
• Deque = double-ended queue, O(1) insert/remove at both ends (collections.deque in Python).
• Priority queue serves by priority, not arrival order; typically heap-backed, O(log n) insert/remove.
• Call stack = the reason deep recursion causes stack overflow.
• DFS uses a stack; BFS uses a queue — same traversal skeleton, different structure, different order.
• Overflow = pushing to a full structure; underflow = popping/dequeuing an empty one.

Related Topics

Prerequisites

• Arrays and their O(1) indexing / O(n) shifting behavior
• Linked lists (nodes, pointers, head/tail)

Related Topics

• Recursion and the call stack
• Graph traversal: Depth-First Search (DFS) and Breadth-First Search (BFS)
• Heaps (the usual backing structure for priority queues)

Next Topics

• Trees and tree traversal
• Hashing and hash tables
• Graph algorithms (Dijkstra's, topological sort) that build on priority queues and BFS