Stack ADT - Introduction and Implementation


A stack is a data structure and generally called as stack ADT (abstract data type). Stack can be implemented using arrays or linked lists. Read this article for an introduction of stack and C programs to implement stack using arrays and linked lists.

Introduction to Stack


A Stack is a data structure which follows FILO (first in last out) principle. The element which is entered first into the stack (first in) is the element which can be last deleted from the stack (last out). Two operations PUSH and POP are commonly used for stack. Here, PUSH means insertion and POP means deletion. Operations like insertion, deletion can be performed at only one end of a stack. A pointer called TOP is used for stacks. Here, TOP represents the end at which insertion and deletion can be performed. There are some other operations for stacks which are PEEK, ISFULL and ISEMPTY. Here, PEEK is used to get the first element of the stack without removing it and ISFULL, ISEMPTY are used to check whether the stack is full (over flow error) or empty (under flow error) respectively. Let us take some real life examples. We put dinner plates to wash one on one and we put playing cards one on one etc,. In the both cases, what gets first into the line (stack) gets out last from the line (stack) i.e. FILO principle. The image below shows a stack, its operations (only insertion and deletion but not others) and the TOP pointer.
Stack ADT

Implementation of Stack


Stack can be implemented using arrays or linked lists.

C Program to implement stack using arrays


Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 5
int stack[SIZE];
int top=-1;
int underflow()
{
if(top==-1)
{
printf("\n Stack is Empty");
return 0;
}
else
return 1;
}
int overflow()
{
if(top==SIZE-1)
{
printf("\n Stack is Full");
return 1;
}
else
return 0;
}
void push(int item)
{
top=top+1;
stack[top]=item;
}
void pop()
{
printf("\n Element %d is popped from the stack",stack[top]);
top=top-1;
}
void display()
{
int i;
for(i=top;i>-1;i--)
printf("%d ",stack[i]);
}
void menu()
{
int choice,item;
printf("\n\n STACK OPERATIONS");
printf("\n 1.Push");
printf("\n 2.Pop");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
if(overflow()==0)
{
printf("\n Enter the item to be pushed : ");
scanf("%d",&item);
push(item);
}
getch();
menu();
break;
case 2:
if(underflow()==1)
pop();
getch();
menu();
break;
case 3:
if(underflow()==1)
{
printf("\n Stack is : ");
display();
}
getch();
menu();
break;
case 4:
exit(1);
break;
default:
printf("\n Your choice is invalid");
menu();
break;
}
}
void main()
{
clrscr();
menu();
}

Output
STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 25

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 59

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 17

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 5

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 35

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 3
Stack is : 35 5 17 59 25

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 35 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 5 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 17 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 3
Stack is : 59 25

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 59 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 25 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Stack is Empty

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 5
Your choice is invalid

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 4

C Program to implement stack using linked lists


Program
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct stack
{
int info;
struct stack *next;
}*top,*newnode,*ptr;
int underflow()
{
if(top==NULL)
{
printf("\n Stack is Empty");
return 0;
}
else
return 1;
}
void push(int item)
{
newnode=(struct stack*)malloc(sizeof(struct stack));
newnode->info=item;
if(top==NULL)
{
top=newnode;
newnode->next=NULL;
}
else
{
newnode->next=top;
top=newnode;
}
}
void pop()
{
printf("\n Element %d is popped from the stack",top->info);
top=top->next;
}
void display()
{
int i;
ptr=top;
i=1;
while(ptr!=NULL)
{
ptr=ptr->next;
i++;
}
ptr=top;
i=i-1;
while(ptr!=NULL)
{
printf("%d ",ptr->info);
ptr=ptr->next;
i--;
}
}
void menu()
{
int choice,item;
printf("\n\n STACK OPERATIONS");
printf("\n 1.Push");
printf("\n 2.Pop");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the item to be pushed : ");
scanf("%d",&item);
push(item);
getch();
menu();
break;
case 2:
if(underflow()==1)
pop();
getch();
menu();
break;
case 3:
if(underflow()==1)
{
printf("\n Stack is : ");
display();
}
getch();
menu();
break;
case 4:
exit(1);
break;
default:
printf("\n Your choice is invalid");
menu();
}
}
void main()
{
clrscr();
menu();
}

Output
STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 25

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 59

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 3
Stack is : 59 25

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 17

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 5

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 1
Enter the item to be pushed : 35

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 3
Stack is : 35 5 17 59 25

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 35 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 5 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 17 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 59 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 2
Element 25 is popped from the stack

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 3
Stack is Empty

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 5
Your choice is invalid

STACK OPERATIONS
1.Push
2.Pop
3.Display
4.Exit
Enter your choice : 4


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: