স্ট্যাকঃ বহুল ব্যবহৃত ডেটা স্ট্রাকচার

Post updated on 6th May, 2018 at 10:31 am

বল্টু একজন ভোজন রসিক বালক। প্রতি সপ্তাহেই সে বিভিন্ন রেস্টুরেন্টে ভাল-মন্দ খানা-দানা করে থাকে। মাসের প্রথম সপ্তাহে সে মুরগি পোড়া খেলে দ্বিতীয় সপ্তাহে খায় কাচ্চি বিরিয়ানি। তৃতীয় সপ্তাহে নিরব হোটেলের ভাত ভর্তা খেয়ে চতুর্থ সপ্তাহে খায় শরমা হাউজের পাহাড়ি কাবাব। এভাবে সে নিয়মিত খাওয়া-দাওয়া চালিয়ে যাচ্ছে। কী পরিমাণ খাওয়া দাওয়া হচ্ছে তার হিসাব রাখার জন্য নিচের ছবির মত একটা হুকের মধ্যে রেস্টুরেন্টের বিলের স্লিপটা গেঁথে রাখে।

হুট করে সে খেতে যাওয়ার আগে চেক করার ইচ্ছা করল গত সপ্তাহে কী খেয়েছ? সে গত সপ্তাহের স্লিপ কোথায় পাবে? গেঁথে রাখা কাগজের স্তুপের (ইংরেজিতে যাকে বলে stack) একদম উপরে তাই না? গত সপ্তাহের স্লিপ বের করার জন্য কিন্তু তার এই স্তুপের সব কাগজ বের করতে হয় নি। সে সবার উপরেরটা উঠিয়ে দেখল কী খেয়েছে। এটা হাতে থাকা অবস্থায় তার আগের সপ্তাহে কী খেয়েছে সেটা দেখতে চাইলে স্তুপের উপরে যেটা আছে সেটাকেই সে চেক করবে। এভাবে একটা একটা করে সে সব চেয়ে পুরোনো স্লিপটা খুঁজে পাবে। তাহলে দেখা যাচ্ছে যেই স্লিপটা সবার শেষে গাঁথা হচ্ছে সেটাকে বের করতে হচ্ছে সবার শুরুতে। ইংরেজিতে যাকে বলা যায় Last In First Out বা LIFO. আর এই স্তুপের মত করে একটার উপরে একটা ডেটা সাজিয়ে রাখার ডেটা স্ট্রাকচারের নামই হচ্ছে স্ট্যাক – Stack Data Structure.

Simple Array ও Linked List উভয়টা দিয়েই Stack implement করা যায়। এই লেখায় অ্যারে দিয়ে স্ট্যাক ইমপ্লিমেন্ট করা দেখানো হবে। স্ট্যাক বোঝার জন্য তাই Array এর উপর স্বচ্ছ ধারণা থাকতে হবে। এই অ্যারেকে নির্দিষ্ট কিছু নিয়মে ব্যবহার করার মাধ্যমেই স্ট্যাক ডেটা স্ট্রাকচারটি ইমপ্লিমেন্ট করা হয়। তাই অ্যারে সম্পর্কে ধারণা না থাকলে এ সম্পর্কে বিস্তারিত জেনে নিতে পারো এখান থেকে।

ডেটা স্ট্রাকচার মূলত ডেটাগুলোকে এমন ভাবে সুসজ্জিত বা সুবিন্যস্ত করার পদ্ধতি যেখানে সহজে ডেটা ইনপুট করা যায় এবং সেখান থেকে ডেটা read করা যায়। অন্যান্য ডেটা স্ট্রাকচারের মত স্ট্যাকেরও কয়েকটি ব্যাসিক অপারেশন রয়েছে।

• push – স্ট্যাকে ডেটা insert করা
• peek – top element কে read করা
• pop – স্ট্যাকের top এ থাকা ডেটাকে remove করে দেয়া

Applications of Stack Data Structure

সাধারণত আমরা দরকার ছাড়া কোন কাজের কাজ করি না। যেহেতু স্ট্যাক ডেটা স্ট্রাকচার শেখাটা একটা কাজের কাজ তাই প্রথম প্রশ্ন আসবে আমরা কেন এটা শিখব? আরো স্পষ্ট করে বলতে বললে বলা যায় “এটা শিখলে কি ভাল চাকরি পাব?” 😛

যাই হোক, জীবন ঘনিষ্ঠ আলোচনায় না গিয়ে কোডিং ঘনিষ্ঠ আলোচনায় মন দেই। নিচে কয়েকটা কমন ক্ষেত্রের কথা উল্লেখ করা হল যেখানে স্ট্যাক ইমপ্লিমেন্ট করার দরকার হয়।

• Web Browser এর back ও forward বাটনের ফিচারটা ইমপ্লিমেন্ট করতে স্ট্যাক ব্যবহার করা হয়। এক্ষেত্রে দুইটা স্ট্যাক নেয়া যেতে পারে। একটার নাম দিলাম ব্যাক স্ট্যাক, আরেকটা ফরওয়ার্ড স্ট্যাক। ধরো, তুমি কোন একটা ট্যাবে ফেসবুকের হোমপেজ ভিজিট করতেছো। হোমপেজের লিংকটাকে ব্যাক স্ট্যাকে পুশ করা হয়। এই ট্যাবেই হাসানের রাফখাতার পেজ ওপেন করলা। এই পেজের লিংক স্ট্যাকে পুশ করা হয়। এরপর ঢুঁ মারলা ইউটিউবে, সাথে সাথেই ইউটিউবের লিংক স্ট্যাকে পুশ করা হবে। এখন স্ট্যাকের একদম নিচে আছে ফেসবুকের হোমপেজ, তার উপরে আছে হাসানের রাফখাতার লিংক, তার উপরে আছে ইউটিউব। ইউটিউব ব্রাউজ করার সময় ব্যাক বাটনে ক্লিক করলে ইউটিউবের লিংকটা ব্যাক স্ট্যাক থেকে তুলে নিয়ে ঢুকানো হবে ফরওয়ার্ড স্ট্যাকে। আর তোমার সামনে লোড করা হবে ব্যাকস্ট্যাকের সবার উপরে থাকা রাফখাতার লিংক। রাফখাতা দেখে ফরওয়ার্ড দিলে ফরওয়ার্ড স্ট্যাক থেকে লিংকটা তুলে এনে ব্যাকস্ট্যাকে রাখা হবে এবং তোমাকে ইউটিউবের পেজ দেখানো হবে। এভাবে দুইটা stack ব্যবহার করে web browser এর back ও forward feature টা implement করা যায়।
• কোন সফটওয়ারের Undo feature implement করতেও স্ট্যাক ব্যবহার করতে হয়। ব্রাউজারের মত এখানেও দুইটা স্ট্যাক লাগে। ধরো তুমি একটা টেক্সট এডিটর বানাচ্ছ। যাতে undo-redo feature থাকবে। ধরো তোমার লজিক হচ্ছে প্রতিটা ক্যারেক্টার লিখলে একেকটা ক্যারেক্টারকে undo stack এ ঢুকিয়ে দিবা। Undo button এ ক্লিক করলে স্ট্যাকের উপরে থাকা অর্থাৎ তোমার ইনপুট করা সর্বশেষ অক্ষরটাকে undo stack থেকে তুলে নিয়ে redo stack এ ঢুকিয়ে দিলা। আবারো আনডু বাটনে ক্লিক করলে undo stack থেকে আরেকটা ক্যারেকটার redo stack  ঢুকিয়ে দিবা। redo button এ ক্লিক করলে redo stack এর উপরে থাকা অক্ষরটাকে undo stack এ ঢুকিয়ে দিবা। আর স্ক্রিনে দেখা যাবে সব সময় undo stack এ থাকা অক্ষরগুলো।
• ক্যালকুলেটরে বড় একটা ইকুয়েশন যখন লিখি তখন ব্র্যাকেটের ব্যালান্স ঠিক আছে কিনা বা অপারেটর কোনটার কাজ আগে হবে বা পরে হবে সেটা চেক করার জন্য স্ট্যাক দরকার হয়। যেমন a + (b*c-(d/e)) টাইপের একটা হিসাব করতে চাচ্ছি। তখন স্ট্যাক ব্যবহার করে এই সমীকরণ খুব সহজে সমাধান করা যায়। কীভাবে করতে হবে সেটা অন্য কোন পোস্টে বিস্তারিত লিখব ইন_শা_আল্লাহ।
• তোমরা নিশ্চয়ই প্রোগ্রামিং করার সময় function ব্যবহার করে থাকবে। ধরো, main ফাংশন একটা স্ট্যাকে রাখা আছে।  main থেকে a নামক ফাংশনকে কল করা হল। তাহলে ঐ স্ট্যাকে main এর উপরে a ফাংশনকে রাখা হবে। a ফাংশন যদি b ফাংশনকে কল করে তাহলে a এর উপরে b-কে রাখা হবে। b এর কাজ শেষ হলে b কে স্ট্যাক থেকে মুছে দেয়া হবে। তখন a এর বাকি কাজ সম্পন্ন করবে।  a এর কাজ শেষ হলে এটাকেও স্ট্যাক থেকে বের করে দেয়া হবে। তখন স্ট্যাকে থাকবে শুধু main ফাংশন। তখন main function তার বাকি কাজ করে শেষ করলে প্রোগ্রাম exit হবে এবং এই ফাংশনকেও স্ট্যাক থেকে মুছে ফেলা হবে।

আপাতত এই কয়টা মাথায় ছিল তাই লিখলাম। আরো আগ্রহ থাকলে গুগল তো আছেই! 🙂

Stack Declaration

আমরা পূর্বে যেই অ্যারে শিখেছি সেটাকে দিয়েই স্ট্যাকের কাজ করব। স্ট্যাকের জন্য মূলত একটা অ্যারেই ডিক্লিয়ার করতে হবে। সি প্রোগ্রামিং ল্যাঙ্গুয়েজে অ্যারে ডিক্লিয়ার করতে পারি এভাবেঃ

.
int myStack[100];
.

তাহলে এই স্ট্যাকে সর্বোচ্চ ১০০ টি ভ্যালু রাখা যাবে। সি++ ল্যাঙ্গুয়েজের Standard Template Library (STL) ব্যবহার করে অ্যারে ডিক্লিয়ার না করে সরাসরি স্ট্যাকই ডিক্লিয়ার করা যায়ঃ

#include<stack>

using namespace std;

int main(){
.
    stack<int> myStack;
.
}

PUSH Operation of Stack

Push করার মানে হচ্ছে স্ট্যাকে একটা নতুন ডেটা ঢুকিয়ে দেয়া বা insert করা। স্ট্যাকটাকে এমন ভাবেই ম্যানেজ করা হয় যেন যেই মানটা ঢুকানো হবে সেটা সবার উপরে থাকে। C++ এর STL Stack ব্যবহার করে পুশ করতে চাইলে এই এক লাইন লিখলেই পুশ হয়ে যাবেঃ

.
myStack.push(34);
.

কিন্তু তুমি যদি সি ল্যাঙ্গুয়েজ বা অন্য কোন ল্যাঙ্গুয়েজ দিয়ে ম্যানুয়াল্যি পুশ করতে চাও তাহলে আরো কয়েক লাইনের সহজ কোড লিখা লাগবে। int ভ্যালুর জন্য একটা push ফাংশন লিখে ফেলি, যার মধ্যে প্যারামিটার হিসেবে একটা int value পাঠাবো। সেই ফাংশনটা global array তে মানটা পুশ করে দিবে।

#define stackSize 100
int myStack[stackSize], top = -1; //Global variables

void push(int value){

    if(top>=stackSize-1)
        printf("Stack is full! Cannot push the value!");
    else
        myStack[++top] = value;

}

৬ নাম্বার লাইনে চেক করা হচ্ছে স্ট্যাকটা অলরেডি ডেটা দ্বারা full হয়ে গিয়েছে কিনা। top ভ্যারিয়েবলের মান Globally ডিক্লিয়ার করার সময় -1 করে দেয়া হয়েছে। এটা দিয়ে হিসাব রাখা হবে স্ট্যাকে কয়টা ডেটা পুশ হয়েছে। top এর মান stackSize এর সমান বা বড় না হলে অর্থাৎ স্ট্যাক full না হলে stack এ ভ্যালুটা পুশ করা হচ্ছে ৮ নাম্বার লাইনে। প্রতিবার পুশ করার পাশাপাশি ++top করা হয়েছে। এতে স্ট্যাকে প্রথম ভ্যালুটা ইনসার্টের সময় top এর মান -1 থেকে বেড়ে 0 হবে এবং myStack[0] এর ঘরে প্রথম ভ্যালুটা পুশ হবে। এরপর আবারো পুশ ফাংশন কল করা হলে স্ট্যাক ফুল না হয়ে গিয়ে থাকলে আবারো ৮ নাম্বার লাইনে স্ট্যাকের ++top-তম ইন্ডেক্সে অর্থাৎ myStack[1] এ এই নতুন ভ্যালু ইনসার্ট করা হবে।

এই top ভেরিয়েবলটা বেশ গুরুত্ব বহন করে। স্ট্যাকে নতুন ভ্যালু ঢুকানোর জন্য অ্যারের top-তম index এর মান ১ বাড়িয়ে নতুন ভ্যালুটা assign করা হয়। অ্যারেটা ডেটা দিয়ে পূর্ণ কিনা সেটাও top দিয়ে চেক করা হয়। পরবর্তীতে স্ট্যাকের সবার উপরের ভ্যালুটা read করার জন্যেও top এর সাহায্য নিতে হবে। মোট কথা স্ট্যাকের ডেটা read-write এর জন্য পুরোপুরি ভাবে আমরা top ভ্যারিয়েবলের উপর নির্ভরশীল।

main function থেকে push(45); push(24), push(-67); তিনবার পুশ ফাংশন কল করা হলে myStack[0] তে থাকবে 45, myStack[1] এ থাকবে 24 এবং myStack[2] তে থাকবে -67.

স্ট্যাকে ডেটা পুশ করতে করতে যখন top এর মান stackSize এর সমান হয়ে যাবে তখন আর কোন ভ্যালু স্ট্যাকে ঢোকানো যাবে না। কারণ array এর সাইজ হচ্ছে stackSize এর মান, অর্থাৎ ১০০। অ্যারের ইন্ডেক্স নাম্বার শুরু হয়েছে 0 থেকে। সর্বশেষ ইন্ডেক্স এর নাম্বার 99. কিন্তু top এর মান stackSize বা 100 এর সমান হয়ে গেলে myStack[top] = value; অর্থাৎ অ্যারের top বা 100 নাম্বার ইন্ডেক্সে value এর মান অ্যাসাইন করার চেষ্টা করা হবে। কিন্তু ১০০ নাম্বার ইন্ডেক্স এই অ্যারেতে অনুপস্থিত। অ্যারেতে বা স্ট্যাকে জায়গা নাই, অথচ আমরা মান insert করতে চাচ্ছি। এই সিচুয়েশনকে বলা হয় Stack Overflow.

PEEK Operation of Stack

এই অপারেশনের নাম এমনিতেই peek দেয়া। বুঝানো হচ্ছে যে এই অপারেশন দিয়ে স্ট্যাকের টপ বা একদম উপরের ভ্যালুটাকে peek/read করা হবে। সি++ এর টেমপ্লেট লাইব্রেরির built in function ব্যবহার করে স্ট্যাকের টপ ভ্যালুটাকে access করা যায়।

.
int topValue = myStack.top();
.

উপরের কোডে top() ফাংশনটি স্ট্যাকের সবার উপরের পজিশনের ভ্যালুটা রিটার্ন করবে।

C programming এর মাধ্যমে স্ট্যাকের টপ পজিশনের ভ্যালু প্রিন্ট করার জন্য নিচের user defined function দিয়ে করলে হবেঃ

void peek()
{
    if(top<0)
       printf("Stack is Empty!\n");
    else
       printf("%d\n", myStack[top]);
}

POP Operation of Stack

Stack এর top position এ থাকা ভ্যালুটাকে রিমুভ করার প্রকৃয়াকে বলা হয় POP. C++ এর STL এর সাহায্যে pop করা যায় খুব সহজেইঃ

.
myStack.pop();
.

উপরের কোড এক্সিকিউশনের পর তুমি এখন myStack.top(); এই ফাংশনটা এক্সিকিউট করলে দেখবে আগে টপের ভ্যালুটা এখন আর নাই। টপের নিচে যেই ভ্যালু ছিল সেটাই এই অবস্থায় এখন টপ ভ্যালু।

সি প্রোগ্রাম দিয়ে ফাংশনটা লিখে ফেলা যায় এভাবেঃ

void pop()
{
    if(top<0)
       printf("Stack is empty! Cannot POP any value!\n");
    else
       top--;
}

Array/Stack থেকে কিন্তু সত্যিকারার্থে টপ ভ্যালুটা মুছে দেয়া হয়নি। বরং আমরা যেই ভ্যারিয়েবল দিয়ে আমাদের ভ্যালুর সংখ্যা হিসাব রাখছিলাম তার মান এক কমিয়ে দিলাম। ধরো স্ট্যাকের ৩ নাম্বার ইন্ডেক্সে (top=3) মান আছে ২৫। এই অবস্থায় pop() কল দেয়া হল। তখন myStack[3] তে ২৫ ঠিকই আছে কিন্তু top এর মান কমে দাঁড়িয়েছে ২। এখন যদি আবার push(57) ফাংশন কল করা হয় তখন top এর মান ১ বেড়ে হবে ৩। myStack[3] এর মানটা রিপ্লেস হয়ে যাবে নতুন ভ্যালু 57 দ্বারা।

pop() function এর শুরুতেই একটা চেক রাখা হয়েছে top এর মান শূণ্যের চেয়ে কম কিনা। top এর মান শূণ্যের চেয়ে কম হবার অর্থ হচ্ছে স্ট্যাকে কোন ডেটা নাই। top এর মান 0 হবার মানে হচ্ছে স্ট্যাকে ১ টা ডেটা আছে, যাকে পাওয়া যাবে myStack[0] তে। Stack এ কোন ভ্যালু নাই, কিন্তু pop করে ভ্যালুকে রিমুভ করার চেষ্টা করা হলে বা peek/read করার চেষ্টা করা হলে উদ্ভুত পরিস্থিতিতে বলা হয় stack underflow.

Complexity of Stack Operations

• push() – O(1)
• pop() – O(1)
• peek() – O(1)

সবগুলো অপারেশন একত্রে একটা প্রোগ্রামে পাওয়া আমার গিটহাব রিপোজিটরিতে।

স্ট্যাকের পরবর্তী পোস্ট স্ট্যাক ব্যবহার করে ব্র্যাকেটের ব্যালেন্স চেকিং।

স্ট্যাক দিয়ে সলভ করতে পারো এই প্রবলেমটিঃ LightOJ 1113

সবার মতামত ও পরামর্শ একান্ত কাম্য। ধন্যবাদ। 🙂