Queue

A queue is FIFO: enqueue at the rear and dequeue from the front of a Python list; a deque works at both ends. Underflow, and choosing a stack, queue or deque.

Key ideas

FIFO, first in first out: items join at the rear and leave from the front, in the order they joined.
With a list, enqueue is append(x) and dequeue is pop(0); dequeuing an empty queue is underflow.
The front item is q[0] and the rear item q[-1]; len(q) gives the size.
A deque (double-ended queue) allows adding and removing at both ends: insert(0, x) and pop(0) at the front, append(x) and pop() at the rear.
Used only with append() and pop(), a deque behaves as a stack; with append() and pop(0), as a queue.
A word is a palindrome if the letters popped from the two ends of a deque match every time.

Remember

Enqueue and dequeue	q = [] q.append(5) q.append(8) print(q.pop(0)) # 5 print(q) # [8]
Reaching the front	the k-th item enqueued is at the front after k − 1 dequeues
Deque ends	front: insert(0, x) and pop(0); rear: append(x) and pop()
Which structure	ticket line, print jobs, CPU tasks: queue; undo, back button, brackets: stack; both ends: deque

Watch out

Using pop() to dequeue: it takes the rear item, as a stack does.
Thinking insert(0, x) adds at the rear: it adds at the front.
Forgetting the underflow check when the queue is empty.

Worked example

What does this print?
d = [47, 46]
d.insert(0, 95)
d.insert(0, 91)
d.insert(0, 99)
d.pop()
d.append(87)
print(d)

Working: append() adds at the rear, insert(0, x) at the front; pop() removes from the rear, pop(0) from the front

Answer: [99, 91, 95, 47, 87]