Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 225 ยท Stacks and Queues

Queues

Understand queues in Python: FIFO order, why list.pop(0) is slow, collections.deque, a linked-list queue, and a queue built from two stacks, with complexity.

A queue is the data structure of waiting in line. The first person to join the line is the first to be served. Computing is full of lines: print jobs waiting for a printer, web requests waiting for a worker, messages waiting to be processed, and the next node to visit in a breadth-first search.

This rule is called FIFO: First In, First Out. It is the mirror image of a stack, which is LIFO. In this lesson you will build queues three ways, see why the "obvious" Python list is a poor choice, and learn the neat trick of building a queue out of two stacks.

The operations

A queue is an abstract data type. It promises these operations:

Operation Meaning Target cost
enqueue(x) add x at the back O(1)
dequeue() remove and return the item at the front O(1)
peek() look at the front item without removing it O(1)
is_empty() is there anything in line? O(1)
len(q) how many items are waiting O(1)
TEXT
enqueue ->  back [ D  C  B  A ] front  -> dequeue
              new arrivals join here      oldest leaves here

Everything in the table should be O(1). The challenge is picking a representation that actually delivers that.

Attempt 1: a Python list (and its trap)

The easiest queue is a list: append(x) to enqueue, pop(0) to dequeue.

It works, but pop(0) removes the first element, so every remaining element must shift one slot to the left. That is O(n) per dequeue. Draining a queue of n items costs about nยฒ/2 shifts. Compare with pop() (from the end), which is O(1), and see arrays for why.

Python The list.pop(0) trap, in operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shift count grows roughly with the square of n: ten times more items means about a hundred times more work. For small queues you will never notice, but a queue of a million items would be painfully slow.

Never use list.pop(0) or list.insert(0, x) in a loop that processes many items. Use collections.deque instead.

Attempt 2: collections.deque (the right tool in Python)

collections.deque ("deck", for double-ended queue) is a doubly linked list of small blocks. It supports O(1) appends and pops at both ends. For a queue, add on the right with append and remove from the left with popleft.

Python A queue with collections.deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notes about deque:

  • d[0] and d[-1] are O(1), but indexing into the middle is O(n). A deque is for ends, not random access.
  • popleft() on an empty deque raises IndexError. Check if d: first.
  • deque(maxlen=k) keeps only the last k items, dropping from the other end when full. We will use it in Circular Queue and Ring Buffer.

Attempt 3: a linked-list queue

To see how a real O(1) queue works, build one from a singly linked list that keeps two pointers: head (the front) and tail (the back).

  • Enqueue: attach a new node after tail, then move tail to it.
  • Dequeue: take the node at head, then move head to the next node.
TEXT
head                tail
 |                   |
 v                   v
[A] -> [B] -> [C] -> [D] -> None

enqueue E:  tail.next = E; tail = E
dequeue:    value = head.value; head = head.next

Why not remove from the tail? Because a singly linked list cannot step backward, so finding the node before the tail would take O(n). Adding at the tail and removing at the head are both O(1).

Python A linked-list queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The classic bug is in dequeue: when the last node leaves, head becomes None but tail still points at the removed node. Always reset tail as well, as the code does.

Attempt 4: a queue from two stacks

A famous interview question: implement a queue using only stacks. The trick uses two stacks, an inbox and an outbox.

  • enqueue pushes onto the inbox.
  • dequeue pops from the outbox. If the outbox is empty, first move everything from the inbox into the outbox, one pop and one push at a time. That move reverses the order, so the oldest item ends on top.
TEXT
enqueue 1,2,3:    inbox [1, 2, 3]     outbox []
dequeue:          outbox empty -> move all
                  inbox []            outbox [3, 2, 1]   (1 is on top)
                  pop outbox -> 1
enqueue 4:        inbox [4]           outbox [3, 2]
dequeue:          pop outbox -> 2     (no move needed)

A single dequeue can cost O(n) when it triggers a transfer, but each item is moved from inbox to outbox at most once. Over m operations the total work is O(m), so each operation is amortized O(1). See amortized analysis.

Python Queue built from two stacks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 1,000 enqueues and 1,000 dequeues the code makes 2,000 operations and moves each item exactly once, so the moves never exceed the number of enqueues.

Complexity summary

Implementation enqueue dequeue peek Notes
list with pop(0) O(1) amortized O(n) O(1) simple, slow for big queues
collections.deque O(1) O(1) O(1) the practical choice
Linked list with tail O(1) O(1) O(1) extra memory per node
Two stacks O(1) O(1) amortized O(1) amortized interview classic

Space is O(n) for n stored items in every case.

Using a queue: a simple simulation

A queue shines when work arrives faster than it can be done. Here is a tiny round-robin job runner: each job gets a fixed time slice and goes to the back of the line if it is not finished. The same pattern appears in the circular linked list lesson and in operating-system schedulers.

Python Round-robin scheduling with a queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Using list.pop(0) for big workloads. It silently turns O(n) work into O(nยฒ).
  • Forgetting the empty case: popleft() and pop() raise IndexError on empty containers.
  • Not resetting tail in a linked-list queue when the last node is removed.
  • Mixing up ends: enqueue at the back, dequeue at the front. If you push and pop at the same end you have built a stack.
  • Using queue.Queue for single-threaded code. The queue module's Queue is built for threads and adds locking overhead. For plain algorithms use deque.

Where queues appear

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which rule describes a queue?

    A queue serves items in the order they arrived, so the oldest item leaves first (FIFO).
  2. 2. Why is list.pop(0) a poor way to dequeue?

    Removing the first element of an array-backed list forces all other elements to move left.
  3. 3. Which Python tool gives O(1) adds at the back and O(1) removals at the front?

    deque supports append and popleft in constant time.
  4. 4. In a linked-list queue with head and tail pointers, which end is removed from, and why?

    A singly linked list cannot step backward, so removing at the tail would require walking the list. Removing at the head is a single pointer move.
  5. 5. Why is dequeue amortized O(1) in the two-stack queue even though one call can cost O(n)?

    An expensive transfer is paid for by the earlier cheap enqueues, since every item is transferred only one time.

Summary

  • A queue is FIFO: enqueue at the back, dequeue at the front, all in O(1) when implemented well.
  • list.pop(0) is O(n); use collections.deque with append and popleft.
  • A linked-list queue needs both head and tail; remember to clear tail when the queue empties.
  • Two stacks can simulate a queue with amortized O(1) operations.
  • Queues drive breadth-first search, schedulers and buffers.

Next: Circular Queue and Ring Buffer