04 — Stack and Queue¶
এখান থেকে শুরু করো¶
প্রথমে ধারণা, তারপর সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ, তারপর কোন প্রশ্নে কোন pattern পড়ো। প্রয়োজন হলে operation ও খরচ পাশে রাখো। সমস্ত problem ও বাংলা নোট এবং উৎসের তালিকা সরাসরি খোলা যাবে।
| ধাপ | কী শিখবে | প্রথম অনুশীলন |
|---|---|---|
| 1 | সর্বশেষ অসমাপ্ত কাজ | Valid Parentheses |
| 2 | দুই structure মেলানো | Queue Using Stacks |
| 3 | অতিরিক্ত তথ্য মনে রাখা | Min Stack |
| 4 | পরবর্তী বড় value | Daily Temperatures |
| 5 | স্তর ধরে ছড়ানো | Rotting Oranges |
| 6 | চলতি window-এর maximum | Sliding Window Maximum |
প্রতিটি ধাপে আগে ছোট 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/)।
- OS আর web server: task queue, message queue (Kafka, RabbitMQ হলো industrial-strength queue)।
- Python-এ
collections.dequeefficient queue চালায়; monotonic deque চালায় streaming window statistics।
Prerequisites¶
- Array chapter (../02-arrays-and-strings/) — এখানকার stack গুলো dynamic array-র উপর বানানো।
- Linked list chapter (../03-linked-list/) — 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-এর 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 | Matching (stack) | নোট পড়ো |
| Implement Queue using Stacks | LeetCode 232 | Design (two stacks) | নোট পড়ো |
| Implement Stack using Queues | LeetCode 225 | Design | নোট পড়ো |
| Min Stack — O(1) push/pop/top/min | LeetCode 155 | Design (twin stack) | নোট পড়ো |
| Next Greater Element I — একটা helper map নিয়ে | LeetCode 496 | Monotonic stack | নোট পড়ো |
| Baseball Game — operation দিয়ে score রাখা | LeetCode 682 | Stack simulation | নোট পড়ো |
Medium¶
| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
|---|---|---|---|
| Evaluate Reverse Polish Notation | LeetCode 150 | Stack simulation | নোট পড়ো |
| Daily Temperatures — কত দিন পর গরম দিন | LeetCode 739 | Monotonic stack | নোট পড়ো |
| Decode String like 3[a2[c]] | LeetCode 394 | Nesting (stack) | নোট পড়ো |
| Asteroid Collision — সংঘর্ষের পর কারা বাঁচে | LeetCode 735 | Stack simulation | নোট পড়ো |
| Number of Islands — flood fill region | LeetCode 200 | BFS frontier (queue) | নোট পড়ো |
| Rotting Oranges — পচন ছড়াতে কত মিনিট | LeetCode 994 | Multi-source BFS (queue) | নোট পড়ো |
| Next Greater Element II — circular array | LeetCode 503 | Monotonic stack | নোট পড়ো |
| Online Stock Span | LeetCode 901 | Monotonic stack | নোট পড়ো |
| Sum of Subarray Minimums — সব window minimum-এর মোট | LeetCode 907 | Monotonic stack + contribution (math level 5) | নোট পড়ো |
Hard¶
| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
|---|---|---|---|
| Sliding Window Maximum — প্রতিটা k-window-র max | LeetCode 239 | Monotonic deque — এই chapter-এর THE worked example, দেখো patterns.md | নোট পড়ো |
| Largest Rectangle in Histogram | LeetCode 84 | Monotonic stack | নোট পড়ো |
| Trapping Rain Water — stack solution | LeetCode 42 | Monotonic stack variant | নোট পড়ো |
| Basic Calculator — parentheses সহ expression | LeetCode 224 | Nesting (stack of contexts) | নোট পড়ো |
Visualization ideas (visualization-এর আইডিয়া)¶
- Stack: উপরে খোলা একটা খাড়া tube আঁকো; push একটা plate ভেতরে ফেলে, pop উপরের plate তুলে নেয়।
- Queue: একটা আনুভূমিক pipe আঁকো; পেছনে ঢোকার arrow, সামনে বেরোনোর arrow।
- Monotonic deque: array-র নিচে deque-টা আঁকো আর পেছন থেকে eject হওয়া প্রতিটা element-কে কেটে দাও (CROSS OUT) — কাটা গুলোই হলো "useless" element।
- VisuAlgo-তে stack/queue animation গুলো step by step দেখো।
- 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 থেকে)।
- 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/-এ ফিরে যায়)।
Recommended learning order (পরামর্শ দেওয়া শেখার ক্রম)¶
- concept.md — analogy, memory-র ছবি, invariant, complexity।
- visual-explanation.md — push/pop/enqueue/dequeue আর monotonic deque, frame by frame।
- operations.md — প্রতিটা operation cost আর pitfall সহ।
- patterns.md — matching, BFS frontier, monotonic stack, monotonic deque (full Sliding Window Maximum walkthrough সহ)।
- implementation.py — Stack, Queue, MinStack, next-greater, window-max — বানানো আর test করা।
problems/— tracker খোলো আর list বেয়ে ওঠো।
Source map¶
এই folder-এর প্রতিটা idea আর link-এর origin আর copying status-এর জন্য দেখো source-map.md।