স্ট্যাক ও কিউ — শেষে এসে আগে যাওয়া, আর আগে এসে আগে যাওয়া

১ · নিয়ম আর গঠন — abstract data type কী

পর্ব ৩৩-এ আপনি linked list বানিয়েছেন — pointer দিয়ে জোড়া ঘরের শিকল। আজ আমরা দুটি নতুন কাঠামো বানাব, যারা আকারে খুব সরল, কিন্তু কম্পিউটারের প্রায় প্রতিটি স্তরে কাজ করে: stack আর queue.

শুরুতেই একটি গুরুত্বপূর্ণ কথা। Stack বা queue কোনো নির্দিষ্ট কোড নয়, এটি একটি নিয়মের তালিকা। “Stack” বললে আমরা বুঝি — ওপরে রাখা যায়, ওপর থেকে তোলা যায়, ওপরেরটা দেখা যায়, আর খালি কি না জানা যায়। ব্যস। এই নিয়মগুলো কীভাবে মানা হবে — array দিয়ে, নাকি linked list দিয়ে — সেটি সম্পূর্ণ আলাদা প্রশ্ন।

যে কাঠামোকে শুধু তার নিয়ম দিয়ে চেনা হয়, তাকে বলে abstract data type (সংক্ষেপে ADT). পর্ব ২৯-এ আপনি একই ভাবনা দেখেছিলেন: header ফাইলে থাকে interface — বাইরের সবার জন্য প্রতিশ্রুতি, আর .c ফাইলে থাকে implementation — প্রতিশ্রুতি রাখার আসল কৌশল।

C-তে একটি stack-এর interface দেখতে এমন হতে পারে। পর্ব ২৯-এর opaque pointer খেয়াল করুন — ব্যবহারকারী struct-এর ভেতরে কী আছে দেখতেই পান না:

/* stack.h - the rules. Users see only this file. */
typedef struct Stack Stack;               /* opaque: fields are hidden */

Stack *stack_new(int capacity);
int    stack_push(Stack *s, int x);        /* returns 0 if full (overflow)   */
int    stack_pop(Stack *s, int *out);      /* returns 0 if empty (underflow) */
int    stack_peek(const Stack *s, int *out);
int    stack_is_empty(const Stack *s);
void   stack_free(Stack *s);

২ · Stack — শেষে যে এল, সে-ই আগে যায়

বিয়েবাড়ির বুফে টেবিলের কথা ভাবুন। পরিষ্কার থালাগুলো একটির ওপর আরেকটি সাজানো। ধোয়া থালা এলে রাখা হয় ওপরে। অতিথি থালা নেন ওপর থেকে। মাঝখান থেকে টেনে কেউ নেন না — স্তূপ ভেঙে পড়বে! ফলে যে থালাটি সবশেষে রাখা হয়েছে, সেটিই সবার আগে কারও হাতে যায়।

এই নিয়মের নাম LIFO — Last In, First Out, অর্থাৎ “শেষে এলে আগে যাবে”। আপনি প্রতিদিন এটি ব্যবহার করেন:

চারটি কাজ — এর বেশি কিছু নয়

চারটি কাজই একটিমাত্র ধাপে হয় — stack-এ এক লাখ জিনিস থাকুক বা দুটি, সময় একই। কারণ আমরা কখনো মাঝখানে হাত দিই না, শুধু ওপরে। পর্ব ৩৯-এ এর নাম শিখবেন O(1).

মেমরিতে একটি array-stack

সবচেয়ে সহজ উপায়: একটি array আর একটি পূর্ণসংখ্যা top. এখানে আমরা top-এর অর্থ ঠিক করলাম — “stack-এ কয়টি জিনিস আছে”, যা একই সাথে “পরের খালি ঘরের index”. তিনটি push-এর পর মেমরি এমন দেখায়:

index :    0      1      2      3      4
data  :  [ 10 ] [ 20 ] [ 30 ] [  ? ] [  ? ]
                                ^
                     top = 3  (৩টি আছে; পরের push যাবে ঘর ৩-এ)

struct Stack { int *data; int top; int cap; };   /* top = number of items */

int stack_push(Stack *s, int x) {
    if (s->top == s->cap) return 0;      /* overflow: refuse, never write */
    s->data[s->top++] = x;               /* write, then move top up */
    return 1;
}
int stack_pop(Stack *s, int *out) {
    if (s->top == 0) return 0;           /* underflow: nothing to give */
    *out = s->data[--s->top];            /* move top down, then read */
    return 1;
}

struct Node  { int value; struct Node *next; };
struct Stack { struct Node *head; };           /* top of stack = head of list */

int stack_push(Stack *s, int x) {
    struct Node *n = malloc(sizeof *n);
    if (n == NULL) return 0;                    /* out of memory */
    n->value = x; n->next = s->head; s->head = n;
    return 1;
}
int stack_pop(Stack *s, int *out) {
    struct Node *n = s->head;
    if (n == NULL) return 0;                    /* underflow */
    *out = n->value; s->head = n->next; free(n);
    return 1;
}

দুটি সংস্করণের stack.h হুবহু এক। যে প্রোগ্রাম stack ব্যবহার করছে, সে জানতেই পারে না ভেতরে কোনটি চলছে। এটাই ADT-র শক্তি।

৩ · বন্ধনী মেলানো — stack-এর প্রথম আসল কাজ

আপনি VS Code-এ একটি { লিখে ভুলে গেলেন বন্ধ করতে। Compiler কীভাবে টের পায়? অথবা a[f(x)] লেখার সময় editor কীভাবে বোঝে কোন ] কোন [-এর জোড়া? উত্তর: একটি stack.

নিয়মটি সহজ। বাঁ থেকে ডানে একটি একটি অক্ষর পড়ুন:

• খোলা বন্ধনী (( [ {) পেলে — push.
• বন্ধ বন্ধনী () ] }) পেলে — stack খালি হলে ভুল; না হলে pop করে মিলিয়ে দেখুন জোড়া ঠিক কি না।
• শেষে stack খালি থাকলে সব ঠিক; কিছু রয়ে গেলে কোনো বন্ধনী খোলা থেকে গেছে।

কেন stack? কারণ বন্ধনী একটির ভেতরে আরেকটি বসে। যে বন্ধনী সবশেষে খোলা হয়েছে, সেটিকেই সবার আগে বন্ধ হতে হবে — ঠিক LIFO. নিচে { [ ( ) ] ( } পরীক্ষা করা হচ্ছে। “পরে” চাপুন, আর ডান দিকে stack-এর অবস্থা দেখুন:

1for (; *s; s++) {2    char c = *s;3    if (c == '(' || c == '[' || c == '{') {4        if (top == 64) return 0;  /* overflow */5        st[top++] = c;            /* push */6    } else if (c == ')' || c == ']' || c == '}') {7        char want = ...;          /* matching opener */8        if (top == 0) return 0;   /* underflow */9        if (st[--top] != want) return 0;10    }11}12return top == 0;

এবার আসল কোডটি চালিয়ে দেখুন। একই ফাংশন পাঁচটি ভিন্ন লেখা পরীক্ষা করছে — শেষের ")(" খেয়াল করুন, এখানে প্রথম অক্ষরেই underflow:

#include <stdio.h>
int balanced(const char *s) {
    char st[64]; int top = 0;               /* the stack and its height */
    for (; *s; s++) {
        char c = *s;
        if (c == '(' || c == '[' || c == '{') {
            if (top == 64) return 0;        /* overflow */
            st[top++] = c;                  /* push */
        } else if (c == ')' || c == ']' || c == '}') {
            char want = c == ')' ? '(' : c == ']' ? '[' : '{';
            if (top == 0) return 0;         /* underflow: nothing to close */
            if (st[--top] != want) return 0; /* pop and compare */
        }
    }
    return top == 0;                        /* leftovers = unclosed */
}
int main(void) {
    const char *t[] = { "{[()]()}", "{[()](}", "(()", "a[i] = f(x);", ")(" };
    for (int i = 0; i < 5; i++) printf("%-13s -> %s\n", t[i], balanced(t[i]) ? "OK" : "ERROR");
    return 0;
}

৪ · Postfix — ক্যালকুলেটর ও compiler যেভাবে হিসাব করে

স্কুলে আমরা লিখি (5 + 3) * 2. অপারেটর বসে দুটি সংখ্যার মাঝখানে — একে বলে infix notation. মানুষের চোখে সহজ, কিন্তু কম্পিউটারের জন্য ঝামেলার: বন্ধনী আছে, আর “গুণ আগে, যোগ পরে” — এমন অগ্রাধিকারের নিয়ম (পর্ব ০৭-এর precedence) মানতে হয়।

একই হিসাব অন্যভাবে লেখা যায়: 5 3 + 2 *. এখানে অপারেটর বসে সংখ্যাগুলোর পরে — postfix notation. পড়ার নিয়ম: “দুটি সংখ্যা পেলে রেখে দাও; অপারেটর পেলে শেষ দুটি সংখ্যা নিয়ে কাজ করো।” বন্ধনীর দরকারই পড়ে না, অগ্রাধিকারের নিয়মও লাগে না। আর “শেষ দুটি সংখ্যা” রাখার জন্য সবচেয়ে মানানসই জায়গা — stack.

আজও এই ভাবনা আপনার চারপাশে কাজ করছে। Compiler প্রায়ই (5 + 3) * 2-কে ভেতরে postfix-এর মতো ক্রমে সাজায়। Java-র JVM, Python-এর CPython আর ব্রাউজারের WebAssembly — তিনটিই stack machine: এদের নির্দেশগুলো একটি stack থেকে মান তোলে, হিসাব করে, ফল আবার stack-এ রাখে। Infix থেকে postfix বানানোর বিখ্যাত পদ্ধতিটিও (Dijkstra-র “shunting-yard” অ্যালগরিদম) একটি stack দিয়েই কাজ করে।

৫ · Stack সবখানে — call stack, undo/redo আর গোলকধাঁধা

পর্ব ১৩-এ দেখেছিলেন, প্রতিটি ফাংশন ডাকলে মেমরিতে একটি stack frame ওপরে যোগ হয়, আর ফাংশন শেষ হলে সেটি সরে যায়। পর্ব ১৫-এর recursion-এ সেই frame-গুলোই একটির ওপর আরেকটি জমছিল। এটি আজকের stack-ই — শুধু CPU নিজে এটি চালায়, push/pop লাগে না, আর জায়গা ফুরিয়ে গেলে হয় stack overflow.

Undo আর Redo — দুটি stack-এর খেলা

একটি editor-এ Undo আর Redo দুটোই কীভাবে কাজ করে? উত্তর: দুটি stack. প্রতিটি নতুন কাজ যায় undo stack-এ। Undo চাপলে undo stack থেকে pop হয়ে কাজটি যায় redo stack-এ। Redo চাপলে উল্টো পথে ফেরে। নিচে দেখুন — বিশেষ করে শেষ ধাপটি, যেখানে অনেকেই অবাক হন:

আরেকটি বড় ব্যবহার সামনে আসছে। গোলকধাঁধায় পথ খোঁজার সময় আমরা একটি পথ ধরে যতদূর পারি যাই, আটকে গেলে ঠিক আগের মোড়ে ফিরে অন্য পথ ধরি। “ঠিক আগের মোড়” মনে রাখার জিনিসটি একটি stack. পর্ব ৩৮-এ এর নাম শিখবেন DFS (depth-first search), আর দেখবেন এর ভাই BFS চলে queue দিয়ে।

৬ · Queue — যে আগে এসেছে, সে আগে সেবা পাবে

ব্যাংকে ঢুকে আপনি মেশিন থেকে একটি টোকেন নিলেন — ৪৭ নম্বর। কাউন্টারে ডাকা হচ্ছে ৪২. আপনার আগে যাঁরা এসেছেন, তাঁরা আগে সেবা পাবেন; আপনার পরে যাঁরা আসবেন, তাঁরা পাবেন আপনার পরে। কেউ লাইন ভাঙলে সবাই রেগে যান — কারণ এই নিয়মটাই ন্যায্য।

এই নিয়মের নাম FIFO — First In, First Out, “আগে এলে আগে যাবে”। Queue-এর দুটি মূল কাজ:

সাধারণ array-তে queue বানালে সমস্যা কোথায়

প্রথম ভাবনা: একটি array নিই, পেছনে যোগ করি, সামনে থেকে বের করি। কিন্তু সামনে থেকে বের করার পর ঘর ০ ফাঁকা। এখন দুটি পথ — দুটিই খারাপ:

দ্বিতীয় পথটি প্রায় ঠিক। শুধু একটি কৌশল যোগ করতে হবে: শেষ ঘরের পরে আবার প্রথম ঘরে ফিরে আসা। পরের অংশে সেটিই দেখব।

৭ · Circular buffer — % দিয়ে ঘুরে আসা

দেয়ালঘড়ির কাঁটার কথা ভাবুন। ১২-এর পর ১৩ আসে না, আবার ১ আসে — কাঁটা ঘুরে শুরুতে ফেরে। Array-কেও যদি এভাবে ভাবি — শেষ ঘরের পরে আবার ঘর ০ — তাহলে সামনের ফাঁকা ঘরগুলো আবার কাজে লাগে। একে বলে circular buffer বা ring buffer.

ঘুরে আসার কাজটি করে পর্ব ০৭-এর modulus অপারেটর %: tail = (tail + 1) % CAP. ৫ ঘরের buffer-এ ঘর ৪-এর পর (4 + 1) % 5 = ০ — একদম শুরুতে ফিরে এলাম। এটি পর্ব ০৫-এর wraparound-এর মতোই, শুধু এবার আমরা ইচ্ছা করে করছি।

আমাদের queue-তে তিনটি সংখ্যা থাকবে: head (পরের dequeue কোন ঘর থেকে), tail (পরের enqueue কোন ঘরে), আর count (কয়টি আছে)। নিচের ডায়াগ্রামে খেয়াল রাখুন tail কখন ৪ থেকে ০-তে লাফ দেয়, আর শেষে কেন count ছাড়া চলত না:

1int enqueue(Queue *q, int x) {2    if (q->count == CAP) return 0;  /* full */3    q->data[q->tail] = x;4    q->tail = (q->tail + 1) % CAP;5    q->count++; return 1;6}7int dequeue(Queue *q, int *out) {8    if (q->count == 0) return 0;    /* empty */9    *out = q->data[q->head];10    q->head = (q->head + 1) % CAP;11    q->count--; return 1;12}

এবার একই queue আসল কোডে চালিয়ে দেখুন। কাজের ক্রম ঠিক উপরের ডায়াগ্রামের মতো, শেষে বাকি সবাইকে dequeue করা হচ্ছে:

#include <stdio.h>
#define CAP 5
typedef struct { int data[CAP]; int head, tail, count; } Queue;
int enqueue(Queue *q, int x) {
    if (q->count == CAP) return 0;               /* full: refuse */
    q->data[q->tail] = x;
    q->tail = (q->tail + 1) % CAP;               /* wrap around */
    q->count++; return 1;
}
int dequeue(Queue *q, int *out) {
    if (q->count == 0) return 0;                 /* empty: nothing to give */
    *out = q->data[q->head];
    q->head = (q->head + 1) % CAP;
    q->count--; return 1;
}
int main(void) {
    Queue q = { .count = 0 }; int x, v;
    for (v = 10; v <= 30; v += 10) enqueue(&q, v);
    dequeue(&q, &x); dequeue(&q, &x);            /* 10 and 20 leave */
    for (v = 40; v <= 80; v += 10) printf("enqueue %d: %s\n", v, enqueue(&q, v) ? "ok" : "FULL");
    while (dequeue(&q, &x)) printf("dequeue -> %d\n", x);
    return 0;
}

ভরা আর খালি — তিনটি প্রচলিত সমাধান

৮ · Deque, priority queue আর বাস্তবের সিস্টেম

দুই মুখ খোলা — deque

Deque (উচ্চারণ “ডেক”, double-ended queue) — সামনে-পেছনে দুই দিকেই যোগ ও বের করা যায়। শুধু এক মাথা ব্যবহার করলে এটি stack, দুই মাথা ব্যবহার করলে queue. Circular buffer দিয়েই সহজে বানানো যায় — শুধু head-কে পেছনে সরানোর সময় উপরের ঋণাত্মক ভাগশেষের সতর্কতা মানতে হবে। Python-এর collections.deque আর C++-এর std::deque এই কাঠামো। নামটি খেয়াল করুন: deque একটি কাঠামো, আর dequeue একটি কাজ — দুটি আলাদা।

আগে এলে নয়, জরুরি হলে আগে — priority queue

ঢাকা মেডিকেলের জরুরি বিভাগে কেউ টোকেনের ক্রমে সেবা পান না। হার্ট-অ্যাটাকের রোগী পরে এলেও আগে যান, হাত কেটে যাওয়া রোগী অপেক্ষা করেন। এটি priority queue — প্রতিটি মানের সাথে একটি “গুরুত্ব” থাকে, আর সবচেয়ে গুরুত্বপূর্ণটি আগে বের হয়।

সাধারণ array-তে এটি করলে প্রতিবার পুরো array খুঁজতে হয়। দ্রুত করার জন্য ব্যবহার হয় binary heap নামের একটি tree-কাঠামো (নাম এক হলেও পর্ব ২০-এর মেমরির heap এলাকার সাথে এর কোনো সম্পর্ক নেই)। পর্ব ৩৫-এ tree শেখার পর পর্ব ৩৬-এ (হিপ ও প্রায়োরিটি কিউ) এটি নিজ হাতে বানাবেন। দুটি জায়গার মধ্যে সবচেয়ে ছোট পথ খোঁজার Dijkstra অ্যালগরিদম থেকে শুরু করে OS-এর কাজ বাছাই — সবখানে priority queue.

আপনার কম্পিউটারের ভেতরে queue

সব queue-এর একটি সাধারণ বিপদ আছে: যদি জিনিস ঢোকে বের হওয়ার চেয়ে দ্রুত, তাহলে queue বাড়তেই থাকে। শেষ পর্যন্ত মেমরি শেষ, অথবা অপেক্ষার সময় অসহ্য। ভালো সিস্টেম তখন উৎসকে বলে “একটু থামো” — একে বলে backpressure. ভাবনার প্রশ্ন ০৫-এ এটি নিয়ে গভীরে যাব।

৯ · AI-এর যুগে stack ও queue

“C-তে একটা stack লিখে দাও” — যেকোনো AI দশ সেকেন্ডে কোড দেবে, আর বেশিরভাগ সময় সাধারণ ইনপুটে সেটি চলবেও। সমস্যা লুকিয়ে থাকে edge case-এ: খালি stack-এ pop, ভরা queue-তে enqueue, ঠিক শেষ ঘরে ঘুরে আসা। এগুলো সাধারণ পরীক্ষায় ধরা পড়ে না, পড়ে আসল ব্যবহারে।

AI সাধারণত যেসব ভুল করে

AI-এর লেখা stack/queue কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি push/enqueue লেখার আগে ভরা কি না যাচাই আছে
• প্রতিটি pop/peek/dequeue পড়ার আগে খালি কি না যাচাই আছে, আর ব্যর্থতা আলাদাভাবে জানানো হয় (-1 দিয়ে নয়)
• top/head/tail-এর অর্থ এক বাক্যে বলতে পারি, আর কোডের সবখানে সেই অর্থই মানা হয়েছে
• Circular buffer-এ ভরা আর খালি আলাদা করার স্পষ্ট ব্যবস্থা আছে (count, এক ঘর ফাঁকা, বা অন্য কিছু)
• নিজে চালিয়ে দেখেছি: খালি অবস্থায় বের করা, ঠিক ভরা অবস্থা, ভরার পরে আরেকটি, আর শেষ ঘর পেরিয়ে ঘুরে আসা
• একাধিক thread একই queue ব্যবহার করলে lock বা অন্য সুরক্ষা আছে কি না জিজ্ঞেস করেছি (পর্ব ৪৯-এ বিস্তারিত)