Knowledge Guide
Home › DSA

Queues

Step 8 in the DSA path · 7 concepts · 6 problems

0 / 13 complete

📘 Learn Queues from zero

A queue is a FIFO container (enqueue at the back, dequeue from the front). A deque (double-ended queue) lets you push/pop from both ends in O(1), which unlocks the most powerful queue trick in interviews: the monotonic deque. The canonical problem is Max of All Subarrays of Size k (LeetCode "Sliding Window Maximum"). Trigger to reach for it: when you slide a fixed-size window across an array and need the min/max of each window, and a naive recompute would be O(n·k). A deque holding indices in decreasing-value order gives the answer in O(n) total: each index is pushed and popped at most once. We trace a = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, expected output [3, 3, 5, 5, 6, 7].

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 0 — The invariant & setup
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx   0   1   2   3   4   5   6   7
         |<-- window k=3 -->|

deque (holds INDICES, front=max): [ ]  empty
output: [ ]

We keep a deque of indices whose values are strictly decreasing front-to-back. The front always holds the index of the current window's maximum. Two rules every step: (1) pop the front if it has slid out of the window; (2) pop from the back any index whose value is ≤ the incoming value. We record an answer once the first full window is formed (i ≥ k-1 = 2).

Step 1 — i=0, push index 0
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx   0
      ^ enqueue idx 0 (val 1)

deque(idx): [0]   vals: [1]
output: []   (window not full yet)

Deque empty, so index 0 just goes to the back. Why safe: a single element is trivially the max of what we've seen. No answer yet because we have only 1 of k=3 elements.

Step 2 — i=1, evict smaller from back
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx   0   1
          ^ incoming val 3

back-pop: a[0]=1 <= 3  -> drop idx 0
deque(idx): [1]   vals: [3]
output: []

Before pushing index 1 (value 3), we pop index 0 from the back because a[0]=1 ≤ 3. Why safe: index 0 is older and smaller, so 3 will always dominate it for every future window that could contain index 0 — it can never be a max again, so we discard it permanently.

Step 3 — i=2, first window done, record max
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx   0   1   2
     [<-- window [0..2] -->]
          ^F      ^back  (val -1)

back-pop? a[1]=3 <= -1? NO -> keep
append idx 2
deque(idx): [1, 2]   vals: [3, -1]
output: [3]   <- a[front=1] = 3

Value -1 is smaller than the back's value (3), so we do not pop; we append index 2. Window [0..2] is now complete, so we emit a[front] = a[1] = 3. Why safe: -1 might still be the max of a later window once 3 leaves, so we keep it; the decreasing order is preserved.

Step 4 — i=3, window slides, keep building tail
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx       1   2   3
         [<- window [1..3] ->]
          ^F          ^back (val -3)

front in window? idx 1 >= i-k+1=1  YES
back-pop? a[2]=-1 <= -3? NO -> keep
deque(idx): [1, 2, 3]  vals: [3,-1,-3]
output: [3, 3]   <- a[front=1] = 3

Window is now [1..3]. Front index 1 is still inside (oldest allowed index is i-k+1 = 1), so it stays. Incoming -3 is smaller than the back, so we append. Emit a[1] = 3 again. Why safe: the strictly-decreasing chain 3 > -1 > -3 means each could become a max as larger elements expire.

Step 5 — i=4, front expires AND back clears
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx           2   3   4
             [<- window [2..4] ->]
                          ^ val 5

front-evict: idx 1 < i-k+1=2 -> popleft
back-pop: a[3]=-3<=5 drop, a[2]=-1<=5 drop
append idx 4
deque(idx): [4]   vals: [5]
output: [3, 3, 5]   <- a[4] = 5

Two things fire. First, front index 1 has slid out (1 < i-k+1 = 2), so we popleft it. Then the new value 5 is bigger than everything left, so we back-pop indices 3 and 2 and push 4. Emit a[4] = 5. Why safe: the front check uses index position, so a stale max is removed exactly when its window passes; and a new large value wipes all smaller older candidates because none can ever out-max it.

Step 6 — i=5, smaller value tucked behind
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx               3   4   5
                 [<- window [3..5] ->]
                          ^F   ^back(val 3)

front in window? idx 4 >= 3  YES
back-pop? a[4]=5 <= 3? NO -> keep
deque(idx): [4, 5]   vals: [5, 3]
output: [3, 3, 5, 5]   <- a[4] = 5

Window [3..5]. Front index 4 is in range; incoming 3 does not exceed the back value 5, so we append it as a backup. Emit a[4] = 5. Why safe: 3 sits behind 5 because if 5 expires later, 3 could be the next-best max — the deque is acting as a queue of future candidates in priority order.

Step 7 — i=6, big value sweeps the deque
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx                   4   5   6
                     [<- window[4..6]->]
                              ^ val 6

front in window? idx 4 >= 4 YES (no evict)
back-pop: a[5]=3<=6 drop, a[4]=5<=6 drop
append idx 6
deque(idx): [6]   vals: [6]
output: [3, 3, 5, 5, 6]   <- a[6] = 6

Value 6 beats both stored candidates, so back-pop indices 5 and 4, then push 6. The front didn't need eviction (index 4 still inside until now). Emit a[6] = 6. Why safe: a value larger than all current candidates makes every older index obsolete in O(1) amortized — each index is popped at most once across the whole run, giving O(n).

Step 8 — i=7, final window & complexity
a = [ 1,  3, -1, -3,  5,  3,  6,  7]
idx                       5   6   7
                         [<- window[5..7]->]
                                  ^ val 7
back-pop: a[6]=6 <= 7 drop
append idx 7
deque(idx): [7]   vals: [7]
output: [3, 3, 5, 5, 6, 7]  DONE

Windows: n-k+1 = 8-3+1 = 6 answers

Final element 7 evicts 6 from the back and becomes the lone max. Emit a[7] = 7. Final result [3, 3, 5, 5, 6, 7] with exactly n-k+1 = 6 windows. Complexity: O(n) time (every index enqueued and dequeued once) and O(k) space. This beats the naive O(n·k) rescan and the O(n·log k) heap approach — the monotonic deque is the gold-standard answer interviewers want.

🎯 Guided practice

  1. Easy — Reverse a Queue. Given a queue [1, 2, 3, 4] (1 at front), produce a queue with the order reversed so the front becomes 4.

    Step 1 — see the mismatch. A queue only lets you remove from the front, but reversing means the last element in must come out first. That LIFO requirement is exactly what a stack gives you. This "I need to flip FIFO order" signal → reach for a stack (or recursion, which is the call stack).

    Step 2 — drain into a stack. Dequeue everything and push onto a stack: dequeue 1→push, 2→push, 3→push, 4→push. The stack top is now 4.

    Step 3 — pour back. Pop from the stack and enqueue back into the queue: pop 4→enqueue, pop 3→enqueue, pop 2, pop 1. The queue is now [4, 3, 2, 1], front = 4. Done.

    Complexity: O(n) time, O(n) extra space. Core pattern: a stack reverses any sequence; pairing a queue with a stack lets you re-order FIFO data.

  2. Medium — Max of All Subarrays of Size k. Given nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3, output the maximum of each window: expected [3, 3, 5, 5, 6, 7].

    Step 1 — reject the naive idea. Recomputing the max of each window is O(n·k). A max-heap improves this to O(n log k). We can do O(n) with a monotonic deque — a double-ended queue that stores indices whose values are kept in decreasing order, so the front index always points at the current window's max.

    Step 2 — maintain two invariants as each index i arrives. (a) Pop expired from the front: if the front index is ≤ i - k, it has slid out of the window — remove it. (b) Pop dominated from the back: while the value at the back index is ≤ nums[i], pop it — an older element no larger than a newer one can never be a future window's max. Then push i to the back. Once i ≥ k - 1, record nums[front] as that window's answer.

    Step 3 — trace it. i=0(1): deque=[0]. i=1(3): 3≥1 so pop 0, push 1 → [1]. i=2(-1): push → [1,2]; first full window, front nums[1]=3. i=3(-3): front index 1 not expired (1 > 3-k=0); push → [1,2,3]; front=3. i=4(5): pop 3,2,1 (values -3,-1,3 all ≤5), push 4 → [4]; → 5. i=5(3): push → [4,5]; → nums[4]=5. i=6(6): pop 5,4, push 6 → [6]; → 6. i=7(7): pop 6, push 7 → [7]; → 7. Result [3,3,5,5,6,7].

    Complexity: O(n) time (each index is pushed and popped at most once → amortized O(1) per step), O(k) space. Core pattern: the monotonic-deque sliding-window template maintains a running extreme over a moving window in linear time — the canonical solution to Sliding Window Maximum (LeetCode 239), reused for sliding-window-minimum and bounded-difference window problems.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic