A queue follows the "first come, first served" (FIFO) rule: items are added at the end and removed from the front. It looks simple, but a naive implementation pays a hidden O(n). In this lesson we build three correct implementations: on a list, on a linked list and on a ring buffer.
Operations
The core operations of the queue ADT are enqueue(x), dequeue(), peek() and is_empty(). The goal is O(1) for each. Unlike a stack, adding and removing happen at opposite ends, so one end of a list is not enough.
Why list.pop(0) is bad
A Python list is an array (array memory). Removing the first item shifts the other n - 1 items one slot to the left. Below is a model that counts the shifts by hand, with no timer; n calls of pop(0) add up to O(n²). For the cost of built-in operations see this table.
def pop_front_moves(items):
moves = 0
for i in range(1, len(items)):
items[i - 1] = items[i]
moves += 1
items.pop()
return moves
for n in (10, 100, 1000):
print(n, pop_front_moves(list(range(n))))10 9
100 99
1000 999