Stacks:( with respect to arrays)
A stack is an ordered list in which all insertion and deletion are performed at one end called Top end. The insertion operation is called Push and deletion operation is called Pop.
A stack is represented as follows:
1. Topmost element in the stack is indicated by the pointer Top.
2. Insertion and Deletion are performed only at the Top end of the stack.
3. Elements can be deleted in the opposite order in which they were added to stack.
Eg. In the above figure the elements are added in the order 10, 20, 30, 40 i.e., the first and last element inserted in the stack is 10 and 40 respectively. The first element that can be deleted from the stack is 40 and the last element to be deleted is 10.
Thus the last element inserted into the stack is the first element to be deleted. Therefore, stack is called as Last in First out (LIFO) list.
Stacks can be implemented by either using one dimensional arrays or using linked list. However, the simplest way to represent stack is by using one dimensional array where ‘n’ is the maximum no. of locations in the stack. The first element in the stack is stored at s[0], second element at s[1] and (n-1)th element at s[n-1]. There is a variable called Top which points to the top most element in the stack.
Operations on the Stack
1. Insertion or Push
2. Deletion or Pop
Insertion:
Initially, when the stack is empty top=-1. when the element is inserted into the stack, top is incremented by 1, so top becomes 0 (top=0). Thus each time an element is inserted into the stack, top is incremented by 1 and then new element is inserted at s[top]. Finally, when top=n-1, we say stack is full and insertion is not possible.
Push function in C Language
void push(int n)
{
if(top==max-1)
{
printf("stack is full. Insertion is not possible\n");
}
else
{
top=top+1;
s[top]=n;
}
}
Deletion:
To delete an element form the stack, top is decremented by 1. Thus deletion is nothing but decrementing top by 1. Finally, when top =-1, we say stack is empty and deletion is not possible.
Pop function in C Language
int pop()
{
int n;
if(top==-1)
{
printf("Stack is Empty. Deletion is not possible \n");
}
else
{
n=s[top];
top=top-1;
}
return n;
}
C Program which demonstrates Stack Operations.
int max;
int top, s[5];
void main()
{
int n;
int pop();
void push(int);
void displist();
clrscr();
top=-1;
max=5;
printf("Enter elements into Stack\n");
push(10);
push(20);
push(30);
push(40);
push(50);
push(60);
displist();
n=pop();
printf("After deletion element from stack=%d\n",n);
n=pop();
printf("After deletion element from stack=%d\n",n);
n=pop();
printf("After deletion element from stack=%d\n",n);
n=pop();
printf("After deletion element from stack=%d\n",n);
n=pop();
printf("After deletion element from stack=%d\n",n);
n=pop();
printf("After deletion element from stack=%d\n",n);
displist();
getch();
}
void displist()
{
int i;
for(i=0;i<=top;i++)
{
printf("%d\n",s[i]);
}
}
void push(int n)
{
if(top==max-1)
{
printf("stack is full. Insertion can not be performed\n");
}
else
{
top=top+1;
s[top]=n;
}
}
int pop()
{
int n;
if(top==-1)
{
printf("stack is empty. Deletion can not be performed\n");
}
else
{
n=s[top];
top=top-1;
}
return n;
}
C Program which demonstrates Stack Operations using Menu
#define max 3
int top=-1,s[max];
void main()
{
int choice;
void push();
void dispstack();
int pop();
clrscr();
while(1)
{
clrscr();
printf("1 push\n");
printf("2 pop\n");
printf("3 display\n");
printf("4 exit\n");
printf("Enter Choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1: {
push();
printf("Press any key to continue");
getch(); break;
}
case 2: {
pop();
printf("Press any key to continue");
getch(); break;
}
case 3: {
dispstack();
printf("Press any key to continue");
getch(); break;
}
case 4: {
exit(0); break;
}
default: {
printf("invalid choice\n");
printf("Press any key to continue");
getch();
}
}
}
}
void dispstack()
{
int i;
for(i=top;i>=0;i--)
{
printf("%d ",s[i]);
}
}
void push()
{
int n;
if(top==max-1)
{
printf("stack is full.insertion can not be performed\n");
}
else
{
top=top+1;
printf("enter element to push\n");
scanf("%d",&n);
s[top]=n;
}
}
int pop()
{
int n;
if(top==-1)
{
printf("stack is empty. delation can not be performed\n");
}
else
{
n=s[top];
top=top-1;
}
return n;
}
No comments:
Post a Comment