Stack |1
STACK
Stack is a restricted linear data structure in which insertion and deletion of data items take
place at one end. The insertion and deletion end of the Stack called the TOP end. Stack is called
a LIFO List (Last in First Out) as the items inserted last is deleted first.
Basic Stack Operations:
1. PUSH: This operation inserts an item at the top of the stack. Once an item is pushed, the
TOP pointer now points to newly inserted item.
2. POP: This operation removed the item from top of the stack. Top is decremented on each
pop operation.
State/ Error conditions in a Stack
1. Overflow: If a Stack is full, a new item cannot be pushed. This state of stack is called
stack overflow. So Push operation failed.
2. Underflow: When a Stack is empty and we want a pop operation. Then this situation is
called underflow. So pop operation is failed.
Example: Consider an array implemented empty Stack of Size=5, show the status of the Stack
stepwise after following operations are made
PUSH(10), PUSH(20),PUSH(30), POP, PUSH(40), PUSH(50), POP, PUSH(60),PUSH(70), PUSH(80),
POP
Assuming Array index starts with 1
Operations STACK TOP
TOP=0
PUSH(10) 10 TOP=1
PUSH(20) 10 20 TOP=2
PUSH(30) 10 20 30 TOP=3
SSG Mishra
Stack |2
POP 10 20 TOP=2
PUSH(40) 10 20 40 TOP=3
PUSH(50) 10 20 40 50 TOP=4
POP 10 20 40 TOP=3
PUSH(60) 10 20 40 60 TOP=4
PUSH(70) 10 20 40 60 70 TOP=5
PUSH( 80) 10 20 40 60 70 Error! UNDERFLOW
POP 10 20 40 60 TOP=4
Algorithm to PUSH an element in a Stack.
PUSH (STACK , MAX , TOP , item)
//This Algorithm inserts an element item into STACK.
1. IF TOP = MAX THEN // Is Stack Full
2. Write “OVERFLOW” and Return.
//End IF
3. TOP = TOP + 1
4. STACK[TOP] = item // inserts new element
5: Return.
Algorithm to POP an element from a Stack.
POP (STACK , MAX , TOP)
//This algorithm deletes an element from STACK and assigns it to item
1. IF TOP = 0 THEN // Stack is empty
2. Write “UNDERFLOW” and Return.
//End of IF
3. item = STACK [TOP].
4. TOP = TOP - 1
5. Return item.
Exercise: Write an algorithm to print the elements of a stack:
Implementation of Stack in C language
A Stack can be implemented in following ways.
I) Using Array
II) Using Linked List
SSG Mishra
Stack |3
Array implemented Stack
Array implementation of Stack is already described .Only difference is the starting index. While
implementing in C Language modify the start index of array to 0 and change the other code
accordingly.
Program: Write a menu design program to implement following operations on a Array
implemented Stack
/* Array implemented stack*/ void push(int num)
#include"stdio.h" {
#include"stdlib.h" if(top== MAX -1)
#define MAX 10 {
int stack[MAX], top= -1; printf("Overflow");
void push(int); return;
int pop(); }
void display(int); top = top + 1;
int main(){ stack[top] = num;
char ch; }
int choice,num;
do { int pop()
printf("\n 1:PUSH."); {
printf("\n 2:POP."); int d;
printf("\n 3:DISPLAY."); if(top == -1)
printf("\n 4:EXIT."); {
printf("\n Enter Your Choice(1,2,3,4):"); printf("Underflow!");
scanf("%d",&choice); return 0;
switch(choice) }
{ else
case 1: {
printf("Enter The Number To Be Insert:"); d=stack[top];
scanf("%d",&num); top=top-1;
push(num); return d;
break; }
case 2: }
printf(" %d is deleted",pop());
break;
case 3: display(top); void display(int i)
break; {
case 4: exit(0); while(i>=0)
} {
printf("\nDo U want to Continue:"); printf(" %d", stack[i]);
getchar(); i= i- 1;
ch=getchar(); }
}while(ch=='y'); }
return 0;
}
SSG Mishra
Stack |4
Linked List Implemented Stack: A linked list is used where a node represents one data items.
For Push operation, a node is added by storing its address in address part of its previous node.
For POP operation, a node can be deleted by making TOP pointer points to the previous node.
Program: Write a menu design program to implement following operations on a Linked
List implemented Stack
#include"stdio.h" void push(int num)
#include"stdlib.h" {
struct stack { curr=(struct stack*)malloc(sizeof(struct stack));
int data; if(curr==NULL){
struct stack *next; printf("Overflow");
}; return;
struct stack *top=NULL,*curr; }
void push(int); curr->data=num;
int pop(void); curr->next=NULL;
void display(struct stack*); if(top==NULL)
int main() top=curr;
{ else {
char ch; curr->next=top;
int choice,num; top=curr;
do { }
printf("\n 1:PUSH."); }
printf("\n 2:POP."); int pop()
printf("\n 3:DISPLAY");
{
printf("\n 4:EXIT.");
int d=NULL;
printf("\n Enter Your Choice(1,2,3,4):"); if(top==NULL){
scanf("%d",&choice);
printf("ERROR! Underflow");
switch(choice)
return d;
{ }
case 1:printf("Enter Number To Push:"); Else {
scanf("%d",&num);
d=top->data;
push(num);
curr=top;
break; top=top->next;
case 2: num=pop();
free(curr);
printf("%d is popped",num);
return d;
break; }
case 3: display(top); }
break;
case 4: exit(0); void display(struct stack *m)
} {
printf("\nDo U want to Continue:"); while(m!=NULL)
getchar(); {
ch=getchar(); printf(" %d",m->data);
}while(ch=='y'); m=m->next;
return 0; }
} }
SSG Mishra
Stack |5
Application of Stack
1. Arithmetic Expression(Polish Notation/ Reverse Polish Notation)
2. Parenthesis Matching Algorithm
3. String reversal Algorithm
1. Arithmetic Expression: An arithmetic expression consists of operands, operators and
parenthesis. Three commonly used arithmetic expressions are:
a) Infix expression: In This notation, the operator is place between two operands (for binary
operator). This notation is used in the mathematical operations by the human beings.
E.g. To add 6 and 8, we write 6 + 8.
b) Prefix expression: In this expression, operator is present before the operands. This
expression is named after a Polish Mathematician Jan Lukasiewicz, so it is otherwise called
Polish Notation.
E.g. To add 6 and 8, we write + 6 8
c) Postfix expression: In this expression, operator is present after the operands. As this
expression is just the reverse of Polish notation, so it is otherwise called Reverse Polish
Notation. This type of expression is implemented in digital device for any calculation.
E.g.: To multiply 6 and 8, we write 6 8 *.
For an Infix notation 5 * 3 + 9 / 3, the postfix and prefix form are as follows:
Prefix: +*53/93
Postfix: 5 3 * 9 / 3 +
Conversion of Infix notation to postfix notation
InfixToPostfix (I)
//This algorithm converts an Infix notation (I) to postfix notation
1. Push ‘(‘ into Stack and add ' ) ' to the end of I
2. Scan I from left to right and repeat step 3 to 10 for each symbol of I until stack is empty.
3. IF symbol is an operand, then add it to P.
4. IF symbol is '(‘ , Push it into stack.
5. IF symbol is an operator( ) then
6. Repeatedly pop from stack and add to P, each operator on the top which has same or
higher precedence than the scanned operator( )
SSG Mishra
Stack |6
7. Add operator into stack
8. IF symbol is ') then
9. Repeatedly pop from stack and add to P each operator on top of stack until ‘(‘.
10. Remove ‘(‘
//End of Loop
11. Return P.
Problem:- Convert to postfix expression
1. A * B + C / D * E * F ^ G - H
2. ( ( A - ( B + C ) * D ) $ ( E + F )
3. 10 + 6 / 3 * 7 – 9 ^ 3
4. A – B / C * D ^ E
Evaluation of postfix expression
PostfixEvaluation(P)
//This algorithm returns the value of postfix expression P
1. FOR each symbol(s) in P
2. IF Symbol(s) is an operand, THEN PUSH(s)
3. IF Symbol(s) is an operator( ) THEN
4. A = pop()
5. B = pop()
6. C = B A
7. PUSH (C)
8. value = pop()
9. Return value
Problem: Evaluate 5 3 – 9 3 / +
Solution:
Symbol Stack Action
5 5 push 5
3 5,3 Push 3
- 2 A = 3,B=5,C= B – A ,push(A)
9 2,9 Push 9
3 2,9,3 push 3
/ 2,3 A= 3, B = 9,C = 9/ 3 = 3, Push 3
+ 5 A=3 3, B = 2,C = 2+3, push 5
End
value = pop() = 5
SSG Mishra
Stack |7
Conversion of infix to prefix Notation
InfixToPrefix (I)
//This algorithm converts an infix notation (I) to prefix notation P
1. Push ')’ into stack, and add ‘(‘ to the beginning of P
2. Scan I from Right to left and repeat step 3 to 6 until stack is empty
3. IF the symbol is an operand, THEN Add it to P
4. IF the symbol is a ‘)’ THEN is push it into stack.
5. IF the symbol is an Operator, THEN
6. Repeatedly pop from stack and add to P, each operator on the top of
stack which have higher precedence that the operator ( )
7. Push (O) into stack
8. IF the symbol is ‘(‘ THEN
9. Repeatedly pop form stack and add to p, each operator on the top of
stack until ‘)’.
10. Remove ‘)’
11. //End of loop
12. Return Reverse (P)
Program: Convert of infix notation to postfix
#include"stdio.h"
#include"stdlib.h"
#include<string.h>
#define MAX 100
void push(char);
char pop(void);
char stack[100],top=-1;
int main() {
int i=0;
char a[MAX],ch;
printf("\n Enter a Infix Expression(put space between numbers):");
gets(a);
strcat(a,")");
push('(');
while(top!=-1) {
switch(a[i]) {
case '(':
push('(');
break;
case ')':
do {
ch=pop();
if(ch!='(')
printf(" %c",ch);
}while(ch!='(');
break;
case '+':
ch=pop();
SSG Mishra
Stack |8
while(ch!='(') {
printf(" %c",ch);
ch=pop();
}
push(ch);
push(a[i]);
break;
case '-':
ch=pop();
while(ch!='(') {
printf(" %c",ch);
ch=pop();
}
push(ch);
push(a[i]);
break;
case '*':
ch=pop();
while( ch=='/' || ch=='*' || ch=='^') {
printf(" %c",ch);
ch=pop();
}
push(ch);
push(a[i]);
break;
case '/':
ch=pop();
while(ch=='*' || ch=='/' || ch=='^') {
printf(" %c",ch);
ch=pop();
}
push(ch); void push(char num)
push(a[i]); {
break; stack[++top] = num;
case '^': }
ch=pop();
while(ch=='^') {
printf(" %c",ch); char pop(void)
ch=pop(); {
} char c;
push(ch); c=stack[top];
push(a[i]); top=top-1;
break; return c;
default: }
printf("%c",a[i]);
}
i++;
}
return 0;
}
SSG Mishra