CodingwithDom
Subscribe

Stack vs queue: what is the difference?

CS Fundamentals 2 min read
Short answer

A stack removes the most recently added item (LIFO). A queue removes the oldest (FIFO). Depth-first search uses a stack; breadth-first search uses a queue.

python
# Stack — LIFO
stack = []
stack.append(1); stack.append(2)
stack.pop()           # 2

# Queue — FIFO
from collections import deque
queue = deque()
queue.append(1); queue.append(2)
queue.popleft()       # 1

#Where each shows up

Stacks:

  • The call stack — every function call pushes a frame
  • Undo history
  • Matching brackets in a parser
  • Depth-first search
  • Backtracking (mazes, sudoku, n-queens)

Queues:

  • Job and task queues
  • Breadth-first search, and therefore shortest path on an unweighted graph
  • Print spoolers, request buffers
  • Rate limiting

#The one that decides your algorithm

Swap the stack for a queue in a graph traversal and depth-first becomes breadth-first. Same code, entirely different traversal order — and only BFS finds the shortest path.

python
def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()        # popleft → BFS, pop → DFS
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)

#Priority queue

A third variant: removes the smallest item rather than the oldest or newest. Python's heapq implements it, and it is what Dijkstra's algorithm and most schedulers run on.

Related answers