Queues: first in, first out

A queue is the other end. Add at the back, remove from the front, like every queue you have stood in.

enqueue(1,2,3)          dequeue() -> 1

front [ 1 | 2 | 3 ] back        [ 2 | 3 ]

The bug you will write first

queue = []
queue.append(x)     # O(1), fine
queue.pop(0)        # O(n), and this is the bug

pop(0) removes from the front of a Python list, which shifts every remaining element left. In a loop over n items that is O(n²).

from collections import deque
queue = deque()
queue.append(x)     # O(1)
queue.popleft()     # O(1)

A deque is built for both ends. Java's equivalent is ArrayDeque.

The circular queue

Implementing a queue on a fixed array wastes space if front and back only move forward: after enough operations both reach the end while the start sits empty.

A circular queue wraps the indices with modulo:

rear = (rear + 1) % capacity

Which raises the question of how to tell full from empty, since both give front == rear. Either keep a count, or leave one slot always unused. Every textbook picks one; say which you chose.

Priority queue

Removes the highest priority item rather than the oldest. Built on a heap, so insert and remove are O(log n) rather than O(1). Hospital triage rather than a post office.

Where queues appear

Anything processed in arrival order: print jobs, the ready queue in a scheduler, request handling. And breadth-first search, where the queue is what makes the traversal explore level by level.