Nexus Learn

Stack vs Queue: Differences and Real Examples

Stacks and queues are two of the simplest data structures. They differ only in the order that items come out, but that one difference makes them useful for very different jobs.

What is a stack?

A stack follows Last In, First Out (LIFO). The last item you put on top is the first one you take off, like a pile of plates. The two main operations are push (add to the top) and pop (remove from the top).

What is a queue?

A queue follows First In, First Out (FIFO). The first item to join is the first to leave, like people waiting in a line. The two main operations are enqueue (add at the back) and dequeue (remove from the front).

Stack vs queue: comparison

StackQueue
OrderLIFO (last in, first out)FIFO (first in, first out)
Addpush, at the topenqueue, at the back
Removepop, from the topdequeue, from the front
Time for add and removeO(1)O(1)
Real-life examplePile of plates, undo historyTicket line, print queue

Where stacks are used

  • The call stack that tracks function calls, including recursion.
  • Undo and redo in editors.
  • Checking matching brackets in code.
  • Depth-first search (DFS) in graphs.
  • The back button in a web browser.

Where queues are used

  • CPU and printer scheduling, where jobs wait their turn.
  • Breadth-first search (BFS) in graphs.
  • Handling requests in a web server.
  • Messages waiting to be processed between systems.

Using them in Python

# Stack: use a list
stack = []
stack.append(1)
stack.append(2)
stack.pop()      # returns 2

# Queue: use deque (fast at both ends)
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft()  # returns 1

Use deque for queues. Removing from the front of a normal list is slow, because every other item has to shift along.

Frequently asked questions

What is a priority queue?

It is a queue where each item has a priority, and the highest priority item leaves first, not the oldest.

What is a deque?

A deque (double-ended queue) lets you add and remove items at both the front and the back.

Which structure does recursion use?

Recursion uses the call stack. Each function call is pushed on, and popped off when it returns.

Keep learning