Stack ADT – Evaluating arithmetic expressions- other applications- Queue ADT – circular queue implementation – Double ended Queues – applications of queues
STACK
- Stack is a Linear Data Structure that follows Last In First Out(LIFO) principle.
- Insertion and deletion can be done at only one end of the stack called TOP of the stack.
- Example: – Pile of coins, stack of trays
STACK ADT:
TOP pointer
It will always point to the last element inserted in the stack. For empty stack, top will be pointing to -1. (TOP = -1) Operations on Stack (Stack ADT)
Two fundamental operations performed on the stack are PUSH and POP.
- PUSH:
It is the process of inserting a new element at the Top of the stack.
For every push operation:
- Check for Full stack ( overflow ).
- Increment Top by 1. (Top = Top + 1)
- Insert the element X in the Top of the stack.
- POP:
It is the process of deleting the Top element of the stack.
For every pop operation:
- Check for Empty stack ( underflow ).
- Delete (pop) the Top element X from the stack
- Decrement the Top by 1. (Top = Top – 1 )
Exceptional Conditions of stack
- Stack Overflow
- An Attempt to insert an element X when the stack is Full, is said to be stack overflow.
- For every Push operation, we need to check this condition.
- Stack Underflow:
- An Attempt to delete an element when the stack is empty, is said to be stack underflow.
- For every Pop operation, we need to check this condition.
Stack can be implemented in 2 ways.
- Static Implementation (Array implementation of Stack)
- Dynamic Implementation (Linked List Implementation of Stack)
- Array Implementation of Stack
- Each stack is associated with a Top pointer.
- For Empty stack, Top = -1.
- Stack is declared with its maximum size.
Array Declaration of Stack:
#define ArraySize 5 int S [ Array Size];
or
int S [ 5 ];
- Stack Empty Operation:
- Initially Stack is Empty.
- With Empty stack Top pointer points to – 1.
- It is necessary to check for Empty Stack before deleting (pop) an element from the stack.
Routine to check whether stack is empty
| int IsEmpty( Stack S ) { if( Top = = – 1 ) return(1) |
- Stack Full Operation:
- As we keep inserting the elements, the Stack gets filled with the elements.
- Hence it is necessary to check whether the stack is full or not before inserting a new element into the stack.
| int IsFull ( Stack S ) { if( Top = = Arraysize – 1 ) return(1); |
Routine to check whether a stack is full
| int IsFull ( Stack S ) { if( Top = = Arraysize – 1 ) return(1); |
(ii) Push Operation
- It is the process of inserting a new element at the Top of the stack.
- It takes two parameters. Push(X, S) the element X to be inserted at the Top of the Stack S.
- Before inserting an Element into the stack, check for Full Stack.
- If the Stack is already Full, Insertion is not possible.
- Otherwise, Increment the Top pointer by 1 and then insert the element X at the Top of the Stack.
Routine to push an element into the stack
void Push ( int X , Stack S )
{
if ( Top = = Arraysize – 1)
Error(“Stack is full!!Insertion is not possible”);
else
{ Top = Top + 1; S [ Top ] =X;
}
}
Pop Operation
- It is the process of deleting the Top element of the stack.
- It takes only one parameter. Pop(X).
- The element X to be deleted from the Top of the Stack.
- Before deleting the Top element of the stack, check for Empty Stack.If the Stack is Empty, deletion is not possible.
Routine to Pop the Top element of the stack
void Pop ( Stack S )
{
if ( Top = = – 1)
Error ( “Empty stack! Deletion not possible”);
else
{ X = S [ Top ] ;
Top = Top – 1 ;
}
}
- Return Top Element
- Pop routine deletes the Top element in the stack.If the user needs to know the last element inserted into the stack, then the user can return the Top element of the stack.
- To do this, first check for Empty Stack.If the stack is empty, then there is no element in the stack.
- Otherwise, return the element which is pointed by the Top pointer in the Stack.
Routine to return top Element of the stack
int TopElement(Stack S)
{
if(Top==-1)
{
Error(“Empty stack!!No elements”); return 0;
}
else
return S[Top];
}
Implementation of stack using Array
/* static implementation of stack*/
#include<stdio.h> #include<conio.h> #define size 5
int stack [ size ]; int top;
void push( )
{
int n ;
printf( “\n Enter item in stack” ) ; scanf( ” %d ” , &n ) ;
if( top = = size – 1)
{
}
else
{
printf( “\nStack is Full” ) ;
top = top + 1 ;
stack [ top ] = n ;
}
}
void pop( )
{
int item;
if( top = = – 1)
{
}
else
{
}
}
printf( “\n Stack is empty” );
item = stack[ top ] ;
printf( “\n item popped is = %d” , item ); top – -;
void display( )
{
int i;
printf(“\n item in stack are”); for(i = top; i > = 0; i –)
printf(“\n %d”, stack[ i ] );
}
void main( )
{
char ch,ch1; ch = ‘y’;
ch1 = ‘y’; top = -1; clrscr( );
while(ch !=’n’)
{
push( );
printf(“\n Do you want to push any item in stack y/n”); ch=getch( );
}
display( ); while( ch1!=’n’ )
{
printf(“\n Do you want to delete any item in stack y/n”); ch1=getch( );
pop( );
}
display( ); getch( );}
OUTPUT:
Enter item in stack20
Do you want to push any item in stack y/n Enter item in stack25
Do you want to push any item in stack y/n Enter item in stack30
Stack is Full
Do you want to push any item in stack y/n item in stack are
25
20
15
10
5
Do you want to delete any item in stack y/n item popped is = 25
Do you want to delete any item in stack y/n item popped is = 20
Do you want to delete any item in stack y/n item popped is = 15
item in stack are 10
5
Linked list implementation of Stack
- Stack elements are implemented using SLL (Singly Linked List) concept.
- Dynamically, memory is allocated to each element of the stack as a node.