# 04 — Stack and Queue

## এখান থেকে শুরু করো

প্রথমে [ধারণা](concept.md), তারপর [সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ](visual-explanation.md), তারপর [কোন প্রশ্নে কোন pattern](patterns.md) পড়ো। প্রয়োজন হলে [operation ও খরচ](operations.md) পাশে রাখো। [সমস্ত problem ও বাংলা নোট](problems/README.md) এবং [উৎসের তালিকা](source-map.md) সরাসরি খোলা যাবে।

| ধাপ | কী শিখবে | প্রথম অনুশীলন |
| --- | --- | --- |
| 1 | সর্বশেষ অসমাপ্ত কাজ | [Valid Parentheses](problems/001-valid-parentheses.md) |
| 2 | দুই structure মেলানো | [Queue Using Stacks](problems/004-queue-via-stacks.md) |
| 3 | অতিরিক্ত তথ্য মনে রাখা | [Min Stack](problems/006-min-stack.md) |
| 4 | পরবর্তী বড় value | [Daily Temperatures](problems/009-daily-temperatures.md) |
| 5 | স্তর ধরে ছড়ানো | [Rotting Oranges](problems/013-rotting-oranges.md) |
| 6 | চলতি window-এর maximum | [Sliding Window Maximum](problems/019-sliding-window-maximum.md) |

প্রতিটি ধাপে আগে ছোট input নিজে আঁকো, তারপর code লেখো। পরের ধাপে যাওয়ার আগে বলো: **কোন তথ্য রাখছি, প্রতি ধাপে কোন নিয়ম ঠিক থাকছে, এবং কাজের মোট খরচ কত?**

## বাস্তব প্রোগ্রামে সিদ্ধান্ত নেওয়া

| প্রোগ্রামে দরকার | structure | ছোট উদাহরণ | শর্ত |
| --- | --- | --- | --- |
| text editor-এর undo | stack | edit A, edit B; undo করলে আগে B ফেরত | redo চাইলে আরেকটি stack |
| printer-এর pending job | queue | A আগে জমা হলে B-এর আগে নেওয়া হবে | priority লাগলে priority queue আলাদা |
| সমান খরচের grid-এ কম ধাপে পৌঁছানো | BFS queue | distance 0, তারপর 1, তারপর 2 | visited চিহ্ন enqueue করার সময় |
| শেষ k sample-এর সর্বোচ্চ মান | monotonic deque | পুরনো index সামনে বাদ, অপ্রয়োজনীয় ছোট value পেছনে বাদ | deque-তে index রাখবে |
| nested expression পড়া | stack | `2*(3+4)`-এর ভেতরের context আগে শেষ | token ও operator-এর নিয়মও parser-এ লাগবে |


> উল্টো personality-র দুটো restricted list: stack সবচেয়ে নতুন জিনিসটা আগে মনে রাখে, queue সবচেয়ে পুরনো জিনিসটা আগে মনে রাখে।

---

## এই data structure-টা কী

**Stack** হলো এমন একটা sequence যেখানে তুমি শুধু একটাই প্রান্তে (the **top**) add আর remove করতে পারো। Last In, First Out — **LIFO**।

**Queue** হলো এমন একটা sequence যেখানে তুমি এক প্রান্তে (the **back**) add করো আর অন্য প্রান্ত (the **front**) থেকে remove করো। First In, First Out — **FIFO**।

**Deque** (double-ended queue) দুই প্রান্তেই O(1) add/remove করতে দেয় — এটা stack হতে পারে, queue হতে পারে, অথবা আরো চালাক কিছু (monotonic deque, এই chapter-এর star pattern)।

এগুলো *restricted* structure: এরা ইচ্ছে করেই random access নিষেধ করে। এই restriction-টাই feature — এতে processing-এর order একটা guarantee হয়ে যায়, আশা না।

## কেন এটার অস্তিত্ব (কোন কষ্টটা solve করে)

সাধারণ list তোমাকে যেকোনো জায়গায় যেকোনো কিছু ছুঁতে দেয় — মানে কোন order-এ জিনিসগুলো handle হবে সেটা *তোমাকে* মনে রাখতে হয়। Stack আর queue order-টা structure-এর ভেতরেই গেঁথে দেয়:

- **Stack = "most recent unfinished thing first।"** যেখানেই কাজ nest করে সেখানে perfect: function call-এর ভেতরে function call, bracket-এর ভেতরে bracket, undo-র ভেতরে undo। Structure-টাই তোমার হয়ে বেরিয়ে আসার পথটা মনে রাখে।
- **Queue = "fairness / arrival order।"** যেখানেই জিনিস আসার ক্রমে serve করতে হয় সেখানে perfect: print job, request, BFS-এর layer। নতুন আসা কেউ পুরনো কাউকে starve করাতে পারে না।

এগুলো ছাড়া প্রতিটা program-এ তোমাকে error-prone index-এর কারিকুরি দিয়ে "কোথায় ফিরতে হবে মনে রাখা" বা "আসার ক্রমে serve করা" নতুন করে বানাতে হতো।

## বাস্তব software-এ কোথায় ব্যবহার হয়

- তোমার লেখা প্রতিটা program চালায় **call stack**; recursion আসলে একটা stack।
- Editor-এ undo/redo; তোমার browser-এর back/forward button — দুটো stack।
- Compiler আর interpreter: expression parse করা, bracket মেলানো, postfix evaluate করা।
- Graph-এ **BFS** তার frontier হিসেবে একটা queue ব্যবহার করে ([../09-graphs/](../09-graphs/README.md))।
- OS আর web server: task queue, message queue (Kafka, RabbitMQ হলো industrial-strength queue)।
- Python-এ `collections.deque` efficient queue চালায়; monotonic deque চালায় streaming window statistics।

## Prerequisites

- Array chapter ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)) — এখানকার stack গুলো dynamic array-র উপর বানানো।
- Linked list chapter ([../03-linked-list/](../03-linked-list/README.md)) — queue কেন সাধারণ Python list হওয়া উচিত না সেটা বুঝতে।
- Basic Big-O।

## শেখার আগে কী revise করবে

- `list.append` / `list.pop` আর কেন দুটোই শুধু END-এ O(1)।
- কেন `list.pop(0)` O(n) (সামনে থেকে delete করলে সবকিছু shift হয় — arrays chapter)।
- [../02-arrays-and-strings/patterns.md](../02-arrays-and-strings/patterns.md)-এর sliding-window pattern — monotonic deque সেটাকেই upgrade করে।
- Nesting-এর intuition: `f()` ডাকছে `g()`-কে, `g()` ডাকছে `h()`-কে — কীভাবে উল্টো ক্রমে unwind হতেই হবে।

## Learning goals (checklist)

- [ ] LIFO আর FIFO বলো আর না ভেবে প্রতিটার একটা বাস্তব জীবনের example দাও।
- [ ] ব্যাখ্যা করো Python list কেন দারুণ stack কিন্তু বাজে queue।
- [ ] `collections.deque` দিয়ে একটা queue implement করো আর বলো দুই প্রান্ত কেন O(1)।
- [ ] Balanced-brackets ঠান্ডা মাথায় solve করো, তিনটা failure mode সহ।
- [ ] ব্যাখ্যা করো BFS-এর queue কীভাবে layer-by-layer order guarantee করে।
- [ ] O(1) `get_min` সহ একটা MinStack বানাও আর twin-stack invariant ব্যাখ্যা করো।
- [ ] Monotonic stack দিয়ে Next Greater Element solve করো আর ব্যাখ্যা করো এটা কেন O(n), O(n^2) না।
- [ ] Monotonic deque দিয়ে Sliding Window Maximum solve করো আর "useless elements" argument-টা ব্যাখ্যা করো।
- [ ] "previous/next smaller/greater" এই কথাগুলো শুনলেই monotonic-stack trigger চিনে ফেলো।

## Problem categories (problem-এর ধরন)

| Category | Typical question shape |
| --- | --- |
| Matching / nesting | "valid parentheses", "decode nested string", "simplify path" |
| Stack simulation | "undo", "browser history", "evaluate expression" |
| Design | "min stack", "queue using stacks", "stack using queues" |
| BFS frontier | "shortest steps", "level order", "rotting/spreading process" |
| Monotonic stack | "next/previous greater/smaller", "largest rectangle", "stock span" |
| Monotonic deque | "max/min of every sliding window", windowed optimization |

## Practice list

Task গুলো আমাদের নিজেদের ভাষায় বলা; official statement link-এর পেছনে।

### Easy

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Valid Parentheses — bracket গুলো কি ঠিকভাবে nested? | [LeetCode 20](https://leetcode.com/problems/valid-parentheses/) | Matching (stack) | [নোট পড়ো](problems/001-valid-parentheses.md) |
| Implement Queue using Stacks | [LeetCode 232](https://leetcode.com/problems/implement-queue-using-stacks/) | Design (two stacks) | [নোট পড়ো](problems/004-queue-via-stacks.md) |
| Implement Stack using Queues | [LeetCode 225](https://leetcode.com/problems/implement-stack-using-queues/) | Design | [নোট পড়ো](problems/005-stack-via-queues.md) |
| Min Stack — O(1) push/pop/top/min | [LeetCode 155](https://leetcode.com/problems/min-stack/) | Design (twin stack) | [নোট পড়ো](problems/006-min-stack.md) |
| Next Greater Element I — একটা helper map নিয়ে | [LeetCode 496](https://leetcode.com/problems/next-greater-element-i/) | Monotonic stack | [নোট পড়ো](problems/007-next-greater-i.md) |
| Baseball Game — operation দিয়ে score রাখা | [LeetCode 682](https://leetcode.com/problems/baseball-game/) | Stack simulation | [নোট পড়ো](problems/002-baseball-game.md) |

### Medium

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Evaluate Reverse Polish Notation | [LeetCode 150](https://leetcode.com/problems/evaluate-reverse-polish-notation/) | Stack simulation | [নোট পড়ো](problems/008-evaluate-rpn.md) |
| Daily Temperatures — কত দিন পর গরম দিন | [LeetCode 739](https://leetcode.com/problems/daily-temperatures/) | Monotonic stack | [নোট পড়ো](problems/009-daily-temperatures.md) |
| Decode String like 3[a2[c]] | [LeetCode 394](https://leetcode.com/problems/decode-string/) | Nesting (stack) | [নোট পড়ো](problems/010-decode-string.md) |
| Asteroid Collision — সংঘর্ষের পর কারা বাঁচে | [LeetCode 735](https://leetcode.com/problems/asteroid-collision/) | Stack simulation | [নোট পড়ো](problems/011-asteroid-collision.md) |
| Number of Islands — flood fill region | [LeetCode 200](https://leetcode.com/problems/number-of-islands/) | BFS frontier (queue) | [নোট পড়ো](problems/012-number-of-islands.md) |
| Rotting Oranges — পচন ছড়াতে কত মিনিট | [LeetCode 994](https://leetcode.com/problems/rotting-oranges/) | Multi-source BFS (queue) | [নোট পড়ো](problems/013-rotting-oranges.md) |
| Next Greater Element II — circular array | [LeetCode 503](https://leetcode.com/problems/next-greater-element-ii/) | Monotonic stack | [নোট পড়ো](problems/015-next-greater-ii.md) |
| Online Stock Span | [LeetCode 901](https://leetcode.com/problems/online-stock-span/) | Monotonic stack | [নোট পড়ো](problems/016-stock-span.md) |
| Sum of Subarray Minimums — সব window minimum-এর মোট | [LeetCode 907](https://leetcode.com/problems/sum-of-subarray-minimums/) | Monotonic stack + contribution (math level 5) | [নোট পড়ো](problems/017-sum-subarray-minimums.md) |

### Hard

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Sliding Window Maximum — প্রতিটা k-window-র max | [LeetCode 239](https://leetcode.com/problems/sliding-window-maximum/) | Monotonic deque — এই chapter-এর THE worked example, দেখো [patterns.md](./patterns.md) | [নোট পড়ো](problems/019-sliding-window-maximum.md) |
| Largest Rectangle in Histogram | [LeetCode 84](https://leetcode.com/problems/largest-rectangle-in-histogram/) | Monotonic stack | [নোট পড়ো](problems/020-largest-rectangle.md) |
| Trapping Rain Water — stack solution | [LeetCode 42](https://leetcode.com/problems/trapping-rain-water/) | Monotonic stack variant | [নোট পড়ো](problems/021-trapping-rain-water-stack.md) |
| Basic Calculator — parentheses সহ expression | [LeetCode 224](https://leetcode.com/problems/basic-calculator/) | Nesting (stack of contexts) | [নোট পড়ো](problems/022-basic-calculator.md) |

## Visualization ideas (visualization-এর আইডিয়া)

- Stack: উপরে খোলা একটা খাড়া tube আঁকো; push একটা plate ভেতরে ফেলে, pop উপরের plate তুলে নেয়।
- Queue: একটা আনুভূমিক pipe আঁকো; পেছনে ঢোকার arrow, সামনে বেরোনোর arrow।
- Monotonic deque: array-র নিচে deque-টা আঁকো আর পেছন থেকে eject হওয়া প্রতিটা element-কে কেটে দাও (CROSS OUT) — কাটা গুলোই হলো "useless" element।
- [VisuAlgo](https://visualgo.net/en)-তে stack/queue animation গুলো step by step দেখো।
- [patterns.md](patterns.md)-এর Sliding Window Maximum table-টা হাতে re-trace করো — এটাই chapter-এর centerpiece।

## Common mistakes (সাধারণ ভুল)

- Queue-র জন্য `list.pop(0)` ব্যবহার করা — চুপচাপ প্রতি dequeue-তে O(n), overall O(n^2)। `collections.deque` ব্যবহার করো।
- "Leftover stack" check ভুলে যাওয়া: bracket তিনভাবে fail করতে পারে — *underflow* (খালি stack-এ close করা), *mismatch*, অথবা *leftovers* (শেষে non-empty)। তিনটাই handle করতে হবে।
- Guard ছাড়া খালি stack/deque থেকে pop করা।
- Monotonic stack: যখন *index* দরকার তখন value push করা (distance-এর জন্য প্রায় সবসময়ই index লাগে)।
- Monotonic deque: ভুল প্রান্তে compare করা, অথবা window থেকে বেরিয়ে যাওয়া element-টা evict করতে ভুলে যাওয়া।
- BFS: node-কে *push*-এর বদলে *pop*-এর সময় visited mark করা, যাতে queue-তে duplicate ঢোকে।

## Interview problem-এর সাথে connection

Stack question (valid parentheses, min stack, calculator) সব level-এর interview-র staple, আর **monotonic stack/deque problem গুলো big-tech-style interview-র একটা প্রিয় hard-question family** — Largest Rectangle আর Sliding Window Maximum হলো classic "separates the prepared from the unprepared" problem। "নতুন আসা element-এর চেয়ে ছোট যে কেউ আর কখনো answer হতে পারবে না, তাই তাকে ফেলে দিই" — এটা বলতে পারাই ঠিক সেই ধরনের invariant-based reasoning যেটা interviewer-রা reward করে।

## Competitive programming-এর সাথে connection

- BFS-with-queue হলো unweighted graph-এ shortest-path problem-এর মেরুদণ্ড (CSES-এর একটা গোটা graph section আছে; শুরু করো [CSES Problem Set](https://cses.fi/problemset/) থেকে)।
- Monotonic deque দেয় O(n) sliding-window minimum/maximum — অনেক DP optimization-এর ভেতরের একটা building block।
- Monotonic stack O(n)-এ previous/next smaller element বের করে — histogram problem আর contribution-technique counting-এর চাবি (দেখো Sum of Subarray Minimums, যেটা আবার [../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এ ফিরে যায়)।

## Recommended learning order (পরামর্শ দেওয়া শেখার ক্রম)

1. [concept.md](concept.md) — analogy, memory-র ছবি, invariant, complexity।
2. [visual-explanation.md](visual-explanation.md) — push/pop/enqueue/dequeue আর monotonic deque, frame by frame।
3. [operations.md](operations.md) — প্রতিটা operation cost আর pitfall সহ।
4. [patterns.md](patterns.md) — matching, BFS frontier, monotonic stack, monotonic deque (full Sliding Window Maximum walkthrough সহ)।
5. [implementation.py](implementation.py) — Stack, Queue, MinStack, next-greater, window-max — বানানো আর test করা।
6. `problems/` — tracker খোলো আর list বেয়ে ওঠো।

## Source map

এই folder-এর প্রতিটা idea আর link-এর origin আর copying status-এর জন্য দেখো [source-map.md](./source-map.md)।