Stack ADT
B.BHUVANESWARAN
ASSISTANT PROFESSOR (SS) / CSE
RAJALAKSHMI ENGINEERING COLLEGE
RAJALAKSHMI NAGAR
THANDALAM
CHENNAI 602 105
Introduction
A stack is a list with the restriction that insertions
and deletions can be performed in only one position,
namely, the end of the list, called the top.
It follows Last-In-First-Out (LIFO) principle.
Operations on Stack
Push - which is equivalent to insert
Pop - which deletes the most recently inserted
element
Top - return top of stack
MakeEmpty - create an empty stack
IsEmpty - check whether a stack is empty
IsFull - check whether a stack is full
Stack Model
Top 4 50
40
30
20
10
Push
The process of inserting a new element to the top of
the stack is called push operation.
For every push operation the top is incremented by 1.
Top 1 20
Top 0 10 10
Top -1 Empty Stack After After
inserting an inserting an
element 10 element 20
Pop
The process of deleting an element from the top of
stack is called pop operation.
After every pop operation the top pointer is
decremented by 1.
Top 2 30
20 Top 1 20
10 10 Top 0 10
Initial Stack After the After the
element 30 element 20
is deleted is deleted
Exceptional Conditions
Overflow
Underflow
Overflow
Attempt to insert an element when the stack is full is
said to be overflow.
Top 4 50
40
30
20
10
Underflow
Attempt to delete an element, when the stack is
empty is said to be underflow.
Top -1
Implementation of Stacks
Array
Linked list
Array Implementation of Stack
In this implementation each stack is associated with
a top pointer, which is -1 for an empty stack.
Push
To push an element X onto the stack, top pointer is
incremented by 1 and then set:
Stack [top] = X.
Pop
To pop an element from the stack, the Stack [top]
value is returned and the top pointer is decremented
by 1.
Exceptional Conditions
Pop on an empty stack or push on a full stack will
exceed the array bounds.
Routine to Check whether a Stack is Full
int IsFull()
{
if(top == MAX - 1)
return 1;
else
return 0;
}
Routine to whether a Stack is Empty
int IsEmpty()
{
if(top == -1)
return 1;
else
return 0;
}
Routine to Push an Element on to the Stack
void Push(int ele)
{
if(IsFull())
printf("Stack Overflow...!\n");
else
{
top = top + 1;
Stack[top] = ele;
}
}
Routine to Pop an Element from the Stack
void Pop()
{
if(IsEmpty())
printf("Stack Underflow...!\n");
else
{
printf("%d\n", Stack[top]);
top = top - 1;
}
}
Routine to Return Top of Stack
void Top()
{
if(IsEmpty())
printf("Stack Underflow...!\n");
else
printf("%d\n", Stack[top]);
}
Routine to Display Stack Elements
void Display()
{
int i;
if(IsEmpty())
printf("Stack Underflow...!\n");
else
{
for(i = top; i >= 0; i--)
printf("%d\t", Stack[i]);
printf("\n");
}
}
Linked List Implementation of Stack
Push operation is performed by inserting an element
at the front of the list.
Pop operation is performed by deleting at the front
of the list.
Top operation returns the element at the front of the
list.
Type Declaration
struct node
{
int Element;
struct node *Next;
}*List = NULL;
typedef struct node Stack;
Routine to whether a Stack is Empty
int IsEmpty()
{
if(List == NULL)
return 1;
else
return 0;
}
Push
The push is implemented as an insertion into the
front of a linked list, where the front serves as the top
of the stack.
Example
Routine to Push an Element on to the Stack
void Push(int e)
{
Stack *NewNode = malloc(sizeof(Stack));
NewNode->Element = e;
if(IsEmpty())
NewNode->Next = NULL;
else
NewNode->Next = List;
List = NewNode;
}
Pop
Pop as a deletion from the front of the list.
Example
Routine to Pop an Element from the Stack
void Pop()
{
if(IsEmpty())
printf("Stack is Underflow...!\n");
else
{
Stack *TempNode;
TempNode = List;
List = List->Next;
printf("%d\n", TempNode->Element);
free(TempNode);
}
}
Top
Top is performed by examining the element in the
first position of the list.
Example
Routine to Return Top of Stack
void Top()
{
if(IsEmpty())
printf("Stack is Underflow...!\n");
else
printf("%d\n", List->Element);
}
Display
Routine to Display Stack Elements
void Display()
{
if(IsEmpty())
printf("Stack is Underflow...!\n");
else
{
Stack *Position;
Position = List;
while(Position != NULL)
{
printf("%d\t", Position->Element);
Position = Position->Next;
}
printf("\n");
}
}
Queries?
Thanks...!
