Stack and Queue — Concept (ধারণা)¶

দুটো বাস্তব জীবনের analogy দিয়ে শুরু করি¶

Stack: plate-এর স্তূপ¶

Cafeteria-তে পরিষ্কার plate গুলো একটা spring-লাগানো tube-এ স্তূপ করা থাকে:

নতুন plate যায় উপরে (push)।
তুমি plate নাও উপর থেকে (pop)।
তুমি যে plate-টা পাও সেটা সবসময় সবচেয়ে recently যোগ হওয়াটা — Last In, First Out (LIFO)।
নিচের plate-টা সারাদিন ওখানেই বসে থাকতে পারে। উপরের সবকিছু না সরিয়ে কেউ ওটায় পৌঁছাতে পারে না — আর structure-টা চেষ্টা করাও নিষেধ করে।

যা কিছু nest করে সেটাই plate-এর মতো আচরণ করে: তিনটা bracket খোলো, তৃতীয়টা আগে বন্ধ করতেই হবে। তিনটা function call করো, তৃতীয়টা আগে return করতেই হবে। তিনটা edit করো, undo তৃতীয়টা আগে উল্টায়।

Queue: ticket counter-এর লাইন¶

মানুষ ticket-এর জন্য লাইন ধরে:

নতুনরা যোগ দেয় পেছনে (enqueue)।
Counter serve করে সামনের জনকে (dequeue)।
যে সবচেয়ে বেশিক্ষণ অপেক্ষা করেছে সে পরে serve হয় — First In, First Out (FIFO)।
লাইন কাটা structure-টাই নিষেধ করে দেয়।

যা কিছু arrival order বা fairness-কে দাম দেয় সেটাই লাইনের মতো আচরণ করে: print job, server request, আর — সবচেয়ে গুরুত্বপূর্ণ — breadth-first search-এর frontier, যাকে কাছের জিনিস দূরের জিনিসের আগে explore করতেই হয়।

Deque: দুই দরজার লাইন¶

Deque (double-ended queue, উচ্চারণ "deck") হলো এমন একটা লাইন যার সামনে আর পেছনে দুটোতেই দরজা আছে — যেকোনো প্রান্তে O(1) add/remove। এটা stack-এর ভান করতে পারে (এক প্রান্ত ব্যবহার করো) বা queue-র (দুই প্রান্ত এক দিকে ব্যবহার করো)। চালাকি করে ব্যবহার করলে (ঢোকার জন্য এক প্রান্ত, বেরোনোর জন্য দুই প্রান্তই), এটা হয়ে ওঠে monotonic deque — এই chapter-এর সবচেয়ে শক্তিশালী pattern।

Memory-র ছবিটা¶

Dynamic array-র উপর stack¶

সবচেয়ে simple, সবচেয়ে fast stack হলো শুধু এক প্রান্তে ব্যবহার করা একটা dynamic array:

backing array (capacity 8):

+----+----+----+----+----+----+----+----+
|  4 |  9 |  2 | 17 | __ | __ | __ | __ |
+----+----+----+----+----+----+----+----+
                  ^
                 top (index 3)

push(x): write at index top+1, top += 1     -> array append, O(1) amortized
pop():   read index top, top -= 1           -> array pop-from-end, O(1)

Stack কখনো সামনে বা মাঝখান ছোঁয় না, তাই সে শুধু array-র সস্তা operation গুলোই ব্যবহার করে। এই কারণেই list.append / list.pop একটা perfect Python stack বানায়।

Queue: সাধারণ array কেন fail করে, আর deque কী করে¶

Queue remove করে FRONT থেকে — array-র দামি প্রান্ত:

naive queue on a list:
[ A | B | C | D ]   dequeue -> remove A -> SHIFT B,C,D left -> O(n) every time!

collections.deque তার বদলে item গুলো রাখে fixed-size block-এর একটা chain-এ, যেগুলো একসাথে link করা:

        block 1              block 2
   +---+---+---+---+    +---+---+---+---+
   | _ | A | B | C | -> | D | E | _ | _ |
   +---+---+---+---+    +---+---+---+---+
         ^front                  ^back

popleft(): advance the front marker — nothing shifts. O(1).
append():  write at the back marker — O(1). Both ends cheap.

দামটা: মাঝখানে কোনো fast random access নেই (প্রান্ত থেকে দূরে deque index করা O(n))। Deque হলো দুই প্রান্ত সস্তা, মাঝখান দামি — array-র ঠিক উল্টো trade-off।

Core invariants¶

Stack discipline। শুধু top-টাই ছোঁয়া যায়। pop return করে সবচেয়ে recent un-popped push-টা। প্রতি মুহূর্তে stack-এর content = "শুরু হয়েছে কিন্তু শেষ হয়নি এমন সবকিছু, নতুনতমটা উপরে।"
Queue discipline। Item গুলো ঠিক যে order-এ ঢুকেছে সেই order-এই বের হয়। কোনো reordering নেই, কখনোই না।
BFS corollary। Invariant 2-এর কারণে, তুমি যদি জিনিসগুলো nondecreasing distance order-এ enqueue করো, তাহলে nondecreasing distance order-এই dequeue-ও করো — এই একটা fact-ই কারণ যে BFS shortest path পায় (../09-graphs/)।
Monotonic stack invariant। প্রতিটা push-এর আগে প্রতিটা ভঙ্গকারীকে pop করে stack-এর value গুলো sorted রাখা হয় (ধরো, bottom থেকে top decreasing)।
Monotonic deque invariant। Front-to-back, value গুলো decreasing রাখা হয়; front-টা তাই সবসময় current window-র maximum।

কখন stack ব্যবহার করবে¶

Problem-টা nest করে: bracket, nested encoding, directory path, expression-এর parentheses।
তোমাকে সবচেয়ে recent unfinished context-এ ফিরতে হবে: undo, backtracking, recursion ছাড়া DFS।
"Most recent X that satisfies Y" ধরনের question → সাধারণত একটা monotonic stack।
Postfix/infix expression evaluate করা।

কখন queue ব্যবহার করবে¶

Arrival order মানতেই হবে: scheduler, buffer, producer/consumer।
Layer-by-layer exploration: BFS, unweighted graph/grid-এ shortest step, tree-র level-order traversal।
কোনো process সময়ের সাথে বাইরের দিকে ছড়ায় (পচন, আগুন, সংক্রমণ — multi-source BFS)।

কখন এগুলো ব্যবহার করবে NA¶

তোমার মাঝখানে random access বা search দরকার → array বা hash map; এই structure গুলো ইচ্ছে করেই মাঝখান নিষেধ করে।
Arbitrary insert আর removal-এর সাথে minimum/maximum দরকার → একটা heap (priority queue) — queue serve করে arrival ধরে, heap serve করে priority ধরে।
Python-specific: কখনো list.pop(0) দিয়ে queue simulate কোরো না; সেটা প্রতি operation-এ O(n)। collections.deque ব্যবহার করো।

Complexity table¶

Operation	Stack (on list)	Queue (on deque)	Deque
push / append (back)	O(1) amortized	O(1)	O(1)
pop (top / back)	O(1)	—	O(1)
dequeue / popleft (front)	—	O(1)	O(1)
peek front/top	O(1)	O(1)	O(1)
search / index in middle	O(n)	O(n)	O(n)
size / is-empty	O(1)	O(1)	O(1)

ছোট ছোট snippet, dry run সহ¶

Snippet 1 — stack আসলে এক প্রান্তে ব্যবহার করা একটা list¶

stack = []
stack.append('f')      # call f
stack.append('g')      # f calls g
stack.append('h')      # g calls h
print(stack.pop())     # h finishes first  -> 'h'
print(stack.pop())     # then g            -> 'g'

Dry run:

push f:  [f]
push g:  [f, g]
push h:  [f, g, h]      <- top is the right end
pop:     returns h, stack=[f, g]     LIFO: last in, first out
pop:     returns g, stack=[f]

Snippet 2 — queue-কে deque হতেই হবে¶

from collections import deque

q = deque()
q.append('job1')       # enqueue at the back
q.append('job2')
q.append('job3')
print(q.popleft())     # serve the front -> 'job1'

Dry run:

enqueue job1: front->[job1]<-back
enqueue job2: front->[job1, job2]<-back
enqueue job3: front->[job1, job2, job3]<-back
popleft:      returns job1 (the OLDEST), q=[job2, job3]    FIFO

Snippet 3 — আট লাইনে bracket matching¶

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    st = []
    for ch in s:
        if ch in '([{':
            st.append(ch)
        elif not st or st.pop() != pairs[ch]:
            return False          # underflow or wrong partner
    return not st                 # leftovers also mean failure

"(]"-এর উপর dry run:

ch='(' : push        st=['(']
ch=']' : pop -> '('  but pairs[']'] = '['   mismatch -> False
(three failure modes: pop on empty, wrong partner, leftovers at end)

Snippet 4 — queue-ই BFS-এর layer order guarantee করে¶

from collections import deque

q = deque([("start", 0)])     # (node, distance)
seen = {"start"}
while q:
    node, d = q.popleft()     # ALWAYS the smallest distance in the queue
    for nb in neighbors(node):
        if nb not in seen:
            seen.add(nb)
            q.append((nb, d + 1))

Dry run-এর shape:

queue over time:  [start(0)]
                  [a(1), b(1)]          start's neighbors
                  [b(1), c(2), d(2)]    a's neighbors join BEHIND b
                  [c(2), d(2), ...]
distance values leave the queue in order 0,1,1,2,2,... — never decreasing.
That ordering IS the shortest-path proof. Full story in ../09-graphs/.

মনে রাখার মতো এক বাক্য¶

Stack উত্তর দেয় "আমি সবচেয়ে recently কী শুরু করেছিলাম?", queue উত্তর দেয় "কে সবচেয়ে বেশিক্ষণ অপেক্ষা করেছে?" — আর ভুলটা বেছে নিলে সঠিক-দেখতে code ভুল উত্তর দেয়, কারণ processing-এর order-টাই হলো algorithm।

এরপর: push, pop আর monotonic deque-কে নড়তে দেখো visual-explanation.md-তে।