Experiment No: 02
Aim: Implement Stack ADT using array.
Theory:
Stack is a linear data structure based on LIFO (Last In First Out) principle in which the
insertion of a new element and removal of an existing element takes place at the same end
represented as the top of the stack.
To implement the stack, it is required to maintain the pointer to the top of the stack, which is
the last element to be inserted because we can access the elements only on the top of the stack.
LIFO(Last In First Out) Principle in Stack Data Structure:
This strategy states that the element that is inserted last will come out first. You can take a pile
of plates kept on top of each other as a real-life example. The plate which we put last is on the
top and since we remove the plate that is at the top, we can say that the plate that was put last
comes out first.
Representation of Stack Data Structure:
Stack follows LIFO (Last In First Out) Principle so the element which is pushed last is popped
first.
Basic Operations on Stack Data Structure:
In order to make manipulations in a stack, there are certain operations provided to us.
push() to insert an element into the stack
pop() to remove an element from the stack
peek() Returns the top element of the stack.
isEmpty() returns true if stack is empty else false.
isFull() returns true if the stack is full else false.
Push Operation in Stack Data Structure:
The push operation is used to insert an element into the stack. The new element is added at the
topmost position of the stack. However, before inserting the value, we must first check if
TOP=MAX–1, because if that is the case, then the stack is full and no more insertions can be
done. If an attempt is made to insert a value in a stack that is already full, an OVERFLOW
message is printed.
Algorithm for push operation
Step 1: IF TOP = MAX-1
PRINT
OVERFLOW [END OF IF]
Step 2: SET TOP = TOP + 1
Step 3: SET STACK[TOP] = VALUE
Step 4: END
Pop Operation in Stack Data Structure:
The pop operation is used to delete the topmost element from the stack. However, before
deleting the value, we must first check if TOP=NULL because if that is the case, then it means
the stack is empty and no more deletions can be done. If an attempt is made to delete a value
from a stack that is already empty, an UNDERFLOW message is printed.
Algorithm for pop operation
Step 1: IF TOP = NULL
PRINT
UNDERFLOW [END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP - 1
Step 4: END
Peek Operation in Stack Data Structure:
Peek is an operation that returns the value of the topmost element of the stack without deleting
it from the stack. However, the Peek operation first checks if the stack is empty, i.e., if TOP =
NULL, then an appropriate message is printed, else the value is returned.
Algorithm for peek operation
Step 1: IF TOP = NULL
PRINT STACK IS EMPTY
Goto Step 3
Step 2: RETURN STACK[TOP]
Step 3: END
Display Operation in Stack Data Structure:
Display operation shows all the elements present in stack from bottom to top.
Algorithm for display operation:
Step 1: IF TOP = NULL
PRINT STACK IS EMPTY
Goto Step 3
Step 2: for i from 0 to TOP:
PRINT STACK[i]
Step 3: END
Applications of stack:
1. Reversing a list
2. Parentheses checker
3. Conversion of an infix expression into a postfix expression
4. Evaluation of a postfix expression
5. Conversion of an infix expression into a prefix expression
6. Evaluation of a prefix expression
7. Recursion
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define n 5
int s[5], top=-1;
void main()
{
int x;
int a;
void push(int);
void pop();
void peek();
void display();
while(1)
{
printf("\n 1. PUSH");
printf("\n 2. POP");
printf("\n 3. display");
printf("\n 4. Peek");
printf("\n 5. exit \n");
printf("Enter your choice \n");
scanf("%d",&a);
switch(a)
{
case 1: printf("Enter the element \n");
scanf("%d", &x);
push(x);
break;
case 2: pop();
break;
case 3: display();
break;
case 4: peek();
break;
case 5: exit(0);
}
getch();
}
}
void push(int x)
{
if(top==n-1)
{
printf("Stack is full \n");
}
else
{
top++;
s[top]=x;
}
}
void pop()
{
int x;
if(top==-1)
{
printf("The Stack is empty \n");
}
else
{
x=s[top];
top--;
printf("The popped element is %d \n", x);
}
}
void peek()
{
printf("Top element of stack is %d. \n", s[top]);
}
void display()
{
int i;
if(top==-1)
{
printf("The Stack is empty \n");
}
else
{
printf("The elements of the stack are \n");
for(i=0;i<=top;i++)
printf("%d\t", s[i]);
}
}
Conclusion:
The programmer can perform various operations on stack. The code handles overflow and
underflow conditions properly by displaying appropriate messages. Thus, it helps
programmer to understand how stack can be implemented using array.
