04 — Stack and Queue¶
উল্টো 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 | Source | 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 | Source | 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 | Source | 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।