ধর তোমার প্রাইমারি স্কুলের টিচার ক্লাসওয়ার্ক চেক করছেন উনার টেবিলে বসে বসে। তার কাছে এখন অনেক গুলো খাতা আছে-একটার উপর আরেকটা সাজানো। এখন তিনি খাতা কাটা শুরু করলে কোনটি থেকে শুরু করবেন? অবশ্যই সবার উপরে যেটা আছে সেটা থেকে।
এখন কেউ যদি তার কাছে আরেকটি খাতা নিয়ে যায়, তাহলে সেটি তিনি কোথায় রাখবেন? সবগুলো খাতার উপর।
এই পুরো ব্যাপারটাকেই সিমুলেট করে স্ট্যাক ডাটা স্ট্রাকচার দিয়ে। স্ট্যাকের মূল ধারণা হল, যখনই নতুন কোনো ডাটা দেওয়া হবে, সেটি স্ট্যাকে সবার উপরে গিয়ে জমা হবে। আবার স্ট্যাকে প্রসেসিং-ও চলবে সবার উপরের ডাটাটা দিয়ে। অর্থাৎ, স্ট্যাকে সবার শেষে যেটা আসছে, তার কাজ হচ্ছে সবার আগে। এটাকে বলে “Last In First Out.” আহা আমাদের লাইনে দাঁড়ানোর সময় ব্যাপারটা এমন হলে কত ভাল হত!
আমাদের স্ট্যাক ডাটা স্ট্রাকচার নিয়ে অনেক কাজই করতে হয়। এ ডাটা স্ট্রাকচারে মূলত নিচের অপারেশনগুলো রাখতে হয়ঃ
- push() – স্ট্যাকে একটি নতুন উপাদান যোগ করা
- pop() – স্ট্যাক থেকে একটি উপাদান সরিয়ে দেওয়া
- top() – স্ট্যাকের সবার উপরের উপাদানটা রিটার্ন করা
- isEmpty() – স্ট্যাকটা খালি কি না চেক করা
- isFull() – স্ট্যাকটা পরিপুর্ণ কি না চেক করা
- size() – স্ট্যাকে উপাদান সংখ্যা রিটার্ন করা
আমরা প্রথমে অ্যারে ব্যবহার করে স্ট্যাক তৈরি করবো, কারণ এটা তুলনামূলকভাবে সহজ! এজন্য আমরা প্রথমে একটি অ্যারে ডিক্লেয়ার করে ফেলি।
#include <stdio.h>
int ara[100000];
int count = 0;
int isEmpty () {
}
int isFull () {
}
int size() {
}
void push (int num) {
}
int pop () {
}
int top () {
}
int display () {
}
void menu () {
while (1) {
printf("Press 1 to push.\n");
printf("Press 2 to check if the Stack is empty.\n");
printf("Press 3 to pop.\n");
printf("Press 4 to show the top element.\n");
printf("Press 5 to display the Stack.\n");
printf("Press 6 to check if the Stack is full.\n");
printf("Press 0 to Exit.\n");
int n;
scanf("%d", &n);
if (n==0) break;
else if (n==1) {
printf("Enter the number: ");
int num;
scanf("%d", &num);
push(num);
}
else if (n==2) {
if (isEmpty()) printf("The Stack is empty.\n");
else printf("The Stack is not empty.\n");
}
else if (n==3) {
if (!isEmpty()) printf("Popped value = %d\n", pop());
else printf("The Stack is empty.\n");
}
else if (n==4) {
if (!isEmpty()) printf("The top element = %d\n", top());
else printf("The Stack is empty.\n");
}
else if (n==5) display();
else if (n==6) {
if (isFull()) printf("The Stack is Full.\n");
else printf("The Stack is not Full.\n");
}
else {
printf("Invalid choice! Try again.\n");
}
}
}
int main () {
menu();
return 0;
}
এটা আমাদের কোডের কাঠামো।
- menu() ফাংশনটির কাজ একবার পড়লেই বুঝতে পারার কথা। তবে এটা নিয়ে আপাতত বেশী মাথা ঘামানোর দরকার নেই!
- count নামের একটা ভ্যারিয়েবল আছে। এই ভ্যারিয়েবলে স্ট্যাকে কতটি উপাদান আছে, সেটি সেভ করা থাকবে।
- আর display() নামে একটি ফাংশন আমি রেখেছি। এটা রাখা হয়েছে প্রতিবার push, pop ইত্যাদি করার পর সব ঠিক থাকে নাকি সেটা চেক করার সুবিধার জন্য। তাহলে এই display() ফাংশন দিয়েই শুরু করা যাক।
display()
এই ফাংশনের কাজ হবে স্ট্যাকের শুরু থেকে শেষ পর্যন্ত সব উপাদান প্রিন্ট করা। কাজটা খুবই সহজ। একটা লুপ চালিয়ে দিলেই তো হয়!
int display () {
int i;
if (count == 0) printf("The Stack is empty.\n");
for (i=0; i<count; i++) printf("%d ", ara[i]);
printf("\n");
}
isEmpty()
এই ফাংশনটি 1 রিটার্ন করবে, যদি স্ট্যাকে কিছু না থাকে। অন্যান্য ক্ষেত্রে এটি রিটার্ন করবে 0।
int isEmpty () {
if (count == 0) return 1;
else return 0;
}
isFull()
এই ফাংশন 1 রিটার্ন করবে, যদি স্ট্যাকটি পরিপূর্ণ থাকে। অন্যান্য ক্ষেত্রে এটি রিটার্ন করবে 0। যেহেতু আমরা ১০০০০০ সংখ্যক উপাদানের অ্যারে ডিক্লেয়ার করেছিলাম, তাহলে এত সংখ্যক উপাদান থাকলেই আমাদের 1 রিটার্ন করতে হবে!
int isFull () {
if (count == 100000) return 1;
else return 0;
}
top()
এই ফাংশনটি স্ট্যাকের সবার উপরের উপাদানটি রিটার্ন করবে। সবার উপরের উপাদান বললে কনফিউশন তৈরি হতে পারে, এটা মানে হল অ্যারের শেষ উপাদানটি। কারণ আগেই বলেছি স্ট্যাক মানে হল লাস্ট ইন, ফার্স্ট আউট। অর্থাৎ, যে সবার পরে এসেছে, সে বের হবে সবার আগে!
int top () {
if (!isEmpty()) return ara[count-1];
else printf("Error! The Stack is empty.\n");
}
push()
খুবই সহজ কাজ, আমরা জানি স্ট্যাকে নতুন উপাদান এসে যুক্ত হয় সবার শেষে। তাহলে পুশ করার জন্য আমরা অ্যারের শেষে একটা নতুন উপাদান রাখবো। এরপর count-এর মান বাড়িয়ে দিব! প্যারামিটার হিসেবে আমাদের ওই নতুন উপাদানটা নিতে হবে।
void push (int num) {
if (count < 100000) {
ara[count] = num;
count++;
}
else printf("Error! The Stack is already full.\n");
}
pop()
এটা আরও সহজ। যেহেতু শেষ উপাদানটাই সরাতে হবে, সেহেতু count-এর মান এক কমিয়ে দিলেই হয়ে যায়। :p তবে খেয়াল রাখতে হবে, সেটা যেন আগে থেকে empty stack না হয়। এছাড়াও যে সংখ্যাটা pop করা হচ্ছে, সেটা রিটার্ন করা যেতে পারে (পরে অন্য কোনো এক ক্ষেত্রে এটা কাজে লাগতে পারে)।
int pop () {
if (!isEmpty()) return ara[--count];
else {
printf("Error! The Stack is empty.\n");
return 0;
}
}
size()
রিটার্ন করতে হবে count ভ্যারিয়েবলের মান। এ আর এমন কী? :p
int size() {
return count;
}
আমার পুরো কোড আছে এই লিংকে।
এখন প্রশ্ন উঠতেই পারে, এত সহজ কেন এটা। প্রশ্ন উঠাটাই স্বাভাবিক! 😛 এখানে আমি কিছু বাজে কাজ করেছি, তা হল গ্লোবাল অ্যারে নিয়ে কাজ করেছি। তোমার কাজ হবে, অ্যারেটা লোকালভাবে ডিক্লেয়ার করে ফাংশনগুলোতে অ্যারের অ্যাড্রেস প্যারামিটার হিসেবে পাঠিয়ে কাজগুলো করা। একজন প্রোগ্রামার সবসময় চেষ্টা করে গ্লোবাল ভ্যারিয়েবলের সংখ্যা যথাসম্ভব কম রাখতে। 🙂
অ্যারে দিয়ে স্ট্যাক ইমপ্লিমেন্ট করা খুব সহজ হলেও এতে আসলে খুব বেশী লাভ নেই। কারণ এখানে মেমরি লিমিটেড হয়ে যায়। আমাদের কাজটা মূলত করতে হবে লিংকড লিস্ট দিয়ে। এটি নিয়েই হবে আমাদের পরের পর্ব। 😀
Muntasir Wahed
Latest posts by Muntasir Wahed (see all)
- ফ্লয়েড ওয়ার্শাল – সব নোড থেকে সব নোডে যাওয়ার সর্বনিম্ন দুরত্ব - May 15, 2017
- নেগেটিভ সাইকেল খুজে বের করা – বেলম্যান ফোর্ড - May 14, 2017
- ডায়াক্সট্রা, ডিজক্সাত্রা নয়! (Dijkstra’s Algorithm for Shortest Path) - May 13, 2017
বাংলায় এই রকম শেখার সোর্স কমই আছে।অনেক ভালো হবে যদি এই রকম ব্লগ থাকে যেখান থেকে মানুষ অনেক কিছু শিখতে পারবে।