LeetCode Solutions← Back to Patterns
Data StructuresEasy
Queue
FIFO structure for ordered processing — use deque for O(1) at both ends.
How it works
A Queue is a First-In-First-Out (FIFO) data structure. Its primary use in algorithms is BFS — nodes are processed in the order they were discovered, which guarantees level-by-level exploration. A Deque (double-ended queue) allows O(1) insertion and removal from both ends, enabling the Monotonic Deque pattern: maintain a deque in decreasing order for a sliding window maximum. When a new element arrives, pop all smaller elements from the back; the front always holds the maximum for the current window. This makes sliding window maximum O(n) instead of O(n·k).
Interactive Playground
Queue is empty. FIFO — first in, first out.
Speed
When to use
- BFS traversal
- Sliding window maximum with deque
- Task scheduling with order constraints
✅Tips
1Use `collections.deque` in Python or `ArrayDeque` in Java — plain lists are O(n) for front removal.
2Monotonic deque for sliding window max: remove from back elements smaller than current, remove from front elements outside the window.
3For BFS level separation, snapshot `queue.size()` at the start of each level to know when to increment depth.
4Circular queue (implemented with array + two pointers) is space-efficient for fixed-size buffers.
❌Common Mistakes
!Using list.pop(0) or ArrayList.remove(0) — these are O(n), making BFS O(n²).
!Forgetting to check that front indices in the deque are still within the window bounds.
!Confusing Queue (FIFO, for BFS) with Stack (LIFO, for DFS).
!Not clearing the queue between test cases in problems with multiple queries.
💡 Key Insight:A monotonic deque maintains order and gives O(1) min/max over a sliding window.