DSA Deques
A deque is a double-ended queue. It adds and removes values at both ends.
Adding at both ends
append adds at the back and appendleft adds at the front.
from collections import deque
d = deque([2, 3])
d.append(4)
d.appendleft(1)
print(list(d))Removing from both ends
pop removes from the back and popleft removes from the front.
from collections import deque
d = deque([1, 2, 3, 4])
print(d.pop())
print(d.popleft())
print(list(d))Reading both ends
Index 0 reads the front and index -1 reads the back. Reading removes nothing.
from collections import deque
d = deque(["a", "b", "c"])
print(d[0])
print(d[-1])
print(list(d))Example
from collections import deque
dock = deque()
dock.append("wrap")
dock.append("ship")
print("after two appends:", list(dock))
dock.appendleft("inspect")
print("after appendleft:", list(dock))
print("served from front:", dock.popleft())
dock.appendleft("seal")
print("after one more appendleft:", list(dock))
print("cancelled from back:", dock.pop())
print("final deque:", list(dock))Key points
- Deque: a double-ended queue with work at both ends
- Use append and pop at the back of a deque
- Use appendleft and popleft at the front of a deque
- Each of the four end operations takes one step
In this example, one deque is driven from both ends. Two values arrive at the back with append. An urgent value jumps to the front with appendleft and leaves first through popleft. A late value enters at the front, and the back value leaves through pop.
Note
Reaching the middle of a deque costs a walk from an end
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Which call adds a value to the front of a deque?