Stack — শেষে ঢোকে, আগে বের হয়

১ · Stack কী — বিয়েবাড়ির থালার স্তূপ

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

এই নিয়মে চলা ডেটা স্ট্রাকচারের নাম stack (স্ট্যাক), আর নিয়মটির নাম LIFO — Last In, First Out. Stack-এ আপনি শুধু একটি প্রান্ত ছুঁতে পারেন, যার নাম top. মাঝের বা নিচের উপাদান সরাসরি দেখা যায় না। শুনতে সীমাবদ্ধতা মনে হয়, কিন্তু এই সীমাবদ্ধতাই stack-কে এত দ্রুত আর এত কাজের বানায়।

Stack একটি abstract data type (ADT): এটি বলে কী কাজ করা যায়, কীভাবে বানানো হবে তা বলে না। কাজগুলো মাত্র চারটি (সাথে প্রায়ই একটি পঞ্চম):

খেয়াল করুন, “৫ নম্বর উপাদানটি দেখাও” বা “৪২ কোথায় আছে খোঁজো” — এমন কাজ stack-এর তালিকায় নেই। দরকার হলে সেটি অন্য ডেটা স্ট্রাকচারের কাজ (অ্যারে, পর্ব ১০; hash table, পর্ব ৩২)। Stack যা কথা দেয়, তা খুব কম — কিন্তু সেগুলো সবই ধ্রুবক সময়ে, ইনপুট যত বড়ই হোক।

২ · নিজে বানানো — array/vector আর linked list

ADT একটি চুক্তি; এবার সেটি পূরণ করার দুটি প্রচলিত উপায় দেখি।

উপায় ১: Array বা vector-এর শেষ প্রান্ত = top

একটি অ্যারে আর একটি সংখ্যা top রাখুন, যা বলে ওপরের উপাদান কোন ঘরে আছে (খালি হলে −1). push মানে top এক বাড়িয়ে সেই ঘরে লেখা; pop মানে শুধু top এক কমানো। কোনো উপাদান সরাতে হয় না, কোনো লুপ নেই — তাই প্রতিটি কাজ O(1). নিচে ৪ ঘরের একটি অ্যারেতে কয়েকটি অপারেশন দেখুন:

নির্দিষ্ট মাপের অ্যারের সমস্যা হলো overflow. সমাধান dynamic array (C++-এর std::vector, Python-এর list) — জায়গা ফুরোলে দ্বিগুণ মাপের নতুন অ্যারে নিয়ে সব কপি করে (পর্ব ১০)। সেই কপির মুহূর্তে একটি push O(n) নেয়, কিন্তু n টি push-এ মোট কপি হয় 2n-এর কম, তাই গড়ে প্রতিটি push amortized O(1). এই কারণেই বাস্তবে stack মানে প্রায় সবসময় একটি vector, যার শেষ প্রান্তটি top: push_back = push, pop_back = pop, back() = top.

উপায় ২: Linked list-এর মাথা = top

প্রতিটি উপাদান একটি node, যাতে থাকে মান আর তার নিচের node-এর ঠিকানা। linked list-এর মাথায় (head) নতুন node বসানো আর মাথা থেকে node সরানো — দুটোই কয়েকটি pointer বদলের কাজ (পর্ব ১২). তাই এখানে প্রতিটি কাজ worst case-এও O(1), amortized নয়।

// stack on a singly linked list: head = top
struct Node { int val; Node* next; };

struct ListStack {
    Node* head = nullptr;
    void push(int x) { head = new Node{x, head}; }     // new node points to old top
    void pop() { Node* t = head; head = head->next; delete t; }  // caller checks empty()
    int top() const { return head->val; }
    bool empty() const { return head == nullptr; }
    ~ListStack() { while (!empty()) pop(); }           // free every node
};

দুটি উপায়েই মোট জায়গা Θ(n), আর কোনো অপারেশনের জন্য বাড়তি auxiliary space লাগে না।

৩ · তৈরি stack — std::stack, Python list আর call stack

কনটেস্ট বা কাজের কোডে নিজে stack বানানোর দরকার কমই পড়ে; ভাষার লাইব্রেরিতে তৈরি আছে। তবে প্রতিটির কিছু ফাঁদ আছে।

#include <stack>
std::stack<int> st;          // default container: std::deque<int>
st.push(10); st.push(20);
int x = st.top();             // 20 -- read first...
st.pop();                     // ...then remove; pop() returns void
if (!st.empty()) { /* top()/pop() only on a non-empty stack */ }
std::stack<int, std::vector<int>> fast;   // vector as the container

st = []                 # a plain list is the standard Python stack
st.append(10)           # push   -- amortized O(1)
st.append(20)
x = st[-1]              # top    -- 20
x = st.pop()            # pop    -- removes AND returns 20
if st:                  # non-empty check
    print(st[-1])
# never: st.pop(0) or st.insert(0, v) -- those shift every element, O(n)

যে stack আপনি না জেনেই প্রতিদিন ব্যবহার করেন

পর্ব ০৭-এ দেখেছেন, প্রতিটি ফাংশন কল call stack-এ একটি নতুন stack frame push করে, আর ফাংশন শেষ হলে সেটি pop হয়। কেন stack-ই? কারণ ফাংশনগুলো ঠিক LIFO নিয়মে শেষ হয়: main ডাকল f-কে, f ডাকল g-কে — তাহলে g শেষ না হওয়া পর্যন্ত f শেষ হতে পারে না। সবচেয়ে সাম্প্রতিক অসমাপ্ত কাজটিই সবার আগে শেষ হয়। এই বাক্যটি মনে রাখুন; পুরো পর্বে stack-এর প্রতিটি ব্যবহারে এটিই ঘুরে ফিরে আসবে।

৪ · বন্ধনী মেলানো — প্রথম ক্লাসিক প্রয়োগ

Code editor আপনার {-এর জোড়া } কোথায়, তা রং দিয়ে দেখায়; compiler বলে দেয় “expected ‘)’”. এর পেছনে আছে stack. প্রশ্নটি হলো: একটি লেখায় বন্ধনীগুলো কি ঠিকঠাক মিলেছে? [()]{} ঠিক; ([)] ভুল (গোল বন্ধনী খুলে তার ভেতরে বন্ধ হয়েছে চারকোনা — একে অপরকে কেটে গেছে); (( ভুল (বন্ধ হয়নি)।

শুধু গোনা যথেষ্ট নয় — ([)]-এ প্রতিটি ধরনের খোলা আর বন্ধ সংখ্যায় সমান, তবু ভুল। আসল নিয়ম: প্রতিটি বন্ধ বন্ধনী মিলবে সবচেয়ে সাম্প্রতিক এখনো-খোলা বন্ধনীর সাথে। “সবচেয়ে সাম্প্রতিক” শব্দটিই stack-এর ইঙ্গিত। অ্যালগরিদম:

1. বাঁ থেকে ডানে প্রতিটি অক্ষর পড়ুন। খোলা বন্ধনী (( [ {) হলে push.
2. বন্ধ বন্ধনী হলে: stack খালি হলে ভুল (বন্ধ করার কিছু নেই)। নইলে top একই ধরনের খোলা বন্ধনী কি না দেখুন — হলে pop, না হলে ভুল।
3. অন্য অক্ষর (অক্ষর, সংখ্যা, operator) উপেক্ষা করুন।
4. শেষে stack খালি হলে balanced, নইলে কিছু বন্ধনী খোলা থেকে গেছে।

কেন এটি ঠিক — একটি invariant. দাবি: যেকোনো অংশ পড়ার পর stack-এ ঠিক সেই খোলা বন্ধনীগুলো আছে, যেগুলো এখনো বন্ধ হয়নি, যে ক্রমে খুলেছে সেই ক্রমে (ওপরে সবচেয়ে নতুনটি)। শুরুতে এটি সত্য (কিছু পড়িনি, stack খালি)। খোলা বন্ধনী push করলে সত্য থাকে। বন্ধ বন্ধনী আসলে বৈধ লেখায় এটিকে অবশ্যই সবচেয়ে নতুন খোলা বন্ধনীর জোড়া হতে হবে — কারণ তার পরে খোলা কোনোটি বন্ধ না করে আগেরটি বন্ধ করলে দুটি জোড়া একে অপরকে কাটত। তাই top-এর সাথে মেলানোই সঠিক পরীক্ষা, আর pop করলে invariant বজায় থাকে। শেষে লেখা balanced হবে ঠিক তখনই, যখন কোনো বন্ধনী খোলা নেই — অর্থাৎ stack খালি। এটি পর্ব ০৩-এর loop invariant পদ্ধতিরই প্রয়োগ।

বিশ্লেষণ: প্রতিটি অক্ষরে সর্বোচ্চ একটি push বা একটি pop, প্রতিটি O(1) — তাই সময় Θ(n). জায়গা worst case Θ(n), যেমন (((((( ইনপুটে। শুধু এক ধরনের বন্ধনী হলে stack-এর দরকারই নেই — একটি counter যথেষ্ট (কখনো ঋণাত্মক হবে না, শেষে শূন্য)। ধরন একাধিক হলেই stack লাগে, কারণ তখন শুধু সংখ্যা নয়, কোনটি খোলা আছে তা-ও মনে রাখতে হয়।

৫ · Infix থেকে postfix — Dijkstra-র Shunting-yard

আমরা লিখি a + b * (c - d) - e — operator দুটি সংখ্যার মাঝখানে। একে বলে infix notation. মানুষের পড়তে সুবিধা, কিন্তু কম্পিউটারের জন্য ঝামেলা: + দেখেই যোগ করা যায় না, কারণ পরে * আসতে পারে যা আগে হিসাব হবে। বন্ধনী থাকলে আরও জটিল।

বিকল্প হলো postfix notation — operator বসে তার দুটি operand-এর পরে: a b c d - * + e -. একে Reverse Polish Notation (RPN)-ও বলে, কারণ পোলিশ যুক্তিবিদ Jan Łukasiewicz ১৯২০-এর দশকে operator-কে আগে বসানোর (prefix) পদ্ধতি দিয়েছিলেন; postfix হলো তার উল্টো। Postfix-এ বন্ধনী লাগে না, precedence-এর নিয়মও লাগে না — যে ক্রমে লেখা, সেই ক্রমেই হিসাব।

Shunting-yard দুটি নিয়ম মেনে চলে। প্রথম, operator precedence: কোন operator আগে। দ্বিতীয়, associativity: একই precedence-এর দুটি পাশাপাশি থাকলে কোনটি আগে।

Pseudocode — Shunting-yard (infix tokens -> postfix list)

for each token t, left to right:
    if t is an operand:      append t to OUTPUT
    else if t == "(":        push t
    else if t == ")":        pop operators to OUTPUT until "(" is on top; pop "(" (discard)
    else (t is an operator):
        while top is an operator o and
              ( prec(o) > prec(t)  or  (prec(o) == prec(t) and t is left-assoc) ):
            pop o to OUTPUT
        push t
at the end: pop every remaining operator to OUTPUT

সহজ ভাষায়: নতুন operator আসার আগে stack থেকে সেই operator-গুলো বের করে দিন, যারা নতুনটির আগে হিসাব হওয়ার কথা — বেশি precedence-এর, অথবা সমান precedence-এর (যদি নতুনটি বাঁ-associative হয়)। ( একটি দেয়াল: এর নিচে কেউ যায় না, যতক্ষণ না ) আসে। এবার a + b * (c - d) - e ধাপে ধাপে দেখুন:

বিশ্লেষণ: প্রতিটি token ঠিক একবার output-এ যায় বা একবার push হয়, আর প্রতিটি push করা operator সর্বোচ্চ একবার pop হয়। ভেতরের while লুপ থাকলেও মোট pop ≤ মোট push ≤ n, তাই সময় Θ(n), জায়গা O(n). এই “প্রতিটি উপাদান একবার ঢোকে, একবার বেরোয়” যুক্তিটি অংশ ৮-এ আবার আসবে, আরও জোরালোভাবে।

৬ · Postfix-এর হিসাব — একটি stack, একবার পড়া

Postfix পেলে মান বের করা আশ্চর্য রকম সহজ। বাঁ থেকে ডানে পড়ুন: সংখ্যা হলে push; operator হলে ওপরের দুটি সংখ্যা pop করে হিসাব করুন, ফল push. শেষে stack-এ একটিই সংখ্যা থাকবে — সেটিই উত্তর। একটি সূক্ষ্ম বিষয়: প্রথমে যেটি pop হয় সেটি ডান operand. 8 2 --এ আগে বেরোয় 2, তারপর 8 — হিসাব 8 − 2, 2 − 8 নয়।

প্রতিটি token-এ O(1) কাজ, তাই সময় Θ(n), জায়গা O(n). শেষে stack-এ একের বেশি সংখ্যা থাকলে, বা কোনো operator-এর সময় দুটি সংখ্যা না পেলে — expression-টিই ভুল লেখা। এবার বন্ধনী মেলানো আর postfix হিসাব একসাথে চালিয়ে দেখুন:

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>
#include <initializer_list>
using namespace std;
bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);   // opener: wait for its partner
        else if (c == ')' || c == ']' || c == '}') {
            char want = c == ')' ? '(' : c == ']' ? '[' : '{';
            if (st.empty() || st.top() != want) return false; // nothing to close, or wrong kind
            st.pop();
        }
    }
    return st.empty();                                        // leftover openers = unbalanced
}
long long evalPostfix(const string& expr) {
    stack<long long> st;
    istringstream in(expr);
    for (string tok; in >> tok; ) {
        if (isdigit((unsigned char)tok[0])) { st.push(stoll(tok)); continue; }
        long long b = st.top(); st.pop();                     // right operand comes out first
        long long a = st.top(); st.pop();
        st.push(tok == "+" ? a + b : tok == "-" ? a - b : tok == "*" ? a * b : a / b);
    }
    return st.top();
}
int main() {
    for (string s : {"[()]{}", "([)]", "((", "a*(b+c)"})
        cout << s << " -> " << (balanced(s) ? "balanced" : "NOT balanced") << '\n';
    for (string e : {"5 1 2 + 4 * + 3 -", "2 3 + 4 *", "8 2 - 3 -"})
        cout << e << " = " << evalPostfix(e) << '\n';
}

[()]{} -> balanced
([)] -> NOT balanced
(( -> NOT balanced
a*(b+c) -> balanced
5 1 2 + 4 * + 3 - = 14
2 3 + 4 * = 20
8 2 - 3 - = 3

PAIR = {')': '(', ']': '[', '}': '{'}

def balanced(s):
    st = []
    for c in s:
        if c in '([{':
            st.append(c)                     # opener: wait for its partner
        elif c in PAIR:
            if not st or st[-1] != PAIR[c]:  # nothing to close, or wrong kind
                return False
            st.pop()
    return not st                            # leftover openers = unbalanced

def eval_postfix(expr):
    st = []
    for tok in expr.split():
        if tok.isdigit():
            st.append(int(tok))
            continue
        b = st.pop()                         # right operand comes out first
        a = st.pop()
        if tok == '+': st.append(a + b)
        elif tok == '-': st.append(a - b)
        elif tok == '*': st.append(a * b)
        else: st.append(int(a / b))          # truncate like C++
    return st[-1]

for s in ["[()]{}", "([)]", "((", "a*(b+c)"]:
    print(f"{s} -> {'balanced' if balanced(s) else 'NOT balanced'}")
for e in ["5 1 2 + 4 * + 3 -", "2 3 + 4 *", "8 2 - 3 -"]:
    print(f"{e} = {eval_postfix(e)}")

[()]{} -> balanced
([)] -> NOT balanced
(( -> NOT balanced
a*(b+c) -> balanced
5 1 2 + 4 * + 3 - = 14
2 3 + 4 * = 20
8 2 - 3 - = 3

৭ · আরও প্রয়োগ — undo/redo, back বোতাম আর DFS

Undo আর redo — দুটি stack

Word-এ লিখছেন, ভুল করে একটি অনুচ্ছেদ মুছে ফেললেন, Ctrl+Z চাপলেন। সবচেয়ে শেষের কাজটিই ফিরে আসে — LIFO. Undo/redo-এর নকশা দুটি stack দিয়ে:

• নতুন কাজ করলে সেটি undoStack-এ push, আর redoStack খালি করে দিন (নতুন পথ শুরু হলো, পুরোনো “ভবিষ্যৎ” আর বৈধ নয়)।
• Undo: undoStack থেকে pop করে কাজটি উল্টে দিন, তারপর সেটি redoStack-এ push.
• Redo: redoStack থেকে pop করে আবার করুন, তারপর undoStack-এ push.

প্রতিটি কাজ O(1) (কাজটি উল্টানোর নিজের খরচ বাদে)। বাস্তব editor-গুলো সাধারণত undoStack-এর সর্বোচ্চ আকার বেঁধে দেয় — যেমন শেষ কয়েকশো কাজ — যাতে মেমরি অসীম না বাড়ে।

ব্রাউজারের back আর forward

একই নকশা। আপনি bKash-এর ওয়েবসাইট থেকে “অফার” পেজে, সেখান থেকে একটি অফারের বিস্তারিত পেজে গেলেন। প্রতিটি নতুন পেজে যাওয়ার সময় আগের পেজ back stack-এ push হয় আর forward stack খালি হয়। Back চাপলে বর্তমান পেজ forward-এ push, back থেকে pop করা পেজ খোলে। Forward ঠিক উল্টো। এজন্যই back চেপে পেছনে গিয়ে নতুন কোনো লিংকে ক্লিক করলে forward বোতাম ধূসর হয়ে যায়।

Explicit stack দিয়ে DFS — পর্ব ৪১-এর আভাস

একটি গোলকধাঁধা বা গ্রাফে DFS (depth-first search) একটি পথ ধরে যতদূর যাওয়া যায় যায়, আটকে গেলে সবচেয়ে সাম্প্রতিক মোড়ে ফিরে অন্য পথ ধরে। “সবচেয়ে সাম্প্রতিক মোড়” — আবার stack. রিকার্শন দিয়ে লিখলে call stack এই কাজ করে; কিন্তু পর্ব ০৭-এ দেখেছেন, ১০^৫ গভীরতায় সেটি stack overflow ঘটাতে পারে। তখন নিজের stack রাখুন:

// iterative DFS: our own stack instead of the call stack
vector<bool> seen(n, false);
vector<int> st{start};
while (!st.empty()) {
    int u = st.back(); st.pop_back();
    if (seen[u]) continue;
    seen[u] = true;                       // visit u
    for (int v : adj[u])
        if (!seen[v]) st.push_back(v);    // the last pushed neighbour is explored first
}

প্রতিটি vertex একবার visit হয়, প্রতিটি edge থেকে সর্বোচ্চ একবার push — তাই সময় O(V + E), যেখানে V = vertex আর E = edge-এর সংখ্যা। (directed গ্রাফে push সর্বোচ্চ E বার, undirected-এ 2E বার — দুটোই O(E).) এখানে stack বদলে queue দিলে একই কাঠামো হয়ে যায় BFS (পর্ব ৪০) — ডেটা স্ট্রাকচার বদলালেই অ্যালগরিদমের চরিত্র বদলায়। বিস্তারিত — visit-এর ক্রম, রিকার্সিভ DFS-এর সাথে সূক্ষ্ম পার্থক্য, আর প্রয়োগ — পর্ব ৪১-এ।

৮ · Monotonic stack — ডানে প্রথম বড় সংখ্যা

এবার একটি সমস্যা, যা ইন্টারভিউ আর কনটেস্টে অসংখ্যবার আসে। একটি অ্যারে দেওয়া আছে; প্রতিটি উপাদানের জন্য বের করুন, তার ডান দিকে প্রথম কোন উপাদানটি তার চেয়ে বড় — না থাকলে −1. একে বলে next greater element (NGE). [2, 7, 3, 5, 4, 6, 8]-এর উত্তর [7, 8, 5, 6, 6, 8, -1].

সরল সমাধান: প্রতিটি i-এর জন্য ডানে হেঁটে প্রথম বড়টি খুঁজুন — worst case O(n²) (যেমন কমতে থাকা অ্যারেতে)। n = 10⁵ হলে প্রায় ৫০০ কোটি তুলনা, সময়সীমা পার।

চালাক সমাধান: বাঁ থেকে ডানে যান, আর একটি stack-এ রাখুন সেই index-গুলো যাদের উত্তর এখনো পাওয়া যায়নি। নতুন উপাদান x এলে, stack-এর ওপরে যতক্ষণ x-এর চেয়ে ছোট মান আছে, ততক্ষণ সেগুলো pop করুন — তাদের সবার উত্তর x. তারপর x-এর index push করুন। ফলে stack-এর মানগুলো নিচ থেকে ওপরে সবসময় কমতে থাকে (বা সমান থাকে) — এজন্যই নাম monotonic stack. একটি উপমা: স্কুলের মাঠে ছাত্রেরা একে একে লাইনে এসে দাঁড়াচ্ছে, আর প্রত্যেকে জানতে চায় তার পরে আসা প্রথম কোন জন তার চেয়ে লম্বা। একজন লম্বা ছাত্র এলে, অপেক্ষায় থাকা তার চেয়ে খাটো সবাই একসাথে উত্তর পেয়ে যায় — আর অপেক্ষার তালিকা থেকে বেরিয়ে যায়।

শুদ্ধতা। Invariant: stack-এ ঠিক সেই index-গুলো আছে যাদের ডানে এখনো বড় কেউ আসেনি, আর তাদের মান নিচ থেকে ওপরে কমে বা সমান থাকে। x যখন index j-কে pop করে, তখন x-ই j-এর প্রথম বড় — কারণ j আর i-এর মাঝের যেকোনো উপাদান a[j]-এর চেয়ে বড় হলে সে আগেই j-কে pop করে ফেলত। আর stack-এ x-এর চেয়ে বড় বা সমান মান পেলেই থামা নিরাপদ: monotonic ক্রমের কারণে তার নিচের সবাই আরও বড় বা সমান, তাদের কারও উত্তর x নয়।

কেন O(n) — amortized যুক্তি। কোডে for-এর ভেতরে while — দেখে O(n²) মনে হয়। কিন্তু হিসাবটা অন্যভাবে করুন: প্রতিটি index ঠিক একবার push হয়, আর pop হলে আর কখনো ফেরে না — তাই সর্বোচ্চ একবার pop. পুরো চলায় while-এর মোট ঘূর্ণন = মোট pop ≤ n. ফলে মোট কাজ ≤ n (push) + n (pop) + n (for-এর তুলনা যা থামায়) = O(n). একটি নির্দিষ্ট ধাপে অনেক pop হতে পারে (ধাপ ৬, ৭), কিন্তু সেই খরচ আগের push-গুলো আগেই “জমা” রেখেছিল। এটিই amortized analysis-এর aggregate পদ্ধতি; পর্ব ৬০-এ এটিকে potential function (Φ = stack-এর আকার) দিয়ে নিখুঁতভাবে প্রমাণ করা হবে। জায়গা O(n).

#include <iostream>
#include <vector>
#include <initializer_list>
using namespace std;

vector<int> nextGreater(const vector<int>& a, int& pops) {
    vector<int> ans(a.size(), -1);
    vector<int> st;                       // indices still waiting; values decrease upward
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!st.empty() && a[st.back()] < a[i]) {
            ans[st.back()] = a[i];        // a[i] is the first greater value to the right
            st.pop_back();
            ++pops;
        }
        st.push_back(i);
    }
    return ans;
}

int main() {
    for (const vector<int>& a : {vector{2, 7, 3, 5, 4, 6, 8}, vector{5, 4, 3, 2, 1},
                                 vector{1, 2, 3, 4, 5}}) {
        int pops = 0;
        vector<int> ans = nextGreater(a, pops);
        cout << "a   ="; for (int x : a) cout << ' ' << x;
        cout << "\nnge ="; for (int x : ans) cout << ' ' << x;
        cout << "\npushes = " << a.size() << ", pops = " << pops << '\n';
    }
}

a   = 2 7 3 5 4 6 8
nge = 7 8 5 6 6 8 -1
pushes = 7, pops = 6
a   = 5 4 3 2 1
nge = -1 -1 -1 -1 -1
pushes = 5, pops = 0
a   = 1 2 3 4 5
nge = 2 3 4 5 -1
pushes = 5, pops = 4

def next_greater(a):
    ans = [-1] * len(a)
    st = []                    # indices still waiting; values decrease upward
    pops = 0
    for i, x in enumerate(a):
        while st and a[st[-1]] < x:
            ans[st.pop()] = x  # x is the first greater value to the right
            pops += 1
        st.append(i)
    return ans, pops

for a in [[2, 7, 3, 5, 4, 6, 8], [5, 4, 3, 2, 1], [1, 2, 3, 4, 5]]:
    ans, pops = next_greater(a)
    print("a   =", *a)
    print("nge =", *ans)
    print(f"pushes = {len(a)}, pops = {pops}")

a   = 2 7 3 5 4 6 8
nge = 7 8 5 6 6 8 -1
pushes = 7, pops = 6
a   = 5 4 3 2 1
nge = -1 -1 -1 -1 -1
pushes = 5, pops = 0
a   = 1 2 3 4 5
nge = 2 3 4 5 -1
pushes = 5, pops = 4

একই ছাঁচ: stock span

Stock span সমস্যা: প্রতিদিনের শেয়ার-দাম দেওয়া আছে। প্রতিটি দিনের “span” মানে আজসহ পরপর কতদিন (পেছন দিকে) দাম আজকের সমান বা কম ছিল। দাম [100, 80, 60, 70, 60, 75, 85] হলে span [1, 1, 1, 2, 1, 4, 6]. এটি আসলে “বাঁ দিকে প্রথম বড়” খোঁজা: বাঁয়ে সবচেয়ে কাছের যে দিনের দাম আজকের চেয়ে বেশি, তার index p হলে span = i − p (না থাকলে i + 1).

Pseudocode — stock span (0-based)

st = empty stack of indices        // prices on the stack strictly decrease upward
for i = 0 .. n-1:
    while st not empty and price[top(st)] <= price[i]:
        pop(st)                    // those days can never block a later day
    span[i] = (st empty) ? i + 1 : i - top(st)
    push(st, i)

হাতে দেখুন দিন ৫ (দাম 75): stack-এ তখন দিন 0, 1, 3, 4 (দাম 100, 80, 70, 60). 60 আর 70 pop হয়, top-এ থামে দিন 1 (80 > 75) — span = 5 − 1 = 4. pop হওয়া দিনগুলো আর কখনো লাগবে না: পরের যেকোনো দিনের জন্য 75 তাদের চেয়ে বড় বা সমান, আর 75 তাদের চেয়ে ডানে। একই amortized যুক্তিতে সময় O(n).

৯ · Histogram-এর সবচেয়ে বড় আয়তক্ষেত্র আর min-stack

Largest rectangle in a histogram — O(n)

পাশাপাশি কয়েকটি ১ চওড়া স্তম্ভ, উচ্চতা [2, 1, 5, 6, 2, 3]. এদের ভেতরে আঁকা যায় এমন সবচেয়ে বড় আয়তক্ষেত্র কত? (ঢাকার রাস্তার পাশে বিভিন্ন উচ্চতার দালানের সারি ভাবুন — সবচেয়ে বড় আয়তাকার বিলবোর্ড, যা দালানগুলোর গায়ে লাগিয়ে রাখা যায়।) উত্তর 10: উচ্চতা 5 আর 6-এর দুটি স্তম্ভ জুড়ে, উচ্চতা 5, চওড়া 2. এটি largest rectangle in a histogram সমস্যা।

মূল পর্যবেক্ষণ: সবচেয়ে বড় আয়তক্ষেত্রের উচ্চতা অবশ্যই কোনো একটি স্তম্ভ j-এর উচ্চতা h[j] (নইলে আরও উঁচু করা যেত)। স্তম্ভ j-কে “সবচেয়ে নিচু” ধরে আয়তক্ষেত্রটি দুই দিকে ছড়ায় যতক্ষণ না h[j]-এর চেয়ে নিচু স্তম্ভে ধাক্কা লাগে। তাই প্রতিটি j-এর জন্য দরকার বাঁ দিকে প্রথম ছোট (L) আর ডান দিকে প্রথম ছোট (R) — চওড়া = R − L − 1. এটি NGE-রই আয়না-রূপ, আর একটি monotonic stack একবারের যাত্রায় দুটোই দেয়: stack-এ উচ্চতা নিচ থেকে ওপরে বাড়ে; নতুন স্তম্ভ i ছোট হলে top j pop হয় — তখন ডানের প্রথম ছোট R = i, আর pop-এর পর নতুন top-ই বাঁয়ের প্রথম ছোট L.

Pseudocode — largest rectangle (0-based; h[n] = 0 is a sentinel that empties the stack)

best = 0; st = empty stack of indices     // heights on the stack increase upward
for i = 0 .. n:
    cur = (i == n) ? 0 : h[i]
    while st not empty and h[top(st)] > cur:
        j = pop(st)                        // first smaller to the right of j is i
        L = (st empty) ? -1 : top(st)      // first smaller to the left of j
        best = max(best, h[j] * (i - L - 1))
    push(st, i)
return best

কেন O(n): সরল পদ্ধতিতে প্রতিটি j থেকে দুই দিকে হেঁটে O(n²). এখানে আবার সেই হিসাব — প্রতিটি index (sentinel-সহ n + 1 টি) ঠিক একবার push, সর্বোচ্চ একবার pop, আর প্রতিটি pop-এ O(1) কাজ (একটি গুণ, একটি তুলনা)। while লুপের মোট ঘূর্ণন ≤ n, তাই সারা অ্যালগরিদম Θ(n), জায়গা O(n). শুদ্ধতার যুক্তি: প্রতিটি j pop-এর মুহূর্তে তার আসল L ও R জানা থাকে, তাই প্রতিটি “j সবচেয়ে নিচু” আয়তক্ষেত্র ঠিক একবার পরীক্ষা হয় — আর সর্বোচ্চটি এদেরই একটি। সমান উচ্চতা থাকলে (যেমন [3, 3]) শেষের 3-এর জন্য হিসাব কম আসে (চওড়া 1), কিন্তু প্রথম 3 pop হওয়ার সময় পুরো চওড়া (2) পায় — তাই > লিখলেও সর্বোচ্চ ঠিক থাকে।

Min-stack — সর্বনিম্ন মানও O(1)-এ

এমন একটি stack চাই যা push, pop, top-এর সাথে getMin()-ও O(1)-এ দেয়। একটি min ভ্যারিয়েবল রাখলে pop-এর সময় বিপদ: সর্বনিম্নটি pop হয়ে গেলে নতুন সর্বনিম্ন কে, তা জানতে পুরো stack ঘাঁটতে হবে — O(n). কৌশল: প্রতিটি ঘরে মানের সাথে লিখে রাখুন “এই ঘর পর্যন্ত (নিচ থেকে) সর্বনিম্ন”। Min-stack-এর প্রতিটি ঘর তখন নিজের নিচের অংশের একটি স্থির ছবি; pop করলে নিচের ঘরের লেখা min আপনাআপনি সঠিক — কারণ সেটি লেখার সময় ওপরের কেউ ছিলই না।

struct MinStack {
    vector<pair<int,int>> st;                       // (value, min of this and everything below)
    void push(int x) { st.push_back({x, st.empty() ? x : min(x, st.back().second)}); }
    void pop()       { st.pop_back(); }
    int  top()    const { return st.back().first; }
    int  getMin() const { return st.back().second; }
};
// push 5, 3, 7, 3  -> mins 5, 3, 3, 3;  pop, pop -> getMin() = 3;  pop -> getMin() = 5

সব কাজ O(1), জায়গা 2n (প্রতি উপাদানে একটি বাড়তি সংখ্যা)। জায়গা বাঁচাতে দ্বিতীয় একটি stack-এ শুধু নতুন সর্বনিম্নগুলো (সমানসহ) রাখা যায়। একই কৌশলে max-stack, বা দুটি stack জুড়ে একটি queue বানালে “sliding window-এর সর্বনিম্ন” পাওয়া যায় (পর্ব ১৪ ও ১৬).

১০ · AI-এর যুগে stack — ছোট কোড, বড় ফাঁদ

Stack-এর কোড ছোট, তাই AI সেটি নির্ভুলভাবে লিখবে — এমন ধারণা স্বাভাবিক। বাস্তবে ছোট কোডেই ভুল লুকোতে সুবিধা: একটি < বনাম <=, দুটি pop-এর ক্রম, বা একটি খালি-যাচাই। ছোট উদাহরণে উত্তর মিলে যায়, আসল ইনপুটে নয়। আর monotonic stack-এর complexity নিয়ে AI কখনো “nested loop, তাই O(n²)” বলে, কখনো আবার প্রমাণ ছাড়াই O(n) দাবি করে — আপনাকে নিজে যুক্তিটি দিতে পারতে হবে।

Stack-এর কোডে AI সাধারণত যেসব ভুল করে

Stack-এর কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি top()/pop()-এর আগে খালি-যাচাই আছে, অথবা কেন দরকার নেই তা বলতে পারি
• Edge case চালিয়েছি: খালি ইনপুট, এক উপাদান, সব সমান, বাড়তে থাকা, কমতে থাকা
• ছোট একটি ইনপুটে খাতায় stack-এর প্রতিটি অবস্থা লিখে কোডের সাথে মিলিয়েছি
• postfix-এ 8 2 - আর 8 2 / দিয়ে operand-এর ক্রম যাচাই করেছি
• O(n²) brute force লিখে হাজারটি এলোমেলো ছোট অ্যারেতে stress testing করেছি
• pop গোনার counter দিয়ে দেখেছি মোট pop ≤ n — amortized O(n) দাবিটি শুধু বিশ্বাস নয়