Queue দিয়ে Stack এবং Stack দিয়ে Queue বানানোর সহজ নিয়ম

Introduction (ভূমিকা) আজকের এই আলোচনায় আমরা ডেটা স্ট্রাকচারের দুটি খুব গুরুত্বপূর্ণ সমস্যা নিয়ে কথা বলব। অনেক সময় ইন্টারভিউতে জিজ্ঞেস করা হয়—তোমার কাছে যদি শুধু Queue থাকে, তবে সেটা দিয়ে কি Stack-এর মতো কাজ করানো সম্ভব? আবার উল্টোটাও হতে পারে, অর্থাৎ Stack ব্যবহার করে Queue বানানো। এই ভিডিওতে Shradha Khapra ম্যাম খুব সহজভাবে দেখিয়েছেন কীভাবে দুটি Queue ব্যবহার করে একটি Stack তৈরি করা যায় এবং দুটি Stack ব্যবহার করে একটি Queue তৈরি করা যায়।

---

১. ২টা Queue ব্যবহার করে Stack তৈরি করা (Implement Stack using Queues)

ভিডিও রেফারেন্স: [00:23]

আমরা জানি Stack কাজ করে LIFO (Last In First Out) নিয়মে—অর্থাৎ যে সবার শেষে আসবে, সে সবার আগে বের হবে। কিন্তু Queue কাজ করে FIFO (First In First Out) নিয়মে—যে আগে আসবে সে আগে বের হবে। এখন Queue-কে Stack বানাতে হলে আমাদের একটু বুদ্ধি খাটাতে হবে।

কিভাবে কাজ করে? এখানে আমরা দুইটা Queue ব্যবহার করব: q1 (আসল ডেটা রাখার জন্য) এবং q2 (সহযোগিতা করার জন্য)। মূল আইডিয়া হলো—যখনই নতুন কোনো ডেটা আসবে, সেটাকে এমনভাবে q1-এর একদম সামনে রাখতে হবে যাতে সেটাকে পপ (Pop) করলে সবার আগে পাওয়া যায়।

ধাপগুলো হলো:

1. q1-এ যা আছে সব q2-তে পাঠিয়ে দাও।

2. নতুন ডেটাটাকে খালি q1-এ ঢুকাও।

3. এখন q2-তে যা যা ছিল, সব আবার q1-এ সিরিয়ালি ঢুকিয়ে দাও। এভাবে করলে নতুন ডেটাটা সবসময় q1-এর সামনে বা Front-এ থাকবে, যা Stack-এর Top হিসেবে কাজ করবে।

সহজ ভাষায় কঠিন শব্দ:

• LIFO (লিফো): লাস্ট ইন ফার্স্ট আউট। যেমন—থালা সাজিয়ে রাখলে উপরের থালাটা আগে নিতে হয়।

• FIFO (ফিফো): ফার্স্ট ইন ফার্স্ট আউট। যেমন—টিকিটের লাইনে যে আগে দাঁড়ায় সে আগে টিকিট পায়।

কোড উদাহরণ (C++):

C++

void push(int x) {
    // ১. সব এলিমেন্ট q1 থেকে q2 তে নাও
    while(!q1.empty()) {
        q2.push(q1.front());
        q1.pop();
    }
    // ২. নতুন এলিমেন্ট q1 এ রাখো
    q1.push(x);
    // ৩. সব আবার q2 থেকে q1 এ ফেরত আনো
    while(!q2.empty()) {
        q1.push(q2.front());
        q2.pop();
    }
} 

ব্যাখ্যা: এই কোডের মাধ্যমে আমরা নিশ্চিত করছি যে নতুন এলিমেন্টটা সবসময় Queue-এর সামনে থাকছে। ফলে pop() করলে সবসময় শেষের জিনিসটাই আগে বের হবে।

---

২. ২টা Stack ব্যবহার করে Queue তৈরি করা (Implement Queue using Stacks)

ভিডিও রেফারেন্স: [09:01]

এবার কাজটা উল্টো। Stack-কে বানাতে হবে Queue। অর্থাৎ আমাদের এমন কিছু করতে হবে যাতে Stack-এর একদম নিচে থাকা এলিমেন্টটা সবার আগে বের হয়ে আসে।

কিভাবে কাজ করে? এখানেও আমরা দুইটা Stack ব্যবহার করব: s1 এবং s2।

1. s1-এ যা আছে সব s2-তে ঢালো (এতে সব উল্টে যাবে)।

2. নতুন ডেটা s1-এর একদম নিচে (খালি অবস্থায়) রাখো।

3. s2 থেকে সব ডেটা আবার s1-এ নিয়ে আসো। এভাবে করলে সবার প্রথমে ঢোকানো ডেটাটা সবসময় s1-এর একদম উপরে থাকবে।

সহজ ভাষায় কঠিন শব্দ:

• Primary (প্রাইমারি): প্রধান বা মেইন জিনিস।

• Helper (হেল্পার): যে সাহায্য করে। এখানে s2 হলো সাহায্যকারী স্ট্যাক।

কোড উদাহরণ (C++):

C++

void push(int x) {
    // ১. s1 থেকে সব s2 তে নিয়ে যাও (উল্টে যাবে)
    while(!s1.empty()) {
        s2.push(s1.top());
        s1.pop();
    }
    // ২. নতুন x কে s1 এ ঢুকাও
    s1.push(x);
    // ৩. s2 থেকে সব আবার s1 এ নিয়ে আসো
    while(!s2.empty()) {
        s1.push(s2.top());
        s2.pop();
    }
} 

ব্যাখ্যা: এই পদ্ধতিতে আমরা Stack-এর ধর্মকে ব্যবহার করে ডেটা উল্টে দিচ্ছি, যাতে সেটা Queue-এর মতো আচরণ করে।

---

এনালাইসিস ও আমার চিন্তাভাবনা (Analysis & Thinking)

মূল উদ্দেশ্য: কন্টেন্ট ক্রিয়েটর এখানে বোঝাতে চেয়েছেন যে, লজিক ঠিক থাকলে এক ধরনের ডেটা স্ট্রাকচার দিয়ে অন্যটির কাজ করানো সম্ভব। ইন্টারভিউতে আপনার লজিক্যাল থিঙ্কিং চেক করার জন্য এই প্রশ্নগুলো খুব কমন।

বাস্তবতা ও সম্ভাবনা: বাস্তব জীবনে আমরা সরাসরি Stack বা Queue ব্যবহার করি কারণ সেগুলোতে অপারেশন দ্রুত হয়। কিন্তু এই কনভার্সন বা রূপান্তরের সময় push অপারেশনটি O(n) বা লিনিয়ার টাইম নেয় (কারণ লুপ চালাতে হয়), যা কিছুটা ধীরগতির।

বিকল্প বুদ্ধি: ভিডিওতে দেখানো হয়েছে push অপারেশনকে কঠিন করে বাকিগুলো সহজ রাখা। এর একটা বিকল্প আছে—push সহজ রেখে pop বা peek করার সময় এলিমেন্ট ট্রান্সফার করা। সেটাকেও "Amortized Constant Time" বলা হয়, যা অনেক ক্ষেত্রে বেশি কার্যকরী।

পরামর্শ: আপনি যদি বিগিনার হন, তবে প্রথমে খাতা-কলমে ছবি এঁকে এলিমেন্টগুলো এক পাত্র থেকে অন্য পাত্রে নেওয়ার প্র্যাকটিস করুন। এতে কোড মুখস্থ করতে হবে না, লজিকটা মাথায় গেঁথে যাবে।

---

Reference Link: https://www.youtube.com/watch?v=sFvP5Ois0CE

[

L79. Implement Queue using Stack & Stack using Queue

Shradha Khapra · 70K views

](http://www.youtube.com/watch?v=sFvP5Ois0CE)