Stack
Stack
• stack is an ordered collection of homogeneous data
elements where the insertion and deletion operations take
place at one end only.
• insertion and 'deletion operations in the case of a stack are
specially termed PUSH and POP,respectively, and the
position of the stack where these operations are performed
is known as the TOP of the stack.
• element in a stack is termed an ITEM. The maximum number
of elements that a stack can accommodate is termed SIZE.
• stack is also called Last-In-First-Out (LIFO) type of list or First
in Last Out(FILO)
• Linear data structure
• Abstract Datatype
Stack
• Common model of a stack is plates in a marriage party. Fresh plates are “pushed”
onto the top and “popped” off the top.
• Some of you may eat biscuits. If you assume only one side of the cover is torn and biscuits are
taken off one by one. This is called popping and similarly, if you want to preserve some biscuits for
some time later, you will put them back into the pack through the same torn end called pushing.
Stack
OPERATIONS ON STACK
Basic operations that can be performed on stack are as follows :
1. PUSH : The process of adding a new element to the top of the stack is called PUSH
operation. Pushing an element in the stack involve adding of element, as the new element will
be inserted at the top, so after every push operation, the top is incremented by one. In case
the array is full and no new element can be accommodated, it is called STACK-FULL
condition. This condition is called STACK OVERFLOW.
2. POP : The process of deleting an element from the top of the stack is called POP
operation. After every pop operation, the stack is decremented by one. If there is no element
on the stack and the pop is performed then this will result into STACK UNDERFLOW
IMPLEMENTATION OF STACKS
Stack can be implemented in two ways :
(a) Static implementation
(b) Dynamic implementation
Push operation
Static implementation-Using Array
Algorithm for PUSH Operation
1) Start
2) Declare item
3) Check whether if Top= size-1, then go to step4 else go to step 5
4) Print Stack overflow. Insertion cannot be done go to step 8
5) Read the element to be inserted as item
6) Set Top=Top+1
7) Set Stack[Top]=item
8) Stop
Static implementation-Using Array
void push()
{
int item;
If(Top=Max-1) {
printf(“Stack Overflow insertion cannot be done”) ;}
else{
printf (“enter element to be inserted”) ;
scanf (“%d”, &item) ;
Top=Top+1;
Stack[Top]=item;}}
Pop
Static implementation-Using Array
Algorithm for POP Operation
1) Start
2) Declare item
3) Check whether if Top= -1, then go to step3 else go to step 4
4) Print Stack underflow. Deletion cannot be done go to step 7
5) Set item=Stack[Top]
6) Set Top=Top-1
7) Print the deleted item as item
8) Stop
Static implementation-Using Array
void pop()
{
int item;
If(Top==-1) {
printf (“stack underflow. Deletion cannot be possible “) ;}
else{
item=Stack[Top];
Top=Top-1;
printf (“Deleted item is%d”, item) ;}
Dynamic implementation-Using Linked List
Algorithm for PUSH()
1) Start
2) Declare a structure pointer new
3) Allocate memory to new
4) Read the element to be inserted as new->data
5) Assign new->next as Top
6) Assign Top as new
7) Stop
Dynamic implementation-Using Linked List
void push()
{
struct node *new;
new=(struct node*) malloc(sizeof(struct node)) ;
Printf(“enter element to be inserted”) ;
Scanf(“%d”, &new->data) ;
new->next=top;
Top=new;}
Dynamic implementation-Using Linked List
1) Start
2) Declare structure pointer Temp
3) Check if top==NULL Then print stack underflow and go to step8 else go to Step4
4) Assign temp as Top
5) Print temp->data
6) Assign top as temp>next
7) Delete temp
8) Stop
Dynamic implementation-Using Linked List
void pop()
{
struct node *temp;
if(Top==NULL) {
printf(“stack underflow”) ;}
else{
temp=Top;
printf (“deleted item is%d”, temp->data) ;
Top=temp ->next;
Free(temp);}