DSA · Chapter 17 of 40
Queues
A queue is a FIFO (first in, first out) structure with enqueue at the rear and dequeue at the front, both O(1) when implemented with a linked list or a deque.
Queues model waiting lines, task scheduling and breadth-first search.
Circular queue
An array-based queue wraps front and rear indices around with modulo arithmetic so no memory is wasted after dequeues.
Deque
A double-ended queue supports push and pop at both ends in O(1) and is used for sliding-window maximum problems.
Example 1 (python)
from collections import deque
q = deque()
q.append('a')
q.append('b')
print(q.popleft())
print(list(q))Output
a
['b']deque gives O(1) operations at both ends.
Example 2 (python)
def max_window(nums, k):
from collections import deque
dq, res = deque(), []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
res.append(nums[dq[0]])
return res
print(max_window([1, 3, -1, -3, 5], 3))Output
[3, 3, 5]A monotonic deque gives sliding-window maximum in O(n).
Key points
- A queue is FIFO with O(1) enqueue and dequeue.
- BFS uses a queue; DFS uses a stack.
- Circular queues reuse array space via modulo.
- Deques support both ends in O(1).
💡 Note: In Python never use list.pop(0) for a queue — it is O(n). Use collections.deque.