# Stack and Queue — Core Operations

আমরা stack-কে ধরি এক প্রান্তে ব্যবহার করা একটা Python `list` হিসেবে, আর queue/deque-কে `collections.deque` হিসেবে। প্রতিটা operation-এ: এটা কী করে, খরচটা যা সেটা কেন, একটা before/after ছবি, code, আর pitfall।

---

## 1. Stack push — `stack.append(x)`

**কী:** `x`-কে stack-এর উপরে বসাও।

**কেন O(1) amortized:** এটা হুবহু শেষে একটা dynamic-array append — spare room-এ লেখো; শুধু কালেভদ্রে doubling copy হয় (দেখো [../02-arrays-and-strings/operations.md](../02-arrays-and-strings/operations.md))।

```text
before:  | 9 |          after push(2):  | 2 | <top
         | 4 | <top                     | 9 |
         +---+                          | 4 |
                                        +---+
```

```python
stack = [4, 9]
stack.append(2)      # [4, 9, 2] — rightmost element is the top
```

**Pitfalls:** "top"-এর জন্য একটাই convention বেছে নাও (এখানে: list-এর ডান প্রান্ত) আর কখনো মেশাবে না। `insert(0, x)` দিয়ে push করা logically কাজ করে কিন্তু O(n) — একটা নীরব performance bug।

## 2. Stack pop — `stack.pop()`

**কী:** top element-টা সরাও আর return করো।

**কেন O(1):** array-র শেষ element সরালে কিছুই shift হয় না।

```text
before:  | 2 | <top     after pop():    | 9 | <top      returns 2
         | 9 |                          | 4 |
         | 4 |                          +---+
         +---+
```

```python
top = stack.pop()    # 2; stack is now [4, 9]
```

**Pitfalls:** খালি list-এ `pop()` করলে `IndexError` ওঠে। `if stack:` দিয়ে guard করো, অথবা algorithm এমনভাবে design করো যাতে ওই point-এ emptiness অসম্ভব হয় (আর comment-এ লেখো কেন)।

## 3. Stack peek — `stack[-1]`

**কী:** না সরিয়ে top-টা দেখো।

**কেন O(1):** জানা position-এ index access।

```python
if stack:
    top = stack[-1]      # read, don't remove
```

**Pitfalls:** খালি stack-এ peek করলেও `IndexError` ওঠে। Monotonic-stack loop করে `while stack and stack[-1] < x:` — ওই `stack and` guard-টা load-bearing।

## 4. Enqueue — deque-তে `q.append(x)`

**কী:** লাইনের পেছনে যোগ দাও।

**কেন O(1):** deque পেছনের block-এর খালি slot-এ লেখে; কোনো shifting নেই, পুরো structure-এর কোনো reallocation নেই।

```text
before: front -> [ A  B ] <- back       after append(C):
        front -> [ A  B  C ] <- back
```

```python
from collections import deque
q = deque(['A', 'B'])
q.append('C')
```

**Pitfalls:** পেছনে কোনোটাই না — বিপদটা সামনে (পরের operation)।

## 5. Dequeue — `q.popleft()`

**কী:** লাইনের সামনের জনকে serve করো আর সরাও।

**কেন O(1):** deque তার front marker-টা front block-এর ভেতরে এগিয়ে নেয়। তুলনা করো: `list.pop(0)`-কে বাকি প্রতিটা element বাঁয়ে shift করতে হয় — O(n)।

```text
before: front -> [ A  B  C ] <- back    after popleft():
        returns A;  front -> [ B  C ] <- back
```

```python
first = q.popleft()    # 'A'
```

**Pitfalls:** BFS loop-এ `list.pop(0)` ব্যবহার করাই হলো THE classic Python ভুল — program-টা correct কিন্তু চুপচাপ O(n^2), বড় input-এ time out করে। খালি deque-তে `popleft` করলে `IndexError` ওঠে; BFS loop সেটা এড়ায় `while q:` দিয়ে।

## 6. Peek front / back — `q[0]`, `q[-1]`

**কী:** না সরিয়ে যেকোনো প্রান্ত পরীক্ষা করো।

**কেন O(1):** deque দুই প্রান্তের block-এরই direct reference ধরে রাখে।

```python
front = q[0]
back = q[-1]
```

**Pitfalls:** deque-র *মাঝখানে* index করা (`q[k]`) O(n) — deque শুধু প্রান্তের জন্য optimized। মাঝখানে fast access দরকার হলে আসলে তোমার দরকার ছিল একটা list।

## 7. Deque back-pop — `q.pop()`

**কী:** পেছন থেকে সরাও — যে operation একটা queue-কে deque বানায়।

**কেন O(1):** `popleft`-এর symmetric।

```python
last = q.pop()
```

**Pitfalls:** monotonic-deque code-এ তুমি `pop()` (useless পেছনের element eject করতে) আর `popleft()` (expired সামনের element eject করতে) — দুটোই ডাকবে। এগুলো গুলিয়ে ফেললে এমন ভুল answer আসে যেগুলো ছোট test-এ *plausible দেখায়* — সন্দেহ হলেই [visual-explanation.md](visual-explanation.md) section 7-এর centerpiece table-টা আবার trace করো।

## 8. Size আর emptiness — `len(q)`, `not q`

**কী:** কয়টা item আছে; খালি কিনা।

**কেন O(1):** দুটো structure-ই একটা size counter maintain করে।

```python
while q:               # idiomatic "while not empty"
    item = q.popleft()
```

**Pitfalls:** `while len(q) > 0:` কাজ করে কিন্তু `while q:`-ই idiom। Loop-এর শুরুতে `n = len(q)` cache করা *level-by-level* BFS-এর জন্য একদম ঠিক (প্রতি outer iteration-এ একটা full layer process করো) — কিন্তু পুরো queue শেষ করতে চাইলে ভুল।

## 9. Bounded deque — `deque(maxlen=k)`

**কী:** এমন একটা deque যেটা বড়জোর k-টা item ধরে; ভরা অবস্থায় add করলে উল্টো প্রান্ত থেকে চুপচাপ ফেলে দেয়।

**কেন matter করে:** "last k events" buffer-এর জন্য perfect (recent log, moving average)।

```python
recent = deque(maxlen=3)
for x in [1, 2, 3, 4]:
    recent.append(x)
# recent is deque([2, 3, 4]) — the 1 fell off the front automatically
```

**Pitfalls:** চুপচাপ ফেলে দেওয়াটা এখানে feature, আর যেখানে তুমি আশা করোনি সেখানে bug। Sliding-window-maximum-এর জন্য `maxlen` ব্যবহার কোরো না — monotonic deque-কে নিজের eviction নিজে control করতেই হবে (front eviction নির্ভর করে *index*-এর উপর, count-এর উপর না)।

## 10. MinStack — twin stack দিয়ে O(1) minimum

**কী:** এমন একটা stack যেটা "current minimum কত?"-এর উত্তরও O(1)-এ দেয়।

**কেন O(1):** মূল stack-এর পাশে একটা দ্বিতীয় stack রাখো, যার top সবসময় *মূল stack-এ এই মুহূর্তে থাকা সবকিছুর minimum*। প্রতিটা push-এর সাথে twin-এ push করো `min(x, current_min)`; দুটো একসাথে pop করো। Minimum-এর history আপনা থেকেই সংরক্ষিত থাকে।

```text
push 5, 2, 7:    main: [5, 2, 7]       mins: [5, 2, 2]
                                              ^ top of mins = current min = 2
pop (7):         main: [5, 2]          mins: [5, 2]    min still 2
pop (2):         main: [5]             mins: [5]       min back to 5 — for free
```

```python
# full class in implementation.py
self.stack.append(x)
self.mins.append(min(x, self.mins[-1] if self.mins else x))
```

**Pitfalls:** শুধু একটা `current_min` variable রাখলে minimum-টা pop হওয়া মাত্র fail করে — history ছাড়া *আগের* minimum-টা ফিরে পাওয়া যায় না। Twin stack-ই হলো সেই history।

---

## Big-O summary table

| Operation | Stack (`list`) | Queue (`deque`) | Deque | Wrong tool (`list` as queue) |
| --- | --- | --- | --- | --- |
| push / append back | O(1) am. | O(1) | O(1) | O(1) |
| pop top / back | O(1) | — | O(1) | O(1) |
| dequeue / pop front | — | O(1) | O(1) | O(n)  ← the trap |
| peek (either end) | O(1) | O(1) | O(1) | O(1) |
| index middle | O(1) | O(n) | O(n) | O(1) |
| search by value | O(n) | O(n) | O(n) | O(n) |
| size / empty check | O(1) | O(1) | O(1) | O(1) |
| MinStack get_min | O(1) | — | — | — |

Table-টা column ধরে পড়ো: প্রতিটা structure ঠিক সেখানেই সস্তা যেখানে তার discipline থাকে, আর সেখানেই দামি যেখানে সে access নিষেধ করে। Structure বেছে নেওয়া = কোন column-এর cost তুমি দেবে সেটা বেছে নেওয়া।

এরপর: named technique গুলো — full Sliding Window Maximum walkthrough সহ — [patterns.md](./patterns.md)-তে।