Stack and Queue — Frame-by-Frame Visuals¶
Stack আঁকা হয় খাড়াভাবে (top = খোলা প্রান্ত)। Queue আর deque আঁকা হয় আনুভূমিকভাবে (front বাঁয়ে)। প্রতিটা sequence frame by frame follow করো আর পরের frame-টা পড়ার আগে নিজে predict করো।
1. Stack: push আর pop¶
Push 4, push 9, push 2, তারপর দুবার pop।
FRAME 0 FRAME 1 FRAME 2 FRAME 3 FRAME 4 FRAME 5
(empty) push(4) push(9) push(2) pop() -> 2 pop() -> 9
| | | | | | | 2 | <top | | | |
| | | | | 9 | <top | 9 | | 9 | <top | |
| | | 4 | <top | 4 | | 4 | | 4 | | 4 | <top
+---+ +---+ +---+ +---+ +---+ +---+
LIFO in action: 2 entered last, left first. 4 entered first, still waiting.
2. Nested bracket track করা stack — "( [ ] ) ("¶
Stack ধরে রাখে প্রতিটা bracket যেটা খোলা হয়েছে কিন্তু এখনো বন্ধ হয়নি।
read '(' : push read '[' : push read ']' : top is '[' — match! pop
| | | [ | <top | |
| ( | <top | ( | | ( | <top
+---+ +---+ +---+
read ')' : top is '(' — match! pop read '(' : push
| | | ( | <top
| | (empty — all closed so far) +---+
+---+
END OF INPUT: stack NOT empty -> invalid. A '(' was never closed.
(the three failure modes: pop-on-empty, mismatched pop, leftovers at end)
3. Queue: enqueue আর dequeue¶
A, B, C enqueue করো; দুবার dequeue করো।
FRAME 0: front -> [ ] <- back (empty)
FRAME 1: front -> [ A ] <- back enqueue A
FRAME 2: front -> [ A B ] <- back enqueue B (joins BEHIND A)
FRAME 3: front -> [ A B C ] <- back enqueue C
FRAME 4: front -> [ B C ] <- back dequeue -> A (oldest leaves)
FRAME 5: front -> [ C ] <- back dequeue -> B
FIFO: leave-order A,B,C equals arrival-order A,B,C. Always.
4. Python list কেন বাজে queue বানায়¶
একটা list-এ pop(0) দিয়ে dequeue — shifting-টা দেখো।
list queue: [ A | B | C | D ]
pop(0): A leaves... but the array cannot have a hole at the front:
[ _ | B | C | D ] -> shift B,C,D left -> [ B | C | D ]
3 moves for 4 items. n items -> O(n) per dequeue. O(n^2) total!
deque: blocks + a front marker:
[ A | B | C | D ]
^front
popleft(): just slide the marker: [ x | B | C | D ]
^front 0 moves. O(1).
5. BFS frontier: queue একটা ring খায়, পরেরটা গজায়¶
S থেকে grid BFS; সংখ্যা = যে step-এ cell-টায় পৌঁছানো হলো।
grid: queue over time (front on the left):
. . . . [S] dequeue S, enqueue its neighbors
. S . . [a1, b1] (the "distance-1 ring")
. . . . [b1, c2, d2] dequeue a1, its new neighbors go BEHIND
[c2, d2, e2] dequeue b1 ...
ring picture: [d2, e2, ...]
2 2 2
2 1 2 all 1s leave the queue before ANY 2 — the queue physically
2 1 2 cannot reorder them. Layer-by-layer is guaranteed, which is
2 2 2 exactly why BFS distances are shortest. (Details: ../09-graphs/)
6. Monotonic stack: Next Greater Element¶
[2, 1, 5, 3]-এর জন্য, প্রতিটা element-এর ডানদিকে next greater খোঁজো। Stack ধরে রাখে যে index গুলোর answer এখনো unknown, value গুলো bottom থেকে top decreasing।
scan i=0 (val 2): stack empty -> push 0 stack: [0] (vals: 2)
scan i=1 (val 1): 1 < 2, no one resolved -> push stack: [0,1] (vals: 2,1)
scan i=2 (val 5): 5 > 1 -> POP 1: ans[1]=5
5 > 2 -> POP 0: ans[0]=5
push 2 stack: [2] (vals: 5)
scan i=3 (val 3): 3 < 5 -> push stack: [2,3] (vals: 5,3)
end: leftovers 2,3 have no greater -> ans = [5, 5, -1, -1]
Why O(n): every index is pushed once and popped at most once.
The nested-looking while loop cannot exceed n pops TOTAL.
7. Monotonic deque: Sliding Window Maximum (chapter-এর centerpiece)¶
Array [1, 3, -1, -3, 5, 3, 6, 7], window size k = 3। Deque-টা রাখে index; তাদের value গুলো front → back decreasing রাখা হয়, তাই front-টাই সবসময় window-র max।
প্রতিটা নতুন element x-এর জন্য rule: পেছন থেকে eject করো প্রতিটা index যার value ≤ x (এরা এখন useless — x একইসাথে নতুন আর বড়), front window থেকে বেরিয়ে গেলে সেটাও eject করো, তারপর front-ই হলো answer।
i=0 v=1 : deque [1] window not full yet
i=1 v=3 : 3 beats 1 -> eject 1; deque [3] 1 can never be a max again
i=2 v=-1: -1 < 3 -> keep; deque [3,-1] window [1,3,-1] MAX=3 (front)
i=3 v=-3: keep; deque [3,-1,-3] window [3,-1,-3] MAX=3
i=4 v=5 : front (the 3 at index 1) slid OUT of the window -> eject front;
5 beats -3 and -1 -> eject both from the back
deque [5] window [-1,-3,5] MAX=5
i=5 v=3 : keep; deque [5,3] window [-3,5,3] MAX=5
i=6 v=6 : 6 beats 3,5 -> eject both; deque [6] window [5,3,6] MAX=6
i=7 v=7 : 7 beats 6 -> eject; deque [7] window [3,6,7] MAX=7
answers: [3, 3, 5, 5, 6, 7]
দুটো প্রান্ত আলাদা আলাদা কাজ করে:
eject smaller-or-equal (useless) eject expired (slid out of window)
| |
v v
new element -> [BACK ... decreasing values ... FRONT] -> current max
কেন O(n): প্রতিটা index deque-তে একবার ঢোকে আর একবার বের হয় (কোনো না কোনো প্রান্ত থেকে)। আটটা element, আটটা entry, বড়জোর আটটা exit — কোনো একটা step যত নাটকীয়ই দেখাক না কেন।
Full pattern write-up (trigger word, thinking tweak, inheritance) আছে patterns.md-এর Pattern 5-এ।
এই frame গুলো কীভাবে study করবে¶
- Sequence 6 আর 7 হলো high-value গুলো: দুটো table-ই খালি পাতা থেকে reproduce করো।
- Sequence 7-এর জন্য, প্রতিটা ejection মুখে বলো: "তুমি নতুন আসা element-এর চেয়ে ছোট আর তার চেয়ে পুরনো — তুমি কখনো answer হতে পারবে না — বেরোও।"
- তারপর পড়ো operations.md cost আর pitfall-এর জন্য, আর patterns.md named technique-এর জন্য।