# Stack and Queue — কোন দিক দিয়ে ঢোকে, কোন দিক দিয়ে বের হয়

Stack-এ শেষের জিনিস আগে বের হয় (**LIFO**)। Queue-তে আগের জিনিস আগে বের হয় (**FIFO**)। এই পার্থক্য মনে রাখলে bracket মিলানো, BFS ও sliding window-তে কোনটি লাগবে বোঝা সহজ হয়।

## 1. Stack: একই প্রান্তে push ও pop

প্রতিটি stack-এর উপরের বাক্সটি `top`। নতুন মান সেখানেই বসে, pop-ও সেখান থেকেই হয়।

```dsa
kind: stack
title: "4, 9, 2 ঢোকালে প্রথমে বের হবে 2"
steps:
  - label: "শুরু"
    values: []
  - label: "push(4)"
    values: [4]
    active: [0]
  - label: "push(9)"
    values: [4, 9]
    active: [1]
  - label: "push(2)"
    values: [4, 9, 2]
    active: [2]
  - label: "pop() → 2"
    values: [4, 9]
    note: "সবচেয়ে শেষে ঢোকা 2 বের হলো।"
  - label: "pop() → 9"
    values: [4]
    note: "4 প্রথমে ঢুকেছিল; সেটি এখনও আছে।"
```

## 2. Bracket মিলানো: খোলা কিন্তু বন্ধ হয়নি—এমনগুলো রাখো

Input `([])(`। Closing bracket এলে stack-এর top-এর সঙ্গে মিলিয়ে pop করি।

```dsa
kind: stack
title: "শেষের খোলা bracket-এর জন্য input অবৈধ"
steps:
  - label: "( পড়ে push"
    values: ["("]
    active: [0]
  - label: "[ পড়ে push"
    values: ["(", "["]
    active: [1]
  - label: "] পড়ে [ মেলাও ও pop"
    values: ["("]
  - label: ") পড়ে ( মেলাও ও pop"
    values: []
    note: "এ পর্যন্ত সব bracket মিলে গেছে।"
  - label: "শেষের ( পড়ে push"
    values: ["("]
    active: [0]
    note: "Input শেষ, stack খালি নয়: এই bracket আর বন্ধ হয়নি।"
```

অবৈধ হওয়ার তিনটি কারণ: খালি stack-এ closing bracket, top-এর সঙ্গে না-মেলা closing bracket, অথবা শেষে কিছু opening bracket থেকে যাওয়া।

## 3. Queue: পেছনে যোগ, সামনে থেকে বের

```dsa
kind: queue
title: "A, B, C ঢোকালে বের হওয়ার ক্রমও A, B, C"
steps:
  - label: "শুরু"
    values: []
  - label: "enqueue A"
    values: [A]
    active: [0]
  - label: "enqueue B"
    values: [A, B]
    active: [1]
  - label: "enqueue C"
    values: [A, B, C]
    active: [2]
  - label: "dequeue → A"
    values: [B, C]
  - label: "dequeue → B"
    values: [C]
```

Python-এ queue বানাতে `collections.deque` সুবিধাজনক। `list.pop(0)` করলে বাকি reference-গুলো বাঁয়ে সরাতে হয়।

| Operation | `[A, B, C, D]` থেকে A বাদ দিতে কী হয় | খরচ |
| --- | --- | --- |
| `list.pop(0)` | B, C, D-এর তিনটি reference সরাতে হয় | O(n) |
| `deque.popleft()` | সামনে থেকে একটি element বাদ যায়; বাকি সব element সরাতে হয় না | O(1) |

List দিয়ে nটি dequeue করলে মোট খরচ **O(n²)** হতে পারে। Deque-এর এই operation-গুলোর মোট খরচ **O(n)**।

## 4. BFS: আগের দূরত্বের কাজ আগে শেষ হয়

S থেকে শুরু করি। প্রতিবেশীদের বর্ণানুক্রমে queue-তে ঢোকাই। **ঢোকানোর সময়ই visited** করি, যাতে একই node দুবার না ঢোকে।

```mermaid
flowchart TD
  S["S · দূরত্ব 0"] --> A["A · দূরত্ব 1"]
  S --> B["B · দূরত্ব 1"]
  A --> C["C · দূরত্ব 2"]
  A --> D["D · দূরত্ব 2"]
  B --> E["E · দূরত্ব 2"]
```

| ধাপ | সামনে থেকে বের হলো | নতুন ঢুকল | queue: front → back |
| --- | --- | --- | --- |
| শুরু | — | S | `[S]` |
| 1 | S | A, B | `[A, B]` |
| 2 | A | C, D | `[B, C, D]` |
| 3 | B | E | `[C, D, E]` |
| 4 | C | কেউ নয় | `[D, E]` |
| 5 | D | কেউ নয় | `[E]` |
| 6 | E | কেউ নয় | `[]` |

A ও B-এর পরে C, D, E বের হয়। সব edge-এর খরচ সমান হলে এই ক্রম shortest-path distance দেয়। ভিন্ন weight-এর ক্ষেত্রে সাধারণ BFS যথেষ্ট নয়।

```dsa
kind: grid
title: "একই ধারণা 3 × 3 খালি grid-এ"
steps:
  - label: "মাঝের cell থেকে চারদিকে চলার দূরত্ব"
    rows: [[2, 1, 2], [1, 0, 1], [2, 1, 2]]
    active: [[1, 1]]
    note: "শুরুতে 0; পাশের চারটি cell 1; কোণগুলো 2 ধাপ দূরে। তির্যক চলা নেই।"
```

বিস্তারিত: [Graph অধ্যায়](../09-graphs/README.md)।

## 5. Monotonic stack: কার উত্তর এখনও বাকি?

`[2, 1, 5, 3]`-এর প্রতিটি মানের ডানদিকে প্রথম বড় মান চাই। Stack-এ **উত্তর না-পাওয়া index** রাখি; তাদের মান নিচ থেকে উপরে কমতে থাকে।

```dsa
kind: stack
title: "5 এলে অপেক্ষায় থাকা 1 ও 2—দুজনের উত্তর মেলে"
steps:
  - label: "i = 1 পর্যন্ত: দুই index অপেক্ষায়"
    values: ["0: 2", "1: 1"]
    note: "প্রতি বাক্সে index: value। top-এ index 1।"
  - label: "i = 2, value = 5: দুজনকে pop করে 2 push"
    values: ["2: 5"]
    active: [0]
    note: "ans[1] = 5 এবং ans[0] = 5।"
  - label: "i = 3, value = 3: অপেক্ষায় যোগ"
    values: ["2: 5", "3: 3"]
    active: [1]
    note: "শেষ পর্যন্ত 5 ও 3-এর ডানে বড় মান নেই।"
```

| i | মান | stack-এ কাজ | index stack: bottom → top | নতুন উত্তর |
| --- | --- | --- | --- | --- |
| 0 | 2 | 0 push | `[0]` | — |
| 1 | 1 | 1 push | `[0,1]` | — |
| 2 | 5 | 1 pop, 0 pop, 2 push | `[2]` | `ans[1]=5`, `ans[0]=5` |
| 3 | 3 | 3 push | `[2,3]` | — |
| শেষ | — | বাকি index-এর উত্তর নেই | `[2,3]` | `ans[2]=ans[3]=-1` |

ফল **`[5, 5, -1, -1]`**। প্রতিটি index একবার push ও সর্বোচ্চ একবার pop হয়; nested `while` থাকলেও মোট **O(n)**।

## 6. Monotonic deque: window-র সবচেয়ে বড় মান

Array `[1, 3, -1, -3, 5, 3, 6, 7]`, window size `k = 3`। Deque-এ index রাখি; তাদের value সামনে থেকে পেছনে কমতে থাকে। তাই front-এর value-ই maximum।

নতুন মান `x` নেওয়ার সময়:

1. Front-এর index window ছেড়ে গেলে সরাও।
2. পেছন থেকে `x`-এর চেয়ে ছোট বা সমান মানের index সরাও। নতুন `x` অন্তত ততটাই বড় এবং বেশি দিন window-তে থাকবে।
3. নতুন index পেছনে ঢোকাও; window পূর্ণ হলে front-এর মান লিখে রাখো।

```dsa
kind: queue
title: "i = 3 থেকে i = 4: deque-এর দুই প্রান্তের কাজ"
steps:
  - label: "i = 3 · window [3, −1, −3]"
    values: ["1: 3", "2: −1", "3: −3"]
    active: [0]
    note: "প্রতি বাক্সে index: value। Front-এর 3-ই maximum।"
  - label: "i = 4 · index 1 window ছেড়েছে"
    values: ["2: −1", "3: −3"]
    note: "পুরনো maximum সামনে দিয়ে বের হলো।"
  - label: "নতুন 5 দুই ছোট মানকে সরায়"
    values: ["4: 5"]
    active: [0]
    note: "পেছন থেকে −3, তারপর −1 বাদ। নতুন window [-1, -3, 5]-এর maximum 5।"
```

পূর্ণ trace-এ deque-এর index ও value আলাদা রাখা হয়েছে, যাতে duplicate মান থাকলেও কোনটি বাদ যায় বোঝা যায়।

| i | x | বাদ যাওয়া index | deque indices | deque values | window maximum |
| --- | --- | --- | --- | --- | --- |
| 0 | 1 | — | `[0]` | `[1]` | window পূর্ণ নয় |
| 1 | 3 | পেছনে 0 | `[1]` | `[3]` | window পূর্ণ নয় |
| 2 | −1 | — | `[1,2]` | `[3,-1]` | 3 |
| 3 | −3 | — | `[1,2,3]` | `[3,-1,-3]` | 3 |
| 4 | 5 | সামনে 1; পেছনে 3, 2 | `[4]` | `[5]` | 5 |
| 5 | 3 | — | `[4,5]` | `[5,3]` | 5 |
| 6 | 6 | পেছনে 5, 4 | `[6]` | `[6]` | 6 |
| 7 | 7 | পেছনে 6 | `[7]` | `[7]` | 7 |

ফল **`[3, 3, 5, 5, 6, 7]`**। প্রতিটি index একবার ঢোকে ও সর্বোচ্চ একবার বের হয়: **O(n)** সময়, **O(k)** অতিরিক্ত জায়গা।

**নিজে চেষ্টা করো:** Next Greater-এর table-টি `[4, 2, 6, 1]` দিয়ে করো। তারপর sliding window-তে প্রতিটি বাদ যাওয়া index-এর কারণ বলো: মেয়াদ শেষ, নাকি আরও ভালো মান এসেছে? পরের পাঠ: [operations](./operations.md) ও [patterns](./patterns.md)।