Queue Basics
Stacks & Queues: lesson 3 of 9
First one in is the first one out.
Lesson 3 of 9 · 4 min
Queue Basics
Step 1 of 8
deque costO(1)list shifts0
deque — popleft()
front
back
job1
job2
job3
job4
list — pop(0)
job1
job2
job3
job4
all shift
Three print jobs, stored two ways. Items join at the back and must leave from the front.
The Idea
A queue is open at both ends. Items join at the back and leave from the front, so the oldest one is always served first. Reach for collections.deque: removing the front is O(1) there, while list.pop(0) costs O(n) because everything behind it shifts down a slot.
Real-World Example
A shared office printer. Three people hit print in the same minute and the machine works through the documents in the order they arrived. A fourth job sent now waits behind all of them, however urgent its owner feels.
The Code
from collections import deque
q = deque()
q.append("job1") # enqueue at the back -> O(1)
q.append("job2")
q.append("job3")
print(q[0]) # "job1" peek at the front
print(q.popleft()) # "job1" the oldest leaves first
print(q.popleft()) # "job2"
print(list(q)) # ["job3"]
# a plain list would need pop(0) here, which is O(n)Your turn
Fill in the blank.
from collections import deque
q = deque(["a", "b", "c"])
# take out the item that arrived first
first = q.___()Mini quiz
1 / 3