Stacks:
A stack is a
non-primitive linear data structure
It is an ordered
list in which addition of new data item and deletion of already existing data
item is done from only one end, known as top
of stack.
As the deletion and
insertion is done from top of the stack the last added element will be the
first to be removed from the stack. That is why stack is also called last-in-first-out (LIFO) type of list.
Here most
accessible element is top most element and last accessible element is the
bottom of the stack.
Representation:
Stack
implementation:
Stack can be
implemented in two ways.
1. Static implementation (using arrays)
2. Dynamic implementation (using pointers i.e., linked
lists)
1. Static implementation:
Static implementation uses arrays to
create stack.
It is a very simple
technique, but is not a flexible way of creation, as the size of stack has to
be declared during program design, after that the size cannot be varied.
As the size of array
is fixed, when we want to store only few elements then memory will be wasted
and also when we want to store more number of elements then we can’t change the
size of array.
2. Dynamic
implantation:
Dynamic
implementation is also called linked
list representation i.e., we implement the stack by using linked lists.
Linked list
representation uses pointers to
implement the stack type of data structure.
Operation on
Stack:
We can perform two Operations by using stacks.
(1) PUSH
(2) POP
(1) PUSH:
The process of
adding new element to the top of the stack is called PUSH Operation.
When we add new
element to the top of the stack every time, the top is incremented by one.
In case array is full and no new element can be
inserted then that condition is called stack
overflow or full.
In case of stack over flow condition,
top= Max. sizeof array -1;
(2) POP:
The process of deleting an element from
toop of the stack is called pop Operation.
After every POP
Operation the stack is decremented by one.
If there is no
element present and id no POP Operation is performed then thet condition is
called Stack underflow or empty.
In case of stack
underflow condition,
top= -1;
Program to demonstrate the
operations performed on stack using arrays:
#include<process.h>
#include<conio.h>
#include<stdio.h>
void push();
int pop();
void traverse();
int stack[5];
int top=-1;
void main()
{
int choice;
do
{
clrscr();
printf("1.push");
printf("2.pop");
printf("3.traverse");
printf("4.exit");
printf("enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1:push();
break;
case
2:printf("deleted element is %d",pop());
break;
case 3:traverse();
break;
case 4:exit(0);
}
}while(choice!=4);
}
void push()
{
int item;
if(top==4)
printf("stack is full");
else
{
printf("enter
element to insert");
scanf("%d",&item);
top=top+1;
stack[top]=item;
}
}
int pop()
{
int item;
if(top=-1)
printf("stack is empty");
else
{
item=stack[top];
top=top-1;
}
return(item);
}
void traverse()
{
if(top==-1)
printf("stack empty");
else
{
for(int
i=0;i<=top;i++)
{
printf("%d",stack[i]);
}
}
}
Program to demonstrate linked
implementation of stacks:
#include<stdio.h>
#include<conio.h>
struct stack
{
int num;
struct stack *next;
}*top=NULL;
typedef struct stack
st;
void push();
int pop();
void display();
void main()
{
int choice,item;
do
{
clrscr();
printf("1.push");
printf("2.pop");
printf("3.display");
printf("4.exit");
printf("enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1:push();
break;
case
2:item=pop();
printf("deleted elements is
%d",item);
break;
case
3:display();
break;
case
4:exit(0);
}
}while(choice!=4);
}
void push()
{
st *p;
p=(st*)malloc(sizeof(st));
printf("enter the
number");
scanf("%d",&p->num);
p->next=top;
top=p;
}
int pop()
{
st *p;
p=top;
if(top==NULL)
printf("stack is empty");
else
{
top=top->next;
return(p->num);
free(p);
}
}
void display()
{
st *p;
p=top;
while(p!=NULL)
{
printf("number=%d",p->num);
p=p->next;
}
printf("stack empty");
}
No comments:
Post a Comment