A stack is an ordered collection of items into which new items can be inserted and from which items can be deleted. But both the operations can be done from one end called the top of the stack (TOS).Unlike array stack provides the facilities for the insertion and deletion of items which makes stack dynamic. A single end of a stack can be designed as the TOS. New items can be put on TOS – in such case top of the stack moves upward to accommodate the new top most element or items from the top of the stack can be removed and top of the stack automatically moves downward to correspond to the new top element.
Array implementation of stack
Array can not be a stack but it can be the home of a stack. An array can be declared large enough for the maximum size of a stack. At the run time the stack can grow or shrink within the space reserved for it. One end of the array will act like the fixed bottom of stack while from the other end items can be added or removed. So another field is needed that keeps track of the current position of the top of the stack. This is called array implementation of stack.
Program on Array implementation of stack
# include< stdio.h>
# include< string.h>
# define size 3
int tos= -1;
/*this variable will keep track of the top of the stack */
int flag = 0;
/* this variable will determine whether push or pop will be granted. */
int stack[size];
/* array , within this array stack will grow and shrink. */
void push(int s[], int d)
{
if(tos==size-1)
{
/* this condition becomes true when the stack can not grow further */
flag=0;
}
else
{
flag = 1;
++tos;
s[tos] = d;
}
}
int pop(int s[])
{
int p;
if(tos == -1)
{
p = 0;
flag = 0;
}
else
{
flag = 1;
p = s[tos];
--tos;
}
return p;
}
void display(int s[])
{
int i;
if(tos == -1)
{
printf("\n Stack is empty");
}
else
{
for(i = tos; i >= 0; --i)
printf("\n %d", s[i] );
}
}
void main()
{
int data;
char choice;
int q = 0;
clrscr();
do
{
printf(" \nPush->i Pop->p Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice =tolower(choice);
}while(strchr("ipq",choice)==NULL);
printf("Your choice is: %c",choice);
switch(choice)
{
case 'i' :
printf("\n Input the element to push:");
scanf("%d", &data);
push(stack, data);
if(flag)
{
printf("\n After inserting ");
display(stack);
if(tos == (size-1))
printf("\n Stack is full");
}
else
printf("\n capacity is exhausted");
break;
case 'p' :
data = pop(stack);
if(flag)
{
printf("\n Data is popped: %d", data);
printf("\n Rest data in stack is as follows:\n");
display(stack);
}
else
printf("\n No popping took place" );
break;
case 'q':
q = 1;
}
} while(!q);
getch();
}
Linked list implementation of stack in C Programming
Our previous program was on implementing array as stack. Today I will show you the actual dynamic stack program where nodes are created and deleted as per requirements.
Codes of the stack program
# include< stdio.h>
# include< stdlib.h>
struct link
{
int info;
struct link *next;
};
void display(struct link *rec)
{
while(rec != NULL)
{
printf(" %d ",rec->info);
rec = rec->next;
}
}
struct link * push(struct link *rec)
{
struct link *new1;
printf("\n Enter value for stack:-");
new1 = (struct link *)malloc(sizeof(struct link));
scanf("%d", &new1->info);
new1->next = rec;
/* next pointer of new1 is holding the address of the first node of the list. so new1 is the first node now.*/
rec = new1;
/* from this point the pointer rec is pointing the first node of the list. */
return rec;
}
struct link * pop(struct link *rec)
{
struct link *temp;
if(rec == NULL)
{
printf("\n Stack is empty");
}
else
{
/*rec is pointing the first node of the list.*/
temp = rec->next;
/*temp is pointing the second node of the list. */
free(rec);
rec = temp;
printf("\n After pop operation the stack is as follows:\n");
display(rec);
if(rec == NULL)
printf("\n Stack is empty");
}
return rec;
}
int selection()
{
int choice;
do
{
printf("\n 1<-Push ");
printf("\n 2<-Pop");
printf("\n 3<-Quit");
printf("\n Input your choice :");
scanf("%d", &choice);
if(choice <1 || choice >3)
printf("\n Incorrect choice-> Try once again");
} while(choice <1 || choice >3);
return choice;
}
void main()
{
struct link *start ;
int choice;
clrscr();
start = NULL;
do
{
choice = selection();
switch(choice)
{
case 1:
start = push(start);
printf("\n After push operation stack is as follows:\n");
display(start);
break;
case 2:
start = pop(start);
break;
default :
printf("\n End of session");
}
} while(choice != 3);
getch();
}
Technical analysis of this stack program
‘struct link *start ;’ is the list pointer which will point the top of the stack. Initial value of this pointer is NULL. Two functions are defined in this program on stack. One is ‘struct link * push(struct link *rec)’ and the other is ‘struct link * pop(struct link *rec)’. Both the functions are return type, returning the address of top of the stack. Both the functions take the front node address of the stack as argument.
On calling the ‘push’ function, new node is dynamically created and the internal pointer is made to point the top of the stack. The address of the new node is returned to ‘void main()’, thus the new node is set on the top of the stack. Similarly when ‘pop ()’ function is called, the node at the front is removed and address of the next location is returned.
No comments:
Post a Comment