Data Structure: Stack
STACK operation with algorithm
স্ট্যাক(Stack) হল একটি লিনিয়ার ডাটা স্ট্রাকচার যা LIFO (Last In First Out) প্রিন্সিপল অনুসরণ করে। স্ট্যাকে প্রধানত নিম্নলিখিত অপারেশনগুলি করা হয়:
PUSH – স্ট্যাকের শীর্ষে একটি উপাদান যোগ করে।
POP – স্ট্যাক থেকে শীর্ষস্থ উপাদানটি সরিয়ে নেয়।
PEEK – স্ট্যাকের শীর্ষস্থ উপাদানটি রিটার্ন করে তবে সরিয়ে নেয় না।
স্ট্যাক(Stack) সম্পর্কে কিছু গুরুত্বপূর্ণ বিষয়:
- স্ট্যাক শুধুমাত্র উপরের উপাদানটির অ্যাক্সেস করা হয়। নিচের উপাদানগুলি সরাসরি অ্যাক্সেস করা যায় না।
- ব্রাউজার, কম্পাইলার, ইন্টারপ্রেটার এদেরকে ইমপ্লিমেন্ট করার জন্য স্ট্যাক(Stack) ব্যবহৃত হয়।
- রিকার্সিভভাবে ফাংশন কল করার জন্য স্ট্যাক ব্যবহার করা হয়।
- স্ট্যাকে শুধুমাত্র একটি দিক থেকে ইনসার্ট(Insert) or পূশ(PUSH) এবং ডিলিট(Delete) পপ (POP) অপারেশন করা যায়, যাকে টপ(TOP) বলা হয়। অন্য দিকটি ফিক্সড এবং বটম নামে ডাকা হয়।
- স্ট্যাকের কিছু সাধারণ অ্যাপ্লিকেশন হলো:
- এক্সপ্রেশন ইভ্যালুয়েশন(Expression Evolution) এবং সিনট্যাক্স পার্সিং(Syntax Parsing)
- ব্যাকট্র্যাকিং(Backtracking) যেমন মেজ(Maze) এবং গ্রাফ প্রবলেম(Graph Problem)
- গার্বেজ কালেকশন ছাড়াই পরিবেশের মেমোরি ম্যানেজমেন্ট
সংক্ষেপে, স্ট্যাক LIFO অর্ডার অনুসরণ করে, শুধুমাত্র এক দিকে অপারেশনের সুবিধা দেয় এবং ফাংশন, পার্সার, ব্যাকট্র্যাকিং অ্যালগরিদম ইত্যাদি ইমপ্লিমেন্টের জন্য ব্যবহৃত হয়। এর সহজ গঠনটি পুশ(PUSH)/পপ(POP) অপারেশনকে খুব দ্রুত করে তুলে। এই দুই অপারেশন দুই ভাবে ইমপ্লিমেন্ট করা সম্ভব 1) Array 2) Link List
স্ট্যাক(STACK) এর পুশ(PUSH) এবং পপ(POP) অপারেশনটির algorithm:
PUSH/INSERT()
1.if top=MAX then
print "Stack is full";
exit;
2. otherwise
top:=top+1;
stack(top)=item;
3. end of if
4. exit
POP/DELETE()
1. if top=0 then
print "Stack is empty";
exit;
2. otherwise
item=stack(top);
top:=top-1;
3. end of if
4. exit
isFull()
1. if top=MAX then
status=true;
2. otherwise
status=false;
3. end of if
4. exit
isEmpty()
1. if top=0 then
status=true;
2. otherwise
status=false;
3. end of if
4. exit
1. Array : স্ট্যাক(STACK) এর পুশ(PUSH) এবং পপ(POP) অপারেশন এর Source code টি উল্লেখ করা হল –
//Stack Implementation Using Array[Static Memory allocation]
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}Link list : স্ট্যাক(STACK) এর পুশ(PUSH) এবং পপ(POP) অপারেশন এর Source code টি উল্লেখ করা হল –
//Stack Implementation Using Link List
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
} *top = NULL;
void push(int);
void pop();
void display();
void main()
{
int ch, data;
printf("\n:: Stack using Linked List ::\n");
while (1)
{
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the value to be insert: ");
scanf("%d", &data);
push(data);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
if (top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
while (temp->next != NULL)
{
printf("%d--->", temp->data);
temp = temp->next;
}
printf("%d--->NULL", temp->data);
}
}