005 — Implement Stack using Queues¶

Problem link ও উৎস

Original source: Classic design exercise
Platform: LeetCode — https://leetcode.com/problems/implement-stack-using-queues/
Topic: stack, queue, design
Difficulty: Easy
Pattern: design composition (queue-based)
Basic idea inherited from: problem 4 (queue via stacks)-এর mirror — এবার উল্টো দিক থেকে

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

তোমাকে একটা LIFO stack বানাতে হবে, কিন্তু শুধু queue-র operation (পেছনে push, সামনে থেকে pop/peek, size, empty) ব্যবহার করে। চারটা method support করতে হবে:

push(x) — উপরে একটা element রাখো।
pop() — উপরের (সবচেয়ে recent) element সরিয়ে return করো।
top() — উপরের element দেখো (না সরিয়ে)।
empty() — stack খালি কিনা বলো।

Input ও output¶

উদাহরণ

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)।

চেনা উদাহরণে বোঝা¶

একটা ঘূর্ণায়মান sushi belt ভাবো যা একমুখী ঘোরে। নতুন প্লেট পেছনে রাখার পর, যদি তুমি বাকি প্লেটগুলোকে একে একে তুলে আবার পেছনে রাখো (একপাক ঘোরাও), নতুন প্লেটটা ঠিক সামনে চলে আসে — গ্রাহক প্রথমেই সেটাই পায়। সবচেয়ে নতুন প্লেট সবার আগে — LIFO।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা problem 4 (Queue using Stacks)-এর mirror। সেখানে দুটো LIFO মিলে FIFO বানানো হয়েছিল; এখানে FIFO container দিয়ে LIFO behaviour বানাতে হবে। key idea একই — restricted structure-এর order-টাকে চালাকি করে উল্টে দেওয়া।

ভেতরের যুক্তি¶

লুকানো logic হলো rotation দিয়ে order উল্টানো। queue স্বভাবতই সামনে-থেকে-পুরোনো দেয়। কিন্তু নতুন element ঢোকানোর সাথে সাথে যদি তার আগের সব element-কে একে একে পেছন থেকে তুলে আবার পেছনে রেখে দিই (rotate), তাহলে নতুন element সামনে চলে আসে। ফলে queue-র front সবসময় সবচেয়ে recent element ধরে রাখে — মানে stack-এর top।

invariant: প্রতিটা push-এর পরে, queue-র front = stack-এর top।

কী দিয়ে তথ্য রাখব¶

একটা queue — Python-এ collections.deque (front থেকে popleft, back-এ append, দুটোই O(1))। একটা queue-ই যথেষ্ট, যদি প্রতি push-এ rotate করি।

এটি কেন উপযুক্ত¶

queue শুধু FIFO দেয়, LIFO না — কিন্তু "push costly" trick দিয়ে আমরা front-কে সবসময় top বানিয়ে রাখি। deque ব্যবহার করি কারণ popleft আর append দুটোই O(1); সাধারণ list-এ pop(0) করলে প্রতিবার O(n) shift হতো (../concept.md-এ এই ফাঁদটা দেখানো আছে)।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

বিকল্প: দুটো queue ব্যবহার করি, আর pop-কে costly বানাই। pop-এর সময় q1-এর শেষ element ছাড়া বাকি সব q2-তে সরাই, শেষ element-টা return করি, তারপর q2-কে q1 বানাই।

উদাহরণ

push: শুধু q1.append(x)  -> সস্তা
pop : q1-এর শেষটা ছাড়া সব q2-তে সরাও; শেষটা return; swap q1,q2

কোথায় বেশি কাজ হচ্ছে¶

ওই 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।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: নতুন element ঢোকানোর সাথে সাথে যদি queue-টাকে এমনভাবে ঘোরাই যে সে front-এ চলে আসে, তাহলে queue-র স্বাভাবিক front-from-old আচরণই LIFO হয়ে যায়। rotate-এর সংখ্যা = (নতুনটা ছাড়া) আগের element সংখ্যা।

আরও কম কাজে সমাধান¶

একটা deque রাখো। push(x): আগে append(x), তারপর len-1 বার appendleft(popleft()) করে front-টা rotate করে নতুন element-কে সামনে আনো। pop(): popleft() — front, যেটা এখন top। top(): q[0]। empty(): queue খালি কিনা।

ভাবনার পরিবর্তন¶

মোচড়: "queue তো LIFO দিতে পারে না" — এই বাধাটা সরাও order maintain করার দায়িত্ব push-এর কাঁধে দিয়ে। প্রতিটা push নিজেই queue-টাকে এমন অবস্থায় রেখে যায় যেখানে front = top; ফলে pop-কে আর কিছু ভাবতেই হয় না।

ছবিতে বোঝা¶

push(1), push(2), push(3), তারপর pop (rotate-on-push পদ্ধতি):

উদাহরণ

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-এ ধাপে ধাপে¶

operations: push(1), push(2), top(), pop(), push(3), pop(), pop():

push(1) → append 1 → [1]; rotate 0 বার → [1]
push(2) → append 2 → [1, 2]; rotate 1 বার (front 1 পেছনে) → [2, 1]
top() → q[0] = 2
pop() → popleft() = 2 → [1]
push(3) → append 3 → [1, 3]; rotate 1 বার (front 1 পেছনে) → [3, 1]
pop() → popleft() = 3 → [1]
pop() → popleft() = 1 → []

বেরোনোর order: 2, 3, 1 — প্রতিবার সবচেয়ে recent push, ঠিক LIFO।

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

উপরের 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!।

খরচ ও সাধারণ ভুল¶

সময়¶

push: O(n) — প্রতি push-এ পুরো queue rotate হয়।
pop / top / empty: O(1)।

অতিরিক্ত জায়গা¶

O(n) — একটাই queue, তাতে n-টা element জমে।

যে ভুলগুলো এড়াতে হবে¶

collections.deque-এর বদলে list + pop(0) ব্যবহার — তাতে প্রতিটা popleft-সমতুল্য O(n) shift, পুরোটা ধীর।
rotate-এর সংখ্যা ভুল — len(self.q) - 1 বার ঘোরাতে হয় (নতুনটা ছাড়া বাকি সব); len(self.q) বার ঘোরালে আবার আগের অবস্থায় ফিরে যায়।
push-এর আগে rotate করা — আগে append করতে হবে, তারপর rotate, নাহলে নতুন element সামনে আসবে না।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: problem 4 (Queue using Stacks)-এর design-composition idea, এবার mirror করা; chapter-এর ../patterns.md-এর Pattern 3 (Design Compositions)। ../concept.md-এর "queue-কে deque হতেই হবে" snippet এখানে কেন deque লাগছে তা ব্যাখ্যা করে।

পরের অনুশীলন¶

Implement Queue using Stacks (এর mirror) — https://leetcode.com/problems/implement-queue-using-stacks/ (এই tracker-এর #4)
Min Stack — https://leetcode.com/problems/min-stack/ (#6)
Design Circular Deque — https://leetcode.com/problems/design-circular-deque/

কৌশলটি মনে রাখুন¶

Queue-to-stack via rotation: push-এর সময় নতুন element-কে front-এ rotate করে আনো, তাহলে queue-র front-from-old আচরণই LIFO হয়ে যায়।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "FIFO দিয়ে LIFO চাইলে — push-এ rotate করে নতুনটাকে সামনে আনো।" মনে রাখবে কোন operation-কে costly বানাবে সেটা তোমার পছন্দ (push-heavy বা pop-heavy)। আর queue মানেই Python-এ deque, কখনো list.pop(0) নয়।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।