AI Hints
Home›DSA in Python Tutorial›Stacks and Queues
DSA in Python · Lesson 33 of 132

Queues

First in, first out.

⏱ 2 min read▶ Video at 38:19🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A queue is like a line at a shop. People join at the back, and are served from the front. First in, first out. Printers, customer support tickets, and messages between programs all use queues.

Queues
From the video: Queues
  • A line at a shop
  • Join at the back, leave from the front
  • Printers, tickets, messages

Use deque, not list

You could use a list as a queue, but pop at zero is O of N, because every item shifts. The collections module has deque, a double ended queue. Append adds to the back, and pop left removes from the front, both in O of one. Run it. Customers are served in the order they arrived.

queue.pypython
from collections import deque

line = deque()
for name in ["Priya", "Sam", "Jo"]:
    line.append(name)
    print(name, "joins:", list(line))

while line:
    print("serving", line.popleft())
Output
Priya joins: ['Priya']
Sam joins: ['Priya', 'Sam']
Jo joins: ['Priya', 'Sam', 'Jo']
serving Priya
serving Sam
serving Jo

How much faster?

Let's measure. We fill a list and a deque with one hundred thousand items, and then empty each one from the front. Run it. The deque empties almost instantly. The list is much slower, because every pop at zero shifts every remaining item.

queue_speed.pypython
import time
from collections import deque
n = 100_000

items = list(range(n))
start = time.perf_counter()
while items:
    items.pop(0)
print(f"list.pop(0):     {time.perf_counter() - start:.3f} s")

q = deque(range(n))
start = time.perf_counter()
while q:
    q.popleft()
print(f"deque.popleft(): {time.perf_counter() - start:.3f} s")
Output
list.pop(0):     0.798 s
deque.popleft(): 0.003 s

Summary

A queue is first in, first out. Use deque, with append and pop left, for O of one at both ends. Next, a new structure. The linked list.

Key takeaways
  • First in, first out
  • deque.append / popleft
  • Both O(1)
Next up: Linked Lists — nodes and pointers