Stack ADT

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())
else
printf("%d\n", Stack[top]);
}
Routine to Display Stack Elements
void Display()
{
int i;
if(IsEmpty())
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())
else
printf("%d\n", List->Element);
}
Display
Routine to Display Stack Elements
void Display()
{
if(IsEmpty())
else
{
Stack *Position;
Position = List;
while(Position != NULL)
{
printf("%d\t", Position->Element);
Position = Position->Next;
}
printf("\n");
}
}
Queries?
Thanks...!

Stack ADT

Uploaded by

Copyright:

Available Formats

Stack ADT

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Stack ADT

Uploaded by

Copyright:

Available Formats

Stack ADT

A stack is a list with the restriction that insertions

Push - which is equivalent to insert

The process of inserting a new element to the top of

Top -1 Empty Stack After After

The process of deleting an element from the top of

Initial Stack After the After the

Attempt to insert an element when the stack is full is

Attempt to delete an element, when the stack is

In this implementation each stack is associated with

To push an element X onto the stack, top pointer is

To pop an element from the stack, the Stack [top]

Pop on an empty stack or push on a full stack will

void Push(int ele)

Push operation is performed by inserting an element

typedef struct node Stack;

The push is implemented as an insertion into the

Pop as a deletion from the front of the list.

Top is performed by examining the element in the

You might also like