Blog

#algorithm #problem solving #programming #ডাটা স্ট্রাকচার #স্ট্যাক #স্ট্যাক ডাটা স্ট্রাকচার #stack in bangla #lifo #push pop #parentheses balance #uva 673 #call stack #postfix expression #ডাটা স্ট্রাকচার #স্ট্যাক #অ্যালগরিদম #প্রোগ্রামিং #প্রবলেম সলভিং

স্ট্যাক ডাটা স্ট্রাকচারঃ যে প্লেটটা সবার শেষে রেখেছেন, সেটাই সবার আগে উঠবে

2026-09-22 · 36 min read

স্ট্যাক ডাটা স্ট্রাকচারঃ যে প্লেটটা সবার শেষে রেখেছেন, সেটাই সবার আগে উঠবে

বিয়েবাড়ির বুফের কথা ভাবুন। টেবিলের এক কোণে প্লেট একটার ওপর আরেকটা সাজানো। খেতে এসে আপনি নিচ থেকে টেনে প্লেট বের করবেন না। করলে প্লেটের পাহাড় ধসে পড়বে আর ক্যাটারিংয়ের মামা রাগী চোখে তাকাবেন। আপনি নেবেন সবার ওপরের প্লেটটা। ধোয়া প্লেট ফেরত এলে সেটাও রাখা হবে সবার ওপরেই। অভিনন্দন, আপনি স্ট্যাক ডাটা স্ট্রাকচার এর মধ্যেই বুঝে ফেলেছেন। 

স্ট্যাক আসলে কী?

স্ট্যাক (Stack) হলো ডাটা রাখার একটা সহজ কিন্তু শক্তিশালী কাঠামো। এর মূলনীতি একটাইঃ

LIFO: Last In, First Out যে সবার শেষে ঢুকেছে, সে-ই সবার আগে বের হবে।

স্ট্যাকে সবকিছু ঘটে শুধু একটা প্রান্তে, যাকে বলে Top। মাঝখান থেকে কিছু ঢোকানো বা বের করা যায় না। করলে সেটা আর স্ট্যাক থাকে না, হয়ে যায় বিশৃঙ্খলা।

স্ট্যাকের তিনটি মূল অপারেশন

অপারেশনকাজপ্লেটের ভাষায়
push(x)নতুন এলিমেন্ট সবার ওপরে রাখেনতুন প্লেট ওপরে রাখা
pop()সবার ওপরের এলিমেন্ট সরিয়ে ফেরত দেয়ওপরের প্লেট তুলে নেওয়া
peek()সবার ওপরে কী আছে দেখায়, সরায় নাউঁকি দিয়ে দেখা, ধরা নয়

সাথে সাধারণত একটা সহায়ক ফাংশন থাকেঃ is_empty(), অর্থাৎ স্ট্যাক খালি কি না।

দুটি বিপদঃ Overflow আর Underflow

  • Stack Overflow: স্ট্যাকের ধারণক্ষমতা ১০, অথচ আপনি ১১ নম্বর এলিমেন্ট ঢোকাতে চাইছেন। জায়গা নেই, প্রোগ্রাম ক্র্যাশ করবে। (প্রোগ্রামারদের বিখ্যাত ওয়েবসাইট Stack Overflow-এর নাম এখান থেকেই এসেছে।)
  • Stack Underflow: স্ট্যাক একদম খালি, তবু pop() করতে চাইছেন। খালি টেবিল থেকে প্লেট তোলার মতো ব্যাপার, হাতে কিছুই আসবে না।

ভালো প্রোগ্রামার এই দুটো পরিস্থিতি আগে থেকেই সামলে রাখেন।

নিজের হাতে একটা স্ট্যাক বানাই (Python)

একটা নির্দিষ্ট আকারের অ্যারে নিলেই স্ট্যাক বানানো যায়। সবার ওপরের এলিমেন্টটা কোন ইনডেক্সে আছে, সেটা একটা ভ্যারিয়েবলে (top) মনে রাখলেই কাজ শেষ।

class Stack:
    def __init__(self, capacity):
        self._items = [None] * capacity
        self._top = -1  # -1 means the stack is empty

    def push(self, item):
        if self._top + 1 == len(self._items):
            raise OverflowError("Stack overflow: no space left")
        self._top += 1
        self._items[self._top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow: stack is empty")
        item = self._items[self._top]
        self._top -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[self._top]

    def is_empty(self):
        return self._top == -1


s = Stack(3)
s.push(10)
s.push(20)
print(s.peek())      # 20
print(s.pop())       # 20
print(s.is_empty())  # False

বাস্তব কাজে Python-এর সাধারণ list-ই চমৎকার স্ট্যাক। append() মানে push, pop() মানে pop, আর stack[-1] মানে peek। C++-এ আছে std::stack, Java-তে ArrayDeque, C#-এ Stack<T>। নিজে একবার বানিয়ে ভেতরের ব্যাপারটা বুঝুন, তারপর লাইব্রেরি ব্যবহার করুন।

কত দ্রুত?

push, pop, peek, is_empty: প্রতিটা অপারেশন O(1)। স্ট্যাকে এক মিলিয়ন এলিমেন্ট থাকুক বা দশটা, প্রতিটা কাজ সমান দ্রুত হবে।

স্ট্যাক কোথায় কাজে লাগে? 

১. Undo (Ctrl+Z) আর ব্রাউজারের Back বাটন

VS Code, Google Docs, Figma বা Photoshop, যেখানেই আপনি Ctrl+Z চাপেন, পেছনে সম্ভবত একটা স্ট্যাক কাজ করছে। প্রতিটা পরিবর্তন স্ট্যাকে push হয়। Undo চাপলে সবার শেষের পরিবর্তনটা pop হয়ে বাতিল হয়। ব্রাউজারের Back বাটনও একইভাবে কাজ করে। নতুন পেজে গেলে আগের পেজটা স্ট্যাকে জমা থাকে, Back চাপলে সেটা pop হয়ে ফিরে আসে।

২. কল স্ট্যাকঃ প্রোগ্রাম কীভাবে ফাংশন মনে রাখে

def func_3():
    return 42

def func_2():
    x = 20
    return x + func_3()

def func_1():
    x = 10
    return x + func_2()

print(func_1())  # 72

func_1 যখন func_2-কে ডাকে, তখন func_1-এর সব তথ্য (লোকাল ভ্যারিয়েবল, কোথায় ফিরতে হবে ইত্যাদি) একটা কল স্ট্যাকে push হয়। তারপর func_2 যখন func_3-কে ডাকে, তখন func_2-এর তথ্যও push হয়। func_3 কাজ শেষ করলে func_2 pop হয়ে আবার চালু হয়, তারপর func_1। রিকার্শন (Recursion) ঠিক এভাবেই কাজ করে। বেস কেস ভুল লিখলে ফাংশন নিজেকে অনন্তবার ডাকতে থাকে, কল স্ট্যাক ভরে যায়, আর দেখা দেয় বিখ্যাত Stack Overflow Error (Python-এ RecursionError)। 

৩. আজকের প্রযুক্তিতে স্ট্যাক

  • JVM (Java), .NET (C#), WebAssembly: এগুলো মূলত স্ট্যাক-ভিত্তিক ভার্চুয়াল মেশিন। আপনার কোড শেষ পর্যন্ত push-pop নির্দেশনায় রূপ নিয়ে চলে।
  • কম্পাইলার ও কোড এডিটরঃ VS Code যখন লাল দাগ দিয়ে দেখায় "এই ব্র্যাকেট বন্ধ হয়নি", তার পেছনে স্ট্যাক-জাতীয় লজিক থাকে।
  • নিরাপত্তাঃ হ্যাকাররা Stack Smashing বা Buffer Overflow নামে এক ধরনের আক্রমণ করে, যেখানে কল স্ট্যাকের মেমরি ওভাররাইট করা হয়। 
  • DFS, Backtracking, গোলকধাঁধা সমাধানঃ ভবিষ্যতে গ্রাফ অ্যালগরিদম শিখতে গেলে স্ট্যাক প্রায় সব জায়গায় পাবেন।

মূল সমস্যাঃ ব্র্যাকেট কি ব্যালেন্সড? (Parentheses Balance)

এটা স্ট্যাকের সবচেয়ে ক্লাসিক সমস্যা, আর ইন্টারভিউতেও খুব জনপ্রিয়।

সমস্যাটা কী?

আপনাকে শুধু ব্র্যাকেট দিয়ে তৈরি একটা স্ট্রিং দেওয়া হবে, যেমন "(({})"। বলতে হবে এটা ব্যালেন্সড কি না। একটা সিকোয়েন্স ব্যালেন্সড হবে যদি, 

  1. স্ট্রিংটা খালি হয়। খালি স্ট্রিং ব্যালেন্সড ধরা হয়।
  2. A আর B দুটোই ব্যালেন্সড হলে পাশাপাশি AB-ও ব্যালেন্সড। যেমন "(){}" আর "()" থেকে "(){}()"।
  3. S ব্যালেন্সড হলে তাকে ব্র্যাকেটে মুড়ে দিলেও ব্যালেন্সড থাকেঃ (S), {S}, [S]। যেমন "{}()" থেকে "({}())"।
স্ট্রিংব্যালেন্সড?কারণ
"(){}"হ্যাঁপ্রতিটা খোলা ব্র্যাকেট ঠিকঠাক বন্ধ হয়েছে
"({})"হ্যাঁভেতরের {} আগে বন্ধ, তারপর বাইরের ()
"(("নাকেউ বন্ধই হয়নি
"({)}"নাক্রম উল্টো, { বন্ধ হওয়ার আগেই ) চলে এসেছে
"()(}"না( বন্ধ করতে এসেছে }

মূল আইডিয়া 

খোলা ব্র্যাকেট পেলে স্ট্যাকে রাখো। বন্ধ ব্র্যাকেট পেলে দেখো স্ট্যাকের ওপরে তার জোড়া আছে কি না।

কেন স্ট্যাক? কারণ যে ব্র্যাকেট সবার শেষে খোলা হয়েছে, তাকেই সবার আগে বন্ধ করতে হয়। এটাই তো LIFO!

অ্যালগরিদম, ধাপে ধাপে

স্ট্রিংয়ের প্রতিটা ক্যারেক্টার বাম থেকে ডানে পড়ুনঃ

  1. খোলা ব্র্যাকেট (, {, [ হলে: স্ট্যাকে push করুন।
  2. বন্ধ ব্র্যাকেট ), }, ] হলেঃ
    • স্ট্যাক খালি হলেঃ ব্যালেন্সড না (বন্ধ করার মতো কেউ নেই)।
    • স্ট্যাকের ওপরেরটা এর জোড়া না হলেঃ ব্যালেন্সড না।
    • জোড়া মিললেঃ স্ট্যাক থেকে pop করুন।
  3. পুরো স্ট্রিং পড়া শেষে স্ট্যাক খালি থাকলে ব্যালেন্সড, আর কিছু থেকে গেলে ব্যালেন্সড না।

ড্রাই রানঃ "(({})"

ধাপক্যারেক্টারকী করলামস্ট্যাক (বাম = নিচ, ডান = ওপর)
১(push(
২(push( (
৩{push( ( {
৪}ওপরে {, জোড়া মিলেছে, pop( (
৫)ওপরে (, জোড়া মিলেছে, pop(
শেষ–স্ট্যাকে একটা ( থেকে গেছেব্যালেন্সড না

একটা ( একা পড়ে রইল, তার কোনো জোড়া নেই। তাই উত্তর: ব্যালেন্সড না।

কোডঃ Python

def is_balanced(s: str) -> bool:
    pairs = {')': '(', '}': '{', ']': '['}
    stack = []

    for ch in s:
        if ch in '({[':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return not stack


print(is_balanced("(){}"))    # True
print(is_balanced("()((("))   # False
print(is_balanced("()(}"))    # False
print(is_balanced("(({})"))   # False
print(is_balanced(""))        # True
  • pairs ডিকশনারি বলে দেয় কোন বন্ধ ব্র্যাকেটের জোড়া কোন খোলা ব্র্যাকেট। এতে অনেকগুলো if-else লিখতে হয় না।
  • not stack মানে স্ট্যাক খালি।
  • লুপ শেষে return not stack: স্ট্যাক খালি হলে True, না হলে False।

অনলাইন জাজে প্র্যাকটিসঃ UVa 673 – Parentheses Balance

নিজেকে যাচাই করতে সমাধান করুন UVa 673 – Parentheses Balance।

এই সমস্যায় শুধু () আর [] আছে। প্রথম লাইনে টেস্ট কেসের সংখ্যা, তারপর প্রতি লাইনে একটা স্ট্রিং, আর উত্তর দিতে হবে Yes বা No। দুটো ফাঁদ আছে, ফাঁকা লাইন আসতে পারে (সেটা ব্যালেন্সড), তাই পুরো লাইন ধরে পড়তে হবে।

#include <bits/stdc++.h>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    int t = stoi(line);

    while (t--) {
        getline(cin, line);   // reads empty lines too
        stack<char> st;
        bool ok = true;

        for (char c : line) {
            if (c == '(' || c == '[') {
                st.push(c);
            } else if (c == ')' || c == ']') {
                char need = (c == ')') ? '(' : '[';
                if (st.empty() || st.top() != need) {
                    ok = false;
                    break;
                }
                st.pop();
            }
        }

        if (!st.empty()) ok = false;
        cout << (ok ? "Yes" : "No") << "\n";
    }
    return 0;
}

কমপ্লেক্সিটিঃ স্ট্রিংয়ের দৈর্ঘ্য n হলে সময় O(n), মেমরি O(n), কারণ সবচেয়ে খারাপ ক্ষেত্রে সব ক্যারেক্টারই খোলা ব্র্যাকেট। LeetCode-এ আরও প্র্যাকটিসঃ 20. Valid Parentheses, যেখানে তিন রকম ব্র্যাকেটই আছে, আর ওপরের Python কোডটা প্রায় হুবহু চলবে।

স্ট্যাক দিয়ে অঙ্কের হিসাব (Postfix / RPN)

(1 + (2 + 5) * 3) + (5 * 7): এমন একটা এক্সপ্রেশনের মান কম্পিউটার কীভাবে বের করে? ব্র্যাকেট আর অপারেটরের অগ্রাধিকার (আগে গুণ, পরে যোগ) সামলানো ঝামেলার কাজ। এর সমাধান হলো Reverse Polish Notation (RPN), যাকে Postfix-ও বলে। এখানে অপারেটর বসে সংখ্যার পরেঃ

  • সাধারণ লেখা: (3 + 4) * 2
  • Postfix: 3 4 + 2 *

Postfix-এ কোনো ব্র্যাকেট লাগে না, আর স্ট্যাক দিয়ে মান বের করা খুব সহজঃ

  • সংখ্যা পেলেঃ push।
  • অপারেটর পেলেঃ দুটো pop করে হিসাব করুন, ফলাফল আবার push করুন।
টোকেনকাজস্ট্যাক
3push3
4push3 4
+3 + 4 = 77
2push7 2
*7 × 2 = 1414 
def eval_postfix(expr: str) -> float:
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
    }
    stack = []
    for token in expr.split():
        if token in ops:
            b = stack.pop()  # second operand comes out first
            a = stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(float(token))
    return stack.pop()


print(eval_postfix("3 4 + 2 *"))  # 14.0

সাধারণ এক্সপ্রেশনকে Postfix-এ রূপান্তর করার জন্য আছে Shunting-yard অ্যালগরিদম।

এক নজরে সারসংক্ষেপ

  • স্ট্যাক একটা LIFO ডাটা স্ট্রাকচারঃ শেষে ঢুকলে আগে বের হয়।
  • মূল অপারেশন push, pop, peek, প্রতিটা O(1)।
  • সাবধান থাকুন Overflow (ভরা স্ট্যাকে push) আর Underflow (খালি স্ট্যাকে pop) নিয়ে।
  • রোজকার ব্যবহারঃ Undo, Back বাটন, কল স্ট্যাক, রিকার্শন, কম্পাইলার, এক্সপ্রেশন ইভ্যালুয়েশন।
  • ব্র্যাকেট ব্যালেন্স সমস্যা হলো স্ট্যাক শেখার সেরা প্রথম প্র্যাকটিস।

সচরাচর জিজ্ঞাসা (FAQ)

প্রশ্নঃ স্ট্যাক আর কিউ-এর পার্থক্য কী? উত্তরঃ স্ট্যাক LIFO, মানে শেষে এলে আগে যায়। কিউ FIFO, মানে আগে এলে আগে যায়, যেমন বাসের লাইন।

প্রশ্নঃ স্ট্যাক কি অ্যারে ছাড়া বানানো যায়? উত্তরঃ হ্যাঁ, লিংকড লিস্ট দিয়ে। তখন নির্দিষ্ট আকারের সীমা থাকে না।

প্রশ্নঃ Stack Overflow এরর কেন হয়? উত্তরঃ সাধারণত রিকার্সিভ ফাংশনের বেস কেস ভুল হলে ফাংশন বারবার নিজেকে ডাকে আর কল স্ট্যাক ভরে যায়।

প্রশ্নঃ ইন্টারভিউতে স্ট্যাকের কোন প্রশ্ন বেশি আসে? উত্তরঃ Valid Parentheses, Min Stack, Next Greater Element, Evaluate Reverse Polish Notation, আর Daily Temperatures।