সি প্রোগ্রামিং ভাষায় উপাত্ত সংগঠন/স্ট্যাক

স্ট্যাক (stack) একপ্রকর সরল রৈখিক উপাত্ত সংগঠন, যেখানে একটি প্রান্ত থেকে উপাত্ত যোগ করা হয় আর ঐ একই প্রান্ত থেকে অপসারণ করা হয়। এটি লাস্ট-ইন-ফার্স্ট-আউট (LIFO) ব্যবস্থা হিসাবে পরিচিত।

ফাংশন

বিভিন্ন কম্পিউটার প্রোগ্রামে স্ট্যাক-সম্পর্কিত একাধিক ফাংশন রয়েছে:

ইজফুল (isFull): স্ট্যাকটি সম্পূর্ণ হয়েছে কি না। স্ট্যাক সম্পূর্ণ হয়ে যাওয়ার অবস্থাকে "স্ট্যাক ওভারফ্লো" (stack overflow) বলে।
ইজএম্পটি (isEmpty): স্ট্যাকটি ফাঁকা কি না। স্ট্যাক ফাঁকা থাকার অবস্থাকে "স্ট্যাক আন্ডারফ্লো" (stack underflow) বলে।
পুশ (push): স্ট্যাকে কোনো উপাদান যোগ করা হয়। এটি কোনো কিছু রিটার্ন করে না।
পপ (pop): স্ট্যাক থেকে শেষের উপাদানকে অপসারণ করা হয়, আর এটি ঐ অপসৃত উপাদানকে রিটার্ন করে।
পিক (peek): অপসারণ না করেই স্ট্যাকের শেষের উপাদানকে রিটার্ন করে।
ডিসপ্লে (display): স্ট্যাকের সমস্ত উপাদানকে শেষ থেকে প্রথম উপাদান অনুযায়ী টার্মিনালে প্রদর্শিত করে।

সি প্রোগ্রামিং ভাষায় প্রয়োগ

সি প্রোগ্রামিং ভাষায় কোনো স্ট্যাককে দুইভাবে উপস্থাপন করা হয়: অ্যারে ও লিঙ্কড লিস্ট।

অ্যারে

অ্যারেতে কোনো স্ট্যাককে সাধারণত এইভাবে উপস্থাপন করা হয়:

#define MAX 15
int stack[MAX], top=-1;

এখানে MAX একটি ম্যাক্রো (macro) এবং সম্পূর্ণ প্রোগ্রামে MAX কথাটি যেখানে ব্যবহৃত হয়েছে কম্পাইলার সেখানে এই কথাটির জায়গায় একটি ধ্রুবক রাশি যোগ করে। উক্ত কোডে #define MAX 15 লেখাটির মাধ্যমে কম্পাইলারকে এটা বোঝানো হয় যে সম্পূর্ণ প্রোগ্রামে MAX কথাটি যেখানে ব্যবহৃত হয়েছে কম্পাইলার সেখানে এই কথাটির জায়গায় 15 যোগ করবে।

এছাড়া এখানে top ভেরিয়েবলটি স্ট্যাকের শেষ উপাদানের ইন্ডেক্সকে সঞ্চয় করে। পুশ ফাংশন ব্যবহার করলে এর পরিমাণ বাড়ে এবং পপ ফাংশন ব্যবহার করলে এর পরিমাণ কমে।

সম্পূর্ণ স্ট্যাক যাচাই

স্ট্যাকে কোনো উপাদান যোগ করার আগে আমাদের যাচাই করা উচিত যে স্ট্যাকে নতুন উপাদান যোগ করার পর্যাপ্ত জায়গা আছে কি না, অর্থাৎ স্ট্যাকটি সম্পূর্ণ হয়েছে কি না। এর জন্য উপযুক্ত সি ফাংশন নিম্নরূপ:

bool isFull() {
    return (top==MAX-1);
}

এখানে এটা যাচাই করা হচ্ছে যে top-এর পরিমাণ MAX-1-এর সমান কি না। MAX-1 হচ্ছে স্ট্যাকের সর্বোচ্চ ইন্ডেক্স আর top এর চেয়ে কোনো বড় ইন্ডেক্সকে সঞ্চয় করতে পারে না। লক্ষণীয় যে এখানে bool ডেটা টাইপটি সি প্রোগ্রামিং ভাষার নিজস্ব ডেটা টাইপ নয়, এর জন্য উপরে #include <stdbool.h> লেখাটি আবশ্যক।

ফাঁকা স্ট্যাক যাচাই

স্ট্যাকে কোনো উপাদান যোগ করার ব্যতীত অন্যান্য ফাংশন প্রয়োগ করার আগে আমাদের যাচাই করা উচিত যে ঐ ফাংশনগুলোর জন্য স্ট্যাকে কিছু উপাদান আছে কি না, অর্থাৎ স্ট্যাকটি ফাঁকা কি না। ফাঁকা স্ট্যাকে উপাদান সংযোজন ("পুশ") ছাড়া অন্য কোনো ফাংশন প্রয়োগ করা যায় না। ফাঁকা স্ট্যাক যাচাই করার জন্য উপযুক্ত সি ফাংশন নিম্নরূপ:

bool isEmpty() {
    return (top==-1);
}

এখানে এটা যাচাই করা হচ্ছে যে top-এর পরিমাণ -1 (ঋণাত্মক ১)-এর সমান কি না। 0 হচ্ছে স্ট্যাকের সর্বনিম্ন ইন্ডেক্স আর top-এ এটি সঞ্চয় করা আছে অর্থ স্ট্যাকে কেবল একটি উপাদান পড়ে আছে, যার ইন্ডেক্স 0। সেইজন্য ফাঁকা স্ট্যাক বোঝানোর জন্য top-এর মান -1 রাখা হয়, যা 0-এর থেকে ছোট।

পুশ

নিম্নলিখিত ফাংশনের মাধ্যমে স্ট্যাকে কোনো উপাদান যোগ করা হয়:

void push(int item) {
    if(isFull()) {
        printf("স্ট্যাক সম্পূর্ণ\n");
        return;
    }
    stack[++top]=item;
}

এখানে প্রথমে স্ট্যাকটি সম্পূর্ণ কি না এটা যাচাই করা হয়। স্ট্যাকটি সম্পূর্ণ হলে টার্মিনালে "স্ট্যাক সম্পূর্ণ" দেখাবে আর পরের লাইনটি সক্রিয় হয় না। সম্পূর্ণ না হলে তবে পরের লাইনটি সক্রিয় হবে। এখানে ++top মানে বোঝাচ্ছে যে উপাদান যোগ করার আগে top-এর মান 1 করে উন্নীত হয়েছে। উন্নীত হওয়ার পর item-এ সঞ্চিত উপাদানটি stack[top]-এ সঞ্চিত হয়।

পপ

নিম্নলিখিত ফাংশনের মাধ্যমে স্ট্যাকের শেষের উপাদানকে অপসারণ করা হয়:

int pop() {
    if(isEmpty()) {
        printf("স্ট্যাক ফাঁকা\n");
        return INT_MIN;
    }
    return stack[top--];
}

এখানে প্রথমে স্ট্যাকটি ফাঁকা কি না এটা যাচাই করা হয়। স্ট্যাকটি ফাঁকা হলে টার্মিনালে "স্ট্যাক ফাঁকা" দেখাবে আর পরের লাইনটি সক্রিয় হয় না। সম্পূর্ণ না হলে তবে পরের লাইনটি সক্রিয় হবে। এখানে INT_MIN বলতে int ডেটা টাইপের সর্বনিম্ন মানকে বোঝাচ্ছে, যার জন্য উপরে #include <limits.h> লেখাটি আবশ্যক।

এখানে top-- মানে বোঝাচ্ছে যে স্ট্যাকের শেষের উপাদানটি রিটার্ন করার পর top-এর মান 1 করে কমে গিয়েছে। এখানে আদতে শেষের উপাদানটি স্ট্যাক থেকে অপসৃত হয়নি, কারণ এটি অ্যারের ক্ষেত্রে সম্ভব নয়। বরং এখানে top-এর মান 1 করে কমানো হয়েছে যাতে "অপসৃত" উপাদানকে top থেকে আর না পাওয়া যায়।

পিক

নিম্নলিখিত ফাংশনের মাধ্যমে স্ট্যাকের শেষের উপাদানকে অপসারণ না করে রিটার্ন করা হয়:

int peek() {
    if(isEmpty()) {
        printf("স্ট্যাক ফাঁকা\n");
        return INT_MIN;
    }
    return stack[top];
}

এখানে প্রথমে স্ট্যাকটি ফাঁকা কি না এটা যাচাই করা হয়। স্ট্যাকটি ফাঁকা হলে টার্মিনালে "স্ট্যাক ফাঁকা" দেখাবে আর পরের লাইনটি সক্রিয় হয় না। সম্পূর্ণ না হলে তবে পরের লাইনটি সক্রিয় হবে। এখানে INT_MIN বলতে int ডেটা টাইপের সর্বনিম্ন মানকে বোঝাচ্ছে।

পরের লাইনে স্ট্যাকটির শেষের উপাদানকে অপসারণ না করে রিটার্ন করা হচ্ছে।

ডিসপ্লে

নিম্নলিখিত ফাংশনের মাধ্যমে স্ট্যাকের সমস্ত উপাদানকে শেষ থেকে প্রথম অনুযায়ী টার্মিনালে প্রদর্শিত করে:

void display() {
    if(isEmpty()) {
        printf("স্ট্যাক ফাঁকা\n");
        return;
    }
    for(int i=top; i>=0; i--) {
        printf("%d", stack[i]);
    }
}