Plain queue for BFS, deque for sliding windows and 0-1 BFS, priority queue for weighted graphs and top-K problems.
QUEUE TYPE — DECISION GUIDE
─────────────────────────────
PLAIN QUEUE (collections.deque):
FIFO: first in, first out
□ BFS traversal (unweighted shortest path)
□ Level-order tree traversal
□ Rotten oranges, walls and gates
Time: O(1) append/popleft
DEQUE (double-ended queue):
Both ends: appendleft, pop, append, popleft
□ Sliding window maximum/minimum
□ 0-1 BFS (edges with weight 0 or 1)
□ Palindrome check from both ends
Time: O(1) both ends
PRIORITY QUEUE (heapq):
Always yields smallest (min-heap)
□ Dijkstra's algorithm (weighted shortest path)
□ Merge K sorted lists
□ Top-K / Kth largest
□ Median from data stream (two heaps)
□ Task scheduler
Time: O(log n) push/pop
DECISION:
Unweighted shortest path? → plain queue (BFS)
Weighted shortest path? → priority queue (Dijkstra)
0-1 weights? → deque (0-1 BFS)
Sliding window extremes? → deque (monotonic)
"Top K" / "Kth smallest"? → priority queue
Need both ends? → deque