Stacks and Queues

Queue Enqueue/Dequeue

Enqueue values at the back and dequeue them from the front in first-in, first-out order.

Algorithm

Basic Implementation

basic.py 
from collections import deque

queue = deque()
for value in [10, 20, 30]:
    queue.append(value)
removed = []
while queue:
    removed.append(queue.popleft())
print(" -> ".join(str(x) for x in removed))

The queue keeps the oldest value at the front and adds new values at the back.

Step 1 - Enqueue 10, 20, 30

New values join at the back. The oldest value, 10, stays at the front.

Queue after three enqueues: front 10, then 20, then back 30.nextnext10front2030back

Step 2 - Dequeue removes 10

Removing from the front returns 10 and makes 20 the new front.

After one dequeue: removed is 10; front moves to 20.next10removed20front30back

Complexity

  • Time: O(1) per operation with a real queue
  • Space: O(n)

Implementation notes

  • Python uses collections.deque for the queue, not a list with pop(0). queue.append(value) mutates the right end, and queue.popleft() removes and returns the oldest value from the left in O(1) time.
  • The deque and the removed list are separate containers. Each removed.append(queue.popleft()) transfers the returned int reference into removed while shrinking the deque.
  • The visible containers are the deque and the removed list; normal Python GC owns them once no references remain. The trace shows the queue move from [] to [10, 20, 30], then drain into removed.
front The front is the oldest value still waiting in the queue.
FIFO A queue removes values in first-in, first-out order.