Problem link ও উৎস
- **Original source:** Classic design exercise
- **Platform:** LeetCode —
- **Topic:** stack, queue, design
- **Difficulty:** Easy
- **Pattern:** design composition (queue-based)
- **Basic idea inherited from:** problem 4 (queue via stacks)-এর mirror — এবার উল্টো দিক থেকে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **LIFO stack** বানাতে হবে, কিন্তু শুধু **queue-র operation** (পেছনে push, সামনে থেকে pop/peek, size, empty) ব্যবহার করে। চারটা method support করতে হবে:
- `push(x)` — উপরে একটা element রাখো।
- `pop()` — উপরের (সবচেয়ে recent) element সরিয়ে return করো।
- `top()` — উপরের element দেখো (না সরিয়ে)।
- `empty()` — stack খালি কিনা বলো।
### Input ও output {#8-example-input-and-output}
```text
ops : push(1), push(2), top(), pop(), empty()
out : - - 2 2 False
তারপর: push(3), pop(), pop(), empty()
out : - 3 1 True
লক্ষ: pop সবসময় সবচেয়ে recent push-টা ফেরত দেয় (2, তারপর 3, তারপর 1)।
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা ঘূর্ণায়মান sushi belt ভাবো যা একমুখী ঘোরে। নতুন প্লেট পেছনে রাখার পর, যদি তুমি বাকি প্লেটগুলোকে একে একে তুলে আবার পেছনে রাখো (একপাক ঘোরাও), নতুন প্লেটটা ঠিক সামনে চলে আসে — গ্রাহক প্রথমেই সেটাই পায়। সবচেয়ে নতুন প্লেট সবার আগে — LIFO।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা problem 4 (Queue using Stacks)-এর **mirror**। সেখানে দুটো LIFO মিলে FIFO বানানো হয়েছিল; এখানে FIFO container দিয়ে LIFO behaviour বানাতে হবে। key idea একই — restricted structure-এর order-টাকে চালাকি করে উল্টে দেওয়া।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **rotation দিয়ে order উল্টানো।** queue স্বভাবতই সামনে-থেকে-পুরোনো দেয়। কিন্তু নতুন element ঢোকানোর সাথে সাথে যদি তার আগের সব element-কে একে একে পেছন থেকে তুলে আবার পেছনে রেখে দিই (rotate), তাহলে নতুন element সামনে চলে আসে। ফলে queue-র front সবসময় সবচেয়ে *recent* element ধরে রাখে — মানে stack-এর top।
invariant: প্রতিটা `push`-এর পরে, queue-র front = stack-এর top।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **queue** — Python-এ `collections.deque` (front থেকে `popleft`, back-এ `append`, দুটোই O(1))। একটা queue-ই যথেষ্ট, যদি প্রতি push-এ rotate করি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
queue শুধু FIFO দেয়, LIFO না — কিন্তু "push costly" trick দিয়ে আমরা front-কে সবসময় top বানিয়ে রাখি। `deque` ব্যবহার করি কারণ `popleft` আর `append` দুটোই O(1); সাধারণ `list`-এ `pop(0)` করলে প্রতিবার O(n) shift হতো ([../concept.md](../concept.md)-এ এই ফাঁদটা দেখানো আছে)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
বিকল্প: **দুটো** queue ব্যবহার করি, আর pop-কে costly বানাই। pop-এর সময় `q1`-এর শেষ element ছাড়া বাকি সব `q2`-তে সরাই, শেষ element-টা return করি, তারপর `q2`-কে `q1` বানাই।
```text
push: শুধু q1.append(x) -> সস্তা
pop : q1-এর শেষটা ছাড়া সব q2-তে সরাও; শেষটা return; swap q1,q2
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
ওই two-queue পদ্ধতিতে `pop` প্রতিবার O(n) (প্রায় সব element সরাতে হয়)। আমাদের one-queue rotate-on-push পদ্ধতিতে `push` O(n) কিন্তু `pop`/`top` O(1)। দুটোতেই কোনো-না-কোনো operation O(n) — queue দিয়ে stack বানানোর এটা অন্তর্নিহিত দাম (problem 4-এর দুই-stack-এ যেটা amortized O(1) ছিল)। আমরা single-queue, push-costly সংস্করণটা বেছে নিচ্ছি — সহজ আর compact।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **নতুন element ঢোকানোর সাথে সাথে যদি queue-টাকে এমনভাবে ঘোরাই যে সে front-এ চলে আসে, তাহলে queue-র স্বাভাবিক front-from-old আচরণই LIFO হয়ে যায়।** rotate-এর সংখ্যা = (নতুনটা ছাড়া) আগের element সংখ্যা।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা `deque` রাখো। `push(x)`: আগে `append(x)`, তারপর `len-1` বার `appendleft(popleft())` করে front-টা rotate করে নতুন element-কে সামনে আনো। `pop()`: `popleft()` — front, যেটা এখন top। `top()`: `q[0]`। `empty()`: queue খালি কিনা।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "queue তো LIFO দিতে পারে না" — এই বাধাটা সরাও order *maintain* করার দায়িত্ব push-এর কাঁধে দিয়ে। প্রতিটা push নিজেই queue-টাকে এমন অবস্থায় রেখে যায় যেখানে front = top; ফলে pop-কে আর কিছু ভাবতেই হয় না।
### ছবিতে বোঝা {#7-visual-explanation}
`push(1)`, `push(2)`, `push(3)`, তারপর `pop` (rotate-on-push পদ্ধতি):
```text
op কাজ queue (front বাঁয়ে)
push(1) append 1; rotate 0 বার [1]
push(2) append 2 -> [1,2]; rotate 1 বার [2, 1]
(front 1 তুলে পেছনে রাখো)
push(3) append 3 -> [2,1,3]; rotate 2 বার [3, 2, 1]
(2 পেছনে, তারপর 1 পেছনে)
top front = 3 [3, 2, 1]
pop popleft -> 3 [2, 1] (LIFO!)
```
প্রতিটা push-এর পর front-টাই হলো সদ্য-যোগ-করা element।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
operations: `push(1)`, `push(2)`, `top()`, `pop()`, `push(3)`, `pop()`, `pop()`:
1. `push(1)` → `append 1` → `[1]`; rotate 0 বার → `[1]`
2. `push(2)` → `append 2` → `[1, 2]`; rotate 1 বার (front 1 পেছনে) → `[2, 1]`
3. `top()` → `q[0]` = `2`
4. `pop()` → `popleft()` = `2` → `[1]`
5. `push(3)` → `append 3` → `[1, 3]`; rotate 1 বার (front 1 পেছনে) → `[3, 1]`
6. `pop()` → `popleft()` = `3` → `[1]`
7. `pop()` → `popleft()` = `1` → `[]`
বেরোনোর order: `2, 3, 1` — প্রতিবার সবচেয়ে recent push, ঠিক LIFO।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q) - 1): # নতুনটাকে সামনে আনতে rotate
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft() # front = top
def top(self):
return self.q[0]
def empty(self):
return not self.q
# ---- tests ----
s = MyStack()
s.push(1)
s.push(2)
assert s.top() == 2 # সবচেয়ে recent
assert s.pop() == 2 # LIFO
assert s.empty() is False
s.push(3)
assert s.pop() == 3
assert s.pop() == 1
assert s.empty() is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.q = deque()` — একটা double-ended queue, যাতে দুই প্রান্তই O(1)।
- `push(x)`: `append(x)` দিয়ে পেছনে রাখো; তারপর `len-1` বার `append(popleft())` — front-এর element গুলো একে একে পেছনে গিয়ে নতুন `x`-কে front-এ আনে।
- `pop()`: `popleft()` front সরায়, যেটা rotate-এর কল্যাণে সবচেয়ে recent।
- `top()`: `q[0]` front-টা দেখায় (না সরিয়ে)।
- `empty()`: queue খালি হলে `True`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
উপরের test: `push(1)`, `push(2)`-এর পর queue `[2, 1]`, তাই `top()` = `2`, `pop()` = `2`। `push(3)`-এর পর `[3, 1]`, `pop()` = `3`, তারপর `pop()` = `1`। `empty()` শেষে `True`। সব assert pass — print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
- `push`: **O(n)** — প্রতি push-এ পুরো queue rotate হয়।
- `pop` / `top` / `empty`: **O(1)**।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — একটাই queue, তাতে n-টা element জমে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `collections.deque`-এর বদলে `list` + `pop(0)` ব্যবহার — তাতে প্রতিটা `popleft`-সমতুল্য O(n) shift, পুরোটা ধীর।
- rotate-এর সংখ্যা ভুল — `len(self.q) - 1` বার ঘোরাতে হয় (নতুনটা ছাড়া বাকি সব); `len(self.q)` বার ঘোরালে আবার আগের অবস্থায় ফিরে যায়।
- push-এর *আগে* rotate করা — আগে `append` করতে হবে, তারপর rotate, নাহলে নতুন element সামনে আসবে না।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 4 (Queue using Stacks)-এর design-composition idea, এবার mirror করা; chapter-এর [../patterns.md](../patterns.md)-এর Pattern 3 (Design Compositions)। [../concept.md](../concept.md)-এর "queue-কে deque হতেই হবে" snippet এখানে কেন `deque` লাগছে তা ব্যাখ্যা করে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Implement Queue using Stacks (এর mirror) —