stack আর queue: আগে বেরোয় সবচেয়ে নতুনটা, নাকি সবচেয়ে পুরোনোটা

Bob একটা paragraph টাইপ করে, একটা শব্দ bold করে, তারপর ভুল করে একটা লাইন মুছে ফেলে। Undo চাপলে editor-কে আগে ফেরাতে হবে সবচেয়ে নতুন বদলটা, ঠিক থালার স্তূপের উপরের থালাটার মতো। Alice-এর বেকারির কাজ উল্টো: যে আগে এসেছে, সে আগে জিনিস পায়, মানে একটা লাইন। Vector বা deque দিয়ে দুটো কাজই চলত, কিন্তু দুটোই এমন কিছু নড়াচড়া করতে দেয়, যা এই কাজে কখনো হওয়া চলবে না। এই lesson প্রতিটা কাজকে এমন একটা container দেবে, যেটা শুধু ঠিক নড়াচড়াগুলোই করতে দেয়।

দুইটা কাজ, দুই রকম ক্রম

Bob-এর undo-র তালিকা আর Alice-এর লাইনে একই ধরনের জিনিস থাকে: আসার ক্রমে কয়েকটা item। তফাত শুধু একটাই, কোনটা আগে বেরোয়। Bob-এর তালিকায় আগে বেরোয় সবচেয়ে নতুনটা, এই ক্রমের নাম LIFO: last in, first out, শেষে ঢুকলে আগে বেরোয়। Alice-এর লাইনে আগে বেরোয় সবচেয়ে পুরোনোটা, এই ক্রমের নাম FIFO: first in, first out, আগে ঢুকলে আগে বেরোয়।

Stack হলো LIFO ক্রমের container, আর queue (উচ্চারণ "কিউ") হলো FIFO ক্রমের container। Stack-এর খোলা মাথা মাত্র একটা, তার নাম top। Queue-এর খোলা মাথা দুইটা: জিনিস ঢোকে back দিয়ে, মানে পেছনে, আর বেরোয় front দিয়ে, মানে সামনে।

তাই যেকোনো কাজকে একটাই প্রশ্ন করো: আগে কে বেরোবে, সবচেয়ে নতুনটা, নাকি সবচেয়ে পুরোনোটা? নতুনটা হলে stack, পুরোনোটা হলে queue।

Stack নড়ে এক মাথায়

এবার একটা stack-কে নড়তে দেখো। নিচের প্রতিটা ধাপ থালার একটা stack-এর উপর একটা করে call, থালাগুলোর নম্বর 1, 2 আর 3, যে ক্রমে আসে। খেয়াল করো, প্রতিটা push কোথায় গিয়ে বসে, আর প্রতিটা pop কোথা থেকে নেয়।

থালা ঢুকেছিল 1, 2, 3 ক্রমে, আর বেরোল 3, 2, 1 ক্রমে। উপরের থালাগুলো চলে যাওয়ার আগে থালা 1-এ কেউ হাতই দেয়নি। তাই stack জিনিস ফেরত দেয় ঢোকার ঠিক উল্টো ক্রমে।

Queue নড়ে দুই মাথায়

এবার একই রকম ধাপ, একটা queue-এর উপর। Alice-এর লাইনে তিনটা ticket ঢোকে, দুইটা বেরোয়, তারপর আরেকটা ঢোকে। Front আর back আলাদা করে খেয়াল করো।

Queue-এ push কাজ করে পেছনে আর pop সামনে, তাই দুজনের কখনো দেখা হয় না। Ticket 104 এসেছে সবার শেষে, তাই অপেক্ষা করে সবার পেছনে। তাই queue জিনিস ফেরত দেয় ঠিক যে ক্রমে ঢুকেছিল, সেই ক্রমেই।

প্রথম দিনেই যে syntax লাগবে

#include <stack>
#include <queue>

stack<T> s;                an empty stack of T
s.push(x);                 put x on the top
s.top()                    the top element, the newest
s.pop();                   remove the top element; returns nothing

queue<T> q;                an empty queue of T
q.push(x);                 add x at the back
q.front()                  the front element, the oldest
q.back()                   the back element, the newest
q.pop();                   remove the front element; returns nothing

s.size()    s.empty()      how many, and whether there are none (q too)

তাই stack-এর কাজের call তিনটা, push, top আর pop, আর queue-এর চারটা: push, front, back আর pop।

Adaptor: সরু দরজার একটা container

std::stack আর std::queue নিজেরা কিছুই জমা রাখে না। প্রত্যেকে ভিতরে আরেকটা container রাখে, তুমি অন্য কিছু না বললে একটা deque, আর তোমার call-গুলো সেটার কাছে পৌঁছে দেয়। এভাবে আরেকটা class-কে মুড়ে রাখা class-কে বলে adaptor। Module 4-এর lesson 04 এটা আগেই দেখিয়েছে: ওর container_type program print করেছিল queue keeps a deque inside: yes।

Adaptor-এর পুরো কাজটাই হলো দরজাটা সরু করা। ভিতরের deque-এর সামনে আছে, পেছনে আছে, আর index দিয়ে পড়ার মতো মাঝখানও আছে। Stack তোমাকে ছুঁতে দেয় শুধু ওর top, আর queue শুধু ওর দুই মাথা। দরজায় নেই এমন call compile-ই হয় না, আর প্রতিটার বার্তা দেখাবে lesson 02।

দরজার প্রতিটা call ভিতরের deque-এর উপর একটাই call, ওর কোনো একটা মাথায়। Module 4 দেখিয়েছে, deque-এর মাথাগুলো সস্তা, তাই এখানকার প্রতিটা push, দেখা আর pop-ও সস্তা। তাই adaptor নতুন কোনো জায়গা যোগ করে না: ও কিছু নড়াচড়া কেড়ে নেয়, আর রাখে শুধু কাজের গুলো।

Stack-এ push, top আর pop

push(x) x-কে top-এ বসায়। top() বলে এই মুহূর্তে top-এ কী আছে। pop() সেটা সরিয়ে দেয়। এই program প্রতিটা call-এর পরে top আর size print করে।

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "top " << s.top() << ", size " << s.size() << '\n';
    s.pop();
    cout << "top " << s.top() << ", size " << s.size() << '\n';
    s.push(40);
    cout << "top " << s.top() << ", size " << s.size() << '\n';
    return 0;
}

top 30, size 3
top 20, size 2
top 40, size 3

Pop-এর পরে 20 আবার top-এ ফিরে এল, কারণ ও ছিল 30-এর নিচে। তারপর 40 বসল 20-এর উপরে। নিচের 10-কে একবারও দেখা গেল না: stack তোমাকে শুধু ওর top-টাই দেখায়। তাই top() সবসময় বলে সবচেয়ে শেষের সেই push-টার কথা, যেটা এখনো pop হয়নি।

Queue-এ push, front, back আর pop

Queue-এর push(x) x-কে পেছনে যোগ করে। front() হলো সবচেয়ে পুরোনো element, আর back() সবচেয়ে নতুনটা। pop() সামনেরটা সরায়।

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    cout << "front " << q.front() << ", back " << q.back() << ", size " << q.size() << '\n';
    q.pop();
    cout << "front " << q.front() << ", back " << q.back() << ", size " << q.size() << '\n';
    q.push(40);
    cout << "front " << q.front() << ", back " << q.back() << ", size " << q.size() << '\n';
    return 0;
}

front 10, back 30, size 3
front 20, back 30, size 2
front 20, back 40, size 3

Call-গুলো stack-এর program-এরই, শুধু top-এর জায়গায় front আর back। অথচ pop এবার নিল 10, 30 না। Module 4 বলেছিল, queue-এর নড়াচড়া তিনটা: পেছনে push, সামনে দেখা, সামনে থেকে pop। back() হলো আরেকটা দেখা, ও কখনো কিছু নড়ায় না। তাই queue-এ pop সবসময় নেয় সেই element-টাকে, যে সবচেয়ে বেশিক্ষণ অপেক্ষা করেছে।

pop কিছুই ফেরত দেয় না: আগে পড়ো, তারপর pop

Bob এক লাইনেই top-এর মানটা নিতে আর সেটা সরাতে চায়, তাই ও লেখে এটা।

stack<int> s;
s.push(4);
int x = s.pop();

Runner-এর flag-এ GCC 12 থেমে যায় error: void value not ignored as it ought to be দিয়ে। void মানে "কোনো মান না": pop() element-টা সরায়, কিন্তু হাতে কিছুই ফেরত দেয় না। Queue-এর pop()-এর বেলাতেও একই কথা। Library কেন এভাবে বানানো, সেটা বলবে lesson 05। সমাধান দুই লাইনের: আগে একটা read, তারপর একটা pop।

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(4);
    s.push(9);
    int x = s.top();
    s.pop();
    cout << "took " << x << ", now the top is " << s.top() << '\n';
    return 0;
}

took 9, now the top is 4

Queue-এ idiom-টা একই, শুধু top()-এর জায়গায় front()। তাই প্রায় প্রতিটা stack বা queue program-এ তুমি এই জোড়াটা লিখবে: আগে দেখা, তারপর pop।

খালি adaptor: Zara-র প্রথম test

Zara সবসময় খালি case আগে চালায়। ও একটা খালি stack-কে ওর top থালার কথা জিজ্ঞেস করে।

stack<int> plates;
cout << "top plate: " << plates.top() << '\n';

Runner-এর flag-এ এটা কোনো বার্তা ছাড়াই compile হয়েছে। Compiler Explorer-এর GCC 12.2-এ একবার চালাতে program কিছুই print করেনি, crash করেছে SIGSEGV দিয়ে, যে signal আসে নিজের না এমন memory পড়তে গেলে। এমনকি top plate: কথাগুলোও আসেনি, কারণ crash-এর সময় ওগুলো তখনো cout-এর কাছেই ধরা ছিল। তারপর ও একটা খালি queue-কে ওর front জিজ্ঞেস করে। সেবার print হয়েছে first in line: 0, আর program স্বাভাবিকভাবেই শেষ হয়েছে।

দুটোই undefined behaviour: কী হবে, C++ standard কিছুই বলে না। তাই এক run crash করে, আরেক run এমন একটা 0 print করে, যেটা কোনো customer না। খালি adaptor-এ pop()-ও undefined। তাই যে top(), front(), back() বা pop()-এর input তোমার হাতে নেই, তার আগে প্রতিবার if (!s.empty()) লেখো।

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        cout << "pop " << s.top() << '\n';
        s.pop();
    }
    return 0;
}

pop 3
pop 2
pop 1

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    while (!q.empty()) {
        cout << "pop " << q.front() << '\n';
        q.pop();
    }
    return 0;
}

pop 1
pop 2
pop 3

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> changes;
    changes.push("typed a paragraph");
    changes.push("made a word bold");
    changes.push("deleted a line");

    for (int press = 1; press <= 2; press++) {
        cout << "undo: " << changes.top() << '\n';
        changes.pop();
    }
    cout << "next undo would take back: " << changes.top() << '\n';
    cout << changes.size() << " change left\n";
    return 0;
}

undo: deleted a line
undo: made a word bold
next undo would take back: typed a paragraph
1 change left

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> line;
    for (int ticket = 101; ticket <= 104; ticket++) {
        line.push(ticket);
    }
    cout << line.size() << " waiting, front " << line.front() << ", back " << line.back() << '\n';

    for (int served = 0; served < 2; served++) {
        cout << "serving ticket " << line.front() << '\n';
        line.pop();
    }
    line.push(105);
    cout << line.size() << " waiting, front " << line.front() << ", back " << line.back() << '\n';
    return 0;
}

4 waiting, front 101, back 104
serving ticket 101
serving ticket 102
3 waiting, front 103, back 105

stack<int> s;
s.push_back(5);

stack<int> s;
s.push(4);
s.push(9);
s.pop();
cout << "took " << s.top() << '\n';

#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    q.push(5);
    cout << q.front() << '\n';
    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    queue<int> q;
    s.push(1);
    s.push(2);
    s.pop();
    s.push(3);
    q.push(1);
    q.push(2);
    q.pop();
    q.push(3);
    cout << s.top() << ' ' << q.front() << '\n';
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    queue<string> line;
    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "join") {
            string name;
            cin >> name;
            // Add name at the back of line.
        } else {
            // op is "serve": print the name at the front and remove it,
            // or print nobody if line is empty.
        }
    }

    // Print the names still waiting, front to back, separated by single
    // spaces, or the word empty if nobody is left.

    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string word;
        cin >> word;
        stack<char> from_end;
        queue<char> from_start;
        // Push every letter of word into both containers.
        // Then compare from_end.top() with from_start.front(), pop both,
        // and repeat until they are empty. Print yes or no.
    }
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    stack<int> pile;
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        pile.push(w);
    }

    stack<int> sorted;
    // Move crates one at a time until pile is empty, so that every crate
    // in sorted sits on a heavier or equal one. You may hold one crate in
    // a variable, and you may move crates from sorted back onto pile.
    // Then print sorted from its top to its bottom.

    return 0;
}

এরপর lesson 02 দুই adaptor-এরই প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ, আর ওরা যা যা করতে দেয় না, সেগুলোও।