Problem link ও উৎস
- **Original source:** Classic design exercise
- **Platform:** LeetCode —
- **Topic:** stack, queue, design
- **Difficulty:** Easy
- **Pattern:** design composition (two stacks)
- **Basic idea inherited from:** dynamic array-র amortized analysis ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) — কালেভদ্রে একটা দামি কাজ, যা অনেক সস্তা operation-এ ভাগ হয়ে যায়
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **FIFO queue** বানাতে হবে, কিন্তু শর্ত হলো — শুধু **stack-এর operation** (push, pop, peek, empty, size) ব্যবহার করতে পারবে, queue-র কোনো built-in operation না। চারটা method support করতে হবে:
- `push(x)` — পেছনে একটা element ঢোকাও।
- `pop()` — সামনের element সরিয়ে return করো।
- `peek()` — সামনের element দেখো (না সরিয়ে)।
- `empty()` — queue খালি কিনা বলো।
### Input ও output {#8-example-input-and-output}
```text
ops : push(1), push(2), peek(), pop(), empty()
out : - - 1 1 False
তারপর: push(3), pop(), pop(), empty()
out : - 2 3 True
Edge case (interleaved push/pop): উপরে দেখানো — push 3 আগের element-দের পেছনে যায়, সামনে নয়।
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুটো খাড়া নলের কথা ভাবো যাতে marble ফেলা হয়। প্রথম নলে (`in`) তুমি একে একে marble ফেলো — শেষেরটা উপরে। এখন প্রথম নলটা উপুড় করে দ্বিতীয় নলে (`out`) সব marble ঢেলে দিলে, *প্রথমে ফেলা* marble-টা এবার দ্বিতীয় নলের উপরে চলে আসে। দ্বিতীয় নল থেকে তুললে marble গুলো ঠিক যে order-এ ফেলেছিলে সেই order-এই বেরোয় — FIFO।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **dynamic array-র amortized argument** ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))-এর বংশধর: মাঝে মাঝে একটা দামি কাজ (পুরো stack ঢেলে দেওয়া) করি, কিন্তু সেই খরচটা পরবর্তী অনেকগুলো সস্তা operation-এর ঘাড়ে ভাগ করে দিই — তাই গড়ে (amortized) প্রতিটা operation O(1)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **double reversal**: একটা stack LIFO order দেয়; সেটাকে আরেকটা stack-এ ঢাললে order উল্টে যায় → আবার LIFO-র উল্টো = FIFO। তাই `in` stack-এ জমা করা element গুলো `out` stack-এ ঢাললে সঠিক queue order-এ বেরোয়।
amortized হিসাব: প্রতিটা element তার জীবনে বড়জোর **চারবার** ছোঁয়া হয় — `in`-এ push, `in` থেকে pop, `out`-এ push, `out` থেকে pop। সব O(1), তাই প্রতি operation amortized O(1)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
**দুটো stack** — একটা `in_stack` (নতুন element ঢোকার জন্য) আর একটা `out_stack` (পুরোনো element বেরোনোর জন্য)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
একটা stack একাই FIFO দিতে পারে না, কারণ সে শুধু শেষ-ঢোকা element দেয়। কিন্তু দুটো stack মিলে capability-টা বানিয়ে ফেলে: `in`-এ push করলে নতুনরা উপরে জমে; `out` খালি হলে `in`-এর পুরোটা `out`-এ ঢেলে দিলে order উল্টে যায়, তাই `out`-এর top এখন সবচেয়ে *পুরোনো* element — মানে queue-র front। এই trick-এর জন্যই দুটো stack নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সহজ (কিন্তু ব্যয়বহুল) চিন্তা: প্রতিটা `push`-এ নতুন element-কে queue-র সামনে আনি। মানে — সব পুরোনো element একটা helper stack-এ সরাও, নতুনটা রাখো, তারপর পুরোনো গুলো ফেরত আনো। তখন একটা stack-এর top-ই সবসময় queue-র front।
```text
push costly: প্রতিবার পুরো stack উল্টে, নতুনটা নিচে বসিয়ে, আবার উল্টাও।
pop/peek: সরাসরি top.
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
ওই "push-costly" পদ্ধতিতে প্রতিটা `push` O(n) (পুরো structure দুবার উল্টানো)। n-টা push করলে → O(n^2)। আমাদের lazy (দুই-stack) পদ্ধতি `out` খালি হলে *তবেই* ঢালে, আর প্রতিটা element সারা জীবনে একবারই ঢালা হয় — তাই amortized O(1)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **ঢালার কাজটা পিছিয়ে দাও (lazy)।** `out` stack-এ যতক্ষণ element আছে, ততক্ষণ সেগুলোই সঠিক front order-এ আছে — নতুন আসা element নিয়ে এখন মাথা ঘামানোর দরকার নেই। `out` *খালি* হলে তবেই `in`-এর পুরোটা একবারে ঢালো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুটো stack রাখো। `push` শুধু `in_stack`-এ `append` করে — সস্তা। `peek`/`pop`-এর সময় দেখো `out_stack` খালি কিনা; খালি হলে `in_stack`-এর সবকিছু `out_stack`-এ ঢেলে দাও (এক-একটা pop করে অন্যটায় push — order উল্টে যায়)। তারপর `out_stack`-এর top-ই হলো queue-র front।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "queue-র front সবসময় তৈরি রাখতে হবে" ভাবার বদলে ভাবো "front যখন *দরকার হবে*, তখনই তৈরি করব, এবং একবার তৈরি হলে সেটা যতক্ষণ পারি ব্যবহার করব।" এই laziness-ই O(n^2)-কে amortized O(1)-এ নামায়।
### ছবিতে বোঝা {#7-visual-explanation}
operation `push 1, push 2, peek, pop, push 3, pop`:
```text
op in_stack out_stack note
push 1 [1] []
push 2 [1, 2] []
peek [] [2, 1] out খালি -> in ঢালো; front = out top = 1
pop [] [2] out top pop -> 1 (FIFO!)
push 3 [3] [2]
pop [3] [] out খালি না -> top pop -> 2 (FIFO)
```
লক্ষ করো: `out` খালি না থাকলে আমরা আবার ঢালি না — তাই নতুন `push 3` পুরোনো `2`-কে টপকে যায় না।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
operations: `push(1)`, `push(2)`, `peek()`, `pop()`, `push(3)`, `pop()`, `pop()`:
1. `push(1)` → `in=[1]`, `out=[]`
2. `push(2)` → `in=[1, 2]`, `out=[]`
3. `peek()` → `out` খালি, ঢালো: `out=[2, 1]`; front = `out[-1]` = `1`
4. `pop()` → `out` খালি না; `out.pop()` = `1`, `out=[2]`
5. `push(3)` → `in=[3]`, `out=[2]`
6. `pop()` → `out` খালি না; `out.pop()` = `2`, `out=[]`
7. `pop()` → `out` খালি, ঢালো: `out=[3]`; `out.pop()` = `3`
বেরোনোর order: `1, 2, 3` — ঠিক FIFO।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x):
self.in_stack.append(x) # সবসময় in-এ জমাও
def _transfer(self):
if not self.out_stack: # out খালি হলেই ঢালো (lazy)
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def peek(self):
self._transfer()
return self.out_stack[-1] # out-এর top = front
def pop(self):
self._transfer()
return self.out_stack.pop() # front সরিয়ে return
def empty(self):
return not self.in_stack and not self.out_stack
# ---- tests ----
q = MyQueue()
q.push(1)
q.push(2)
assert q.peek() == 1 # front
assert q.pop() == 1 # FIFO
assert q.empty() is False
q.push(3)
assert q.pop() == 2 # পুরোনোটা আগে
assert q.pop() == 3
assert q.empty() is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.in_stack`, `self.out_stack` — দুটো খালি stack; নতুন `in`-এ, বেরোনো `out` থেকে।
- `push(x)` — শুধু `in_stack`-এ `append`; O(1)।
- `_transfer()` — `out_stack` খালি হলে `in_stack`-এর সব element `pop`-করে-`append` করে ঢেলে দেয়, order উল্টে যায়। খালি না হলে কিছুই করে না (lazy)।
- `peek()` — ঢালার পর `out_stack[-1]`, মানে সবচেয়ে পুরোনো element।
- `pop()` — ঢালার পর `out_stack.pop()`, front সরিয়ে দেয়।
- `empty()` — দুটো stack-ই খালি হলে queue খালি।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
উপরের test: `push(1)`, `push(2)`-এর পর `peek()` `out`-কে `[2, 1]` বানায়, front `1` দেয়। `pop()` `1` দেয়। `push(3)`-এর পর `out=[2]` থাকায় পরের `pop()` `2` দেয়, তারপর `pop()` আবার ঢেলে `3` দেয়। `empty()` শেষে `True`। সব assert pass — print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class MyQueue {
constructor() {
this.inStack = []; // নতুন element এখানে জমে
this.outStack = []; // পুরোনো element এখান থেকে বেরোয়
}
push(x) { this.inStack.push(x); } // সবসময় in-এ — O(1)
_transfer() {
if (this.outStack.length === 0) { // out খালি হলেই ঢালো (lazy)
while (this.inStack.length) this.outStack.push(this.inStack.pop());
}
}
peek() { this._transfer(); return this.outStack[this.outStack.length - 1]; }
pop() { this._transfer(); return this.outStack.pop(); }
empty() { return this.inStack.length === 0 && this.outStack.length === 0; }
}
// ---- test cases ----
const q = new MyQueue();
q.push(1);
q.push(2);
assert(q.peek() === 1, "front 1"); // সবচেয়ে পুরোনো
assert(q.pop() === 1, "FIFO 1");
assert(q.empty() === false, "not empty");
q.push(3);
assert(q.pop() === 2, "পুরোনোটা আগে"); // push 3 সামনে আসে না
assert(q.pop() === 3, "then 3");
assert(q.empty() === true, "empty শেষে");
console.log("সব JS test pass!");
```
> **JS টীকা:** JS-এ array নিজেই একটা নিখুঁত stack — `push`/`pop` দুটোই array-র শেষ প্রান্তে কাজ করে, amortized O(1)। `outStack` খালি কিনা বলতে `.length === 0` ব্যবহার করো; `!this.outStack` ভুল হবে কারণ খালি array-ও truthy। দুটো array দিয়েই double-reversal করে FIFO পাওয়া যায়, আলাদা কোনো linked-list দরকার নেই।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
class MyQueue {
private inStack: number[] = [];
private outStack: number[] = [];
push(x: number): void { this.inStack.push(x); }
private transfer(): void {
if (this.outStack.length === 0) {
while (this.inStack.length) this.outStack.push(this.inStack.pop()!);
}
}
peek(): number { this.transfer(); return this.outStack[this.outStack.length - 1]; }
pop(): number { this.transfer(); return this.outStack.pop()!; }
empty(): boolean { return this.inStack.length === 0 && this.outStack.length === 0; }
}
function expect