# 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:

```text
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-র দামি প্রান্ত:

```text
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 করা:

```text
        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

1. **Stack discipline।** শুধু top-টাই ছোঁয়া যায়। `pop` return করে সবচেয়ে recent un-popped `push`-টা। প্রতি মুহূর্তে stack-এর content = "শুরু হয়েছে কিন্তু শেষ হয়নি এমন সবকিছু, নতুনতমটা উপরে।"
2. **Queue discipline।** Item গুলো ঠিক যে order-এ ঢুকেছে সেই order-এই বের হয়। কোনো reordering নেই, কখনোই না।
3. **BFS corollary।** Invariant 2-এর কারণে, তুমি যদি জিনিসগুলো nondecreasing distance order-এ enqueue করো, তাহলে nondecreasing distance order-এই *dequeue*-ও করো — এই একটা fact-ই কারণ যে BFS shortest path পায় ([../09-graphs/](../09-graphs/README.md))।
4. **Monotonic stack invariant।** প্রতিটা push-এর আগে প্রতিটা ভঙ্গকারীকে pop করে stack-এর value গুলো sorted রাখা হয় (ধরো, bottom থেকে top decreasing)।
5. **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

```python
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:

```text
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 হতেই হবে

```python
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:

```text
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

```python
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:

```text
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 করে

```python
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:

```text
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](./visual-explanation.md)-তে।