After this lesson, you will be able to: Implement queues with an array and a linked list, understand FIFO, and recognize deques, priority queues, and their real uses in job queues and BFS.
A queue is the mirror image of a stack: first in, first out. It models anything that processes things in arrival order, from print jobs to message queues to breadth-first search.
A queue supports enqueue (add to the back) and dequeue (remove from the front). The first thing you added is the first thing you remove, like a line at a checkout. Done right, both operations are O(1). The challenge is that a naive array implementation makes dequeue O(n) because removing the front shifts everything, so queues need a smarter backing structure.
Use a deque (double-ended queue), which is O(1) at both ends.
# WRONG: list.pop(0) is O(n) because every element shifts leftq = [1, 2, 3]q.append(4) # O(1)first = q.pop(0) # O(n) <-- slow# RIGHT: collections.deque is O(1) at both endsfrom collections import dequeq = deque([1, 2, 3])q.append(4) # enqueue, O(1)first = q.popleft() # dequeue, O(1)# JavaScript has no built-in deque; for big queues use two stacks# or a ring buffer, NOT array.shift() (which is O(n)).
A deque (double-ended queue) lets you add and remove from both ends, so it can act as a stack or a queue. A priority queue is different: instead of FIFO, it always removes the highest-priority element next, regardless of arrival order. Priority queues are almost always implemented with a heap, which you will learn two lessons from now. They power task schedulers, Dijkstra's shortest-path algorithm, and anything that says 'handle the most urgent item first.'
A classic interview question that proves you understand both structures.
1. Keep two stacks: inbox and outbox.
2. enqueue(x): push x onto inbox.
3. dequeue(): if outbox is empty, pop everything from inbox into outbox (this reverses the order), then pop from outbox.
4. Convince yourself each element moves at most once between stacks, so dequeue is amortized O(1).
5. Test with enqueue 1,2,3 then dequeue three times; expect 1,2,3.
Using list.pop(0) or array.shift() for a queue and turning an O(n) algorithm into O(n squared) (use a deque). Confusing a queue with a priority queue (FIFO vs by-priority). Forgetting that a priority queue needs a heap to be efficient. In the two-stacks trick, refilling the outbox while it still has items, which breaks the order (only refill when outbox is empty).
Sign in and purchase access to unlock this lesson.