Data Structures (DS)
GTU # 3130702
Unit-2
Linear Data Structure
(Stack)
Stack
A linear list which allows insertion and deletion of an element at one end only is called stack.
The insertion operation is called as PUSH and deletion operation as POP.
The most accessible elements in stack is known as top.
The elements can only be removed in the opposite orders from that in which they were added to
the stack.
Such a linear list is referred to as a LIFO (Last In First Out) list.
Deletion
Insertion
C
B … …
A
TOP
Stack Cont…
A pointer TOP keeps track of the top element in the stack.
Initially, when the stack is empty, TOP has a value of “-1”.
Each time a new element is inserted in the stack, the pointer is incremented by “one” before,
the element is placed on the stack.
The pointer is decremented by “one” each time a deletion is made from the stack.
Applications of Stack
Recursion
Evaluation of expressions
Reversing characters
Microsoft Word (Undo / Redo)
Procedure : PUSH (S, TOP, X)
This procedure inserts an element X to the top of a stack.
Stack is represented by a vector S containing N elements.
A pointer TOP represents the top element in the stack.
1. [Check for stack overflow] Stack is empty, TOP = -1, N=3 TOP = 2 -5
If TOP > N TOP = 1 8
Then write (‘STACK OVERFLOW’) PUSH(S, TOP, 10) TOP = 0 10
Return S
2. [Increment TOP] PUSH(S, TOP, 8)
TOP ← TOP + 1
PUSH(S, TOP, -5)
3. [Insert Element]
S[TOP] ← X
PUSH(S, TOP, 6)
4. [Finished]
Return Overflow
Function : POP (S, TOP)
This function removes & returns the top element from a stack.
Stack is represented by a vector S containing N elements.
A pointer TOP represents the top element in the stack.
1. [Check for stack underflow] POP(S, TOP) TOP = 2 -5
If TOP = -1 TOP = 1 8
TOP = 0 10
Then write (‘STACK UNDERFLOW’) POP(S, TOP)
TOP = -1 S
Return (0)
2. [Decrement TOP] POP(S, TOP)
TOP ← TOP - 1
3. [Return former top element of POP(S, TOP)
stack]
Return(S[TOP + 1])
Underflow
Stack implementation using arrays
#include<stdio.h>
//stack Abstract Data Type with specification
#define max 10 //maximum size of stack
int stack[max];
int top=-1; // Initialization to -1 indicates stack is empty
//Stack operations
void push(int val);
int pop();
void display();
int isEmpty();
int isFull();
isFull and push
//function to check whether stack is full or not
int isFull ()
{
if(top==max-1) //if top is equals to max position then Stack overflow
return 1;
else
return 0;
}
//function to push an element into stack
void push(int val)
{
/* element to be pushed onto stack if it is not full*/
if (!isFull()) // stack is not full
{
top++; //increment top to next position
stack[top]=val; //assigning val to stack[top]
}
else
printf("Stack overflow");
}
isEmpty and pop
//function to check whether stack is empty or not
int isEmpty()
{
if(top==-1) //if top is -1 then Stack is Empty and it returns 1
return 1;
else
return 0; //if stack is not empty it returns 0
}
//function to pop an element from the stack
int pop()
{
if (!isEmpty()) // The stack is not empty
{
printf("\nThe pop element is \t%d",stack[top]);
top--; //decrement top
}
else
printf( "\n Stack is Empty no items to pop");
return 0;
}
Displaying the stack elements
//function to display the stack elements
void display()
{
int i ;
if (!isEmpty())
{
printf("\n ****elements of stack****");
for(i=top;i>=0;i--) //display stack elements
printf("\n %d\t",stack[i]);
}
else
printf("\n stack is Empty.");
}
main handler function
int main()
{ int choice, item; // item is to be pushed on to stack
do
{
printf("\n menu");
printf("\n1:push\t2:pop\t3:display\t4:exit");
printf("\n Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter an element to push: ");
scanf("%d",&item);
push(item);
break;
case 2: pop();
break;
case 3: display();
break;
}
}while(choice !=4);
return 0;
}