By: Dr.

Piyush Arora Data Structures using C

Stack
• Stack is non-primitive, linear, static or dynamic and homogeneous data structure.
• A stack is a linear data structure in which elements can be added or removed only at one end.
• The element is always inserted or deleted at Top of Stack (TOS / TOP).
• So, the last item to be added to a stack is the first item to be removed from the stack.
e.g.: Stack of plates in a cafeteria. During dinner time, the customers take plates from the top
of the stack and waiter puts the washed plates on the top of the stack.
• Stack is also called as last in first out (LIFO) data structure or LIFO lists.
• It can also be called as first in last out (FILO) data structure or FILO lists.
This is because, the element added at the top is the first to be removed.
• Stack looks like a restricted data structure, but it has many important applications in computer
science.
e.g.: we can use one feature of Ms. Word of “Copy”, wherein we can copy multiple texts,
images and paste them in reverse order.
Note: We can insert or delete only one element from the stack at one time.
Examples of stack: stack of plates on counter in a cafeteria, disks on a peg, railway shunting system.
• Assume, we declare a stack of size 4. That is int s[4];

Stack Terminologies and operations

• When stack “s” is initialized, “s.top” = -1 OR TOS = -1.
• For insertion, “s.top” increases by 1 and for deletion, “s.top” decreases by 1.
• So, to check, whether stack is empty or not, we can simply compare “s.top” with -1.
• Push: This operation is used to insert an element onto the stack by using TOS.
• Pop: This operation is used to delete an element from the stack by using TOS.
• Peep: This operation is used to extract information of element from the TOS.
• Change: This operation is used to change information of element on the TOS.
• When the stack becomes full and no more insertion is possible, then this condition is known as
“Stack Overflow”.
• When the stack is empty and no more deletion is possible, then this condition is known as “Stack
Underflow”.

Algorithms for operations on stack:

Note: peep and change or update, are not the actual operations on stack, because in stack, we can access only
top of stack (TOS). So, if you perform change operation, only TOS should be changed.
In peep(s), we move the pointer to the desired location in the stack and fetch the value of the ith location.
In update(s), we move the pointer to the desired location in the stack and update the value of the ith location.

Algorithm for PUSH operation

“s” represents stack
“tos” indicates top of stack
“value” indicates the element to be pushed
“SIZE” represents the number of elements in the stack
Step 1: [Check for Stack Overflow]
If tos == SIZE – 1 then
Output (“Stack Overflow”) and Exit
Step 2: [Increment top of stack (tos)]
tos = tos + 1

S. V. Patel College Page | 1

By: Dr. Piyush Arora Data Structures using C
Step 3: [Push Element in stack]
s[tos] = value
Step 4: Exit

Algorithm for POP operation

“s” represents stack
“tos” indicates top of stack
“value” indicates the element popped
Step 1: [Check for stack Underflow]
If tos == – 1
Output (“Stack Underflow”) and Exit
Step 2: [Perform Deletion operation]
value = s[tos]
Step 3: [Decrement top of stack (tos)]
tos = tos – 1
Step 4: [Display the popped element]
Output “value”
Step 5: Exit

Algorithm for PEEP operation

“s” represents stack
“tos” indicates top of stack
“value” indicates the peeped / displayed element
Step 1: [Check for stack underflow]
If tos == – 1
Output (“Stack Underflow”) and Exit
Step 2: [Perform peep operation on tos]
value = s[tos]
Step 3: [Display the peeped element]
Output “value”
Step 4: Exit

Algorithm for CHANGE / UPDATE operation

“s” represents stack
“tos” indicates top of stack
“value” indicates new element to be replaced against element at tos
Step 1: [Check for stack underflow]
If tos == – 1
Output (“Stack Underflow”) and Exit
Step 2: [Perform update operation on tos]
s[tos] = value
Step 3: Exit

Algorithm for DISPLAY operation

“s” represents stack
“tos” indicates top of stack
“i” is the variable used as counter in display operation
Step 1: [Check for stack underflow]
If tos == – 1
Output (“Stack Underflow”) and Exit
Step 2: [Initialize a counter “i” with “tos” for display operation]
i = tos
Step 3: [Check whether counter “i” is greater than or equal to “0”]
If (i >= 0)
Display element s[i]
Decrement “i” by 1
S. V. Patel College Page | 2
By: Dr. Piyush Arora Data Structures using C
Repeat step 3
Step 4: Exit

Program for operations on stack:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int tos = -1;

int stack[20];

void push(int value, int size);

void pop();
void peep();
void change(int value);
void display();

void main()
{
int ch, size, value;
printf("Enter the size of stack : ");
scanf("%d",&size);
do
{
printf("\n 0. Exit");
printf("\n 1. Push ");
printf("\n 2. Pop ");
printf("\n 3. Peep");
printf("\n 4. Change");
printf("\n 5. Display");
printf("\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 0:
exit(0);
break;
case 1:
printf("\nEnter the element to be pushed : ");
scanf("%d", &value); 30
push(value, size);
display();
break;
case 2:
pop();
display();
break;
case 3:
peep();
display();
break;
case 4:
printf("\nEnter the tos to be changed : ");
scanf("%d",&value);
change(value);
S. V. Patel College Page | 3
By: Dr. Piyush Arora Data Structures using C
display();
break;
case 5:
display();
break;
default:
printf("\n Enter Proper choice \n");
}
}
while(ch != 0);
}
void push(int value, int size)
{
if(tos == size – 1)
{
printf("\n ---Stack overflow--- \n");
return;
}
else
{
tos = tos + 1;
stack[tos] = value;
}
}
void pop()
{
int x;
if(tos == -1)
{
printf("\n ---Stack Underflow--- \n");
return;
}
else
{
x = stack[tos];
tos = tos - 1;
printf(“Popped element = %d”, x);
}
}
void peep()
{
if(tos == -1)
{
printf("\n Stack is empty \n");
return;
}
else
{
printf("\n TOS = %d",stack[tos]);
}
}
void change(int value)
{
if(tos == -1)
{
printf("\n Stack is empty \n");
S. V. Patel College Page | 4
By: Dr. Piyush Arora Data Structures using C
return;
}
else
{
stack[tos] = value;
}
}
void display()
{
int i;
if(tos == -1)
{
printf("\n Stack is empty -- underflow \n");
return;
}
printf("\n Stack Elements: \n");
for(i=tos ; i>=0 ; i--)
{
printf("Element = %d \n",stack[i]);
}
}

Uses of stack in computer system’s memory management

• The stack is the region of memory, where programs temporarily hold data as they execute.
• When program sends parameters to a function, the parameters are placed on the stack and when the
function completes, the items are popped out from the stack.
• Also, when the function passes local variables, the values of these local variables are stored on the
stack during the execution of the function. When the function completes, the variables are discarded.
e.g.: suppose we have three subprograms X, Y and Z. Suppose X calls Y and Y calls Z. Then Y will
not finish its work until Z has finished and returned.
Similarly, X will not finish its work until Y has finished and returned. They are executed in LIFO
order.
Z
Y Y Y
X X X X X

S. V. Patel College Page | 5

By: Dr. Piyush Arora Data Structures using C
Applications of Stack
1. Evaluation of arithmetic expression or Infix Notation
2. Conversion of infix to postfix / Reverse Polish Notation
3. Evaluation of postfix / Reverse Polish Notation
4. Conversion of infix to prefix / Polish Notation
5. Evaluation of prefix / Polish Notation
6. Implementation of Recursion

Introduction:
There are three notations to represent arithmetic expressions (AE).
a. Infix notation: In this notation, the operator comes between the two operands.
<operand> <operator> <operand>
e.g.: A+B A*B A-B A/B A^B
b. Prefix notation OR Polish Notation: In this notation, the operator comes before the two operands.
<operator> <operand> <operand>
e.g.: +AB *AB -AB /AB ^AB
c. Postfix notation OR Reverse Polish Notation: In this notation, the operator comes after two operands.
<operand> <operand> <operator>
e.g.: AB+ AB* AB- AB/ AB^

Evaluation of arithmetic expression

• To evaluate an arithmetic expression, we follow the rules of mathematics.
• We need to consider the associativity and precedence of operators.
Operators Precedence Associativity
() (brackets) 7
^(exponentiation) 6 Right to left
*(multiplication) and /(division) 5 Left to right
+(addition) and –(subtraction) 4 Left to right
<, >, <=, !=, >= 3 Left to right
AND 2 Left to right
OR, XOR 1 Left to right

Remember the following precedence for Conversions:

Infix To Postfix Infix To Prefix
^ 3 ^
*, / 2 *, /
+, - 1 +, -
“(” opening bracket 0 “)” closing bracket

Examples of Infix expressions:

1. A+B
2. A+B*C
3. A*B+C
4. A+B/C-D
5. (A+B)/(C-D)
6. ((B*C)+C/D^F)+G
7. A+B*C-D^E+F/G
8. A*(B+C)-(G+H)/L+P
9. A+((B*(C-D)^E)+F)/G
10. A^B*C-D+E/F/(G+H)
11. X*(Y+Z)/A-B*(C+D/E)
12. A*B-(C+D)-(E-F)+G/H^I
13. (A+B)*C*((C-D^E/F)+G)+H-I
14. A^B*(C+D)+(E-F)+G/(H+W)

S. V. Patel College Page | 6

By: Dr. Piyush Arora Data Structures using C
Direct Evaluation method (Shortcut method)

Conversion of Infix to Postfix / Reverse Polish Notation:

Algorithm to convert Infix expression to Postfix expression / Infix to Reverse Polish Notation
Input: “E” is an arithmetic expression in infix notation.
Output: An arithmetic expression in postfix notation. It is stored in array and displayed in same manner.
Data Structure: One stack “s1” is used for push and pop operation.
Push(s1, x) means adding “x” to stack s1.
Push(s1, item) means adding an “item” to stack s1.
Pop(s1) means removing the top most element from the stack s1.
“item” is the symbol scanned.
“x” is the symbol popped from stack s1.
Scan_ch( ): The method used to scan one item from left to right.
Write(x): The method used to write the variable “x” in output expression.
Write(item): The method used to write the variable “item” in output expression.
Precedence( ): The method used to check the precedence of operators.

Step 1: [Initially add a right parenthesis “)” at the end of the infix expression E].
Step 2: [Push left parenthesis “(” on to the stack]
Push (s1, “(”)
Step 3: [Repeat steps 4 to 21 while stack s1 is not empty]
Step 4: [Scan the symbol from Infix Expression in left to right manner]
Set item = E.Scan_ch( )
Step 5: If (item == operand)
Step 6: [Write the symbol into output expression]
Write (item)
[End of step 5 if structure)]
Step 7: If (item == “(”)
Step 8: [Push symbol “(” into the stack s1]
Push(s1, item)
[End of step 7 if structure]
Step 9: If (item == operator)
Step 10: x = Pop(s1)
Step 11: If precedence (x) >= precedence (item)
Step 12: Repeat steps 13 and 14 while (precedence (x) >= precedence (item))
Step 13: Write (x)
Step 14: x = Pop(s1)
[End of step 12 loop]
[End of step 11 if structure]
Step 15: Push(s1, x)
Step 16: Push(s1, item)
[End of step 9 if structure]
Step 17: If (item == “)”)
Step 18: x = Pop(s1)
Step 19: Repeat steps 20 and 21 while x ≠ “(“
Step 20: Write (x)
Step 21: x = Pop(s1)
[End of step 19 loop]
[End of step 17 if structure]
[End of step 3 loop]
Step 22: Exit

S. V. Patel College Page | 7

By: Dr. Piyush Arora Data Structures using C
Example 1: Given “E”: A+((B*(C-D)^E)+F)/G
Append a right parenthesis at the end of the expression, so it looks like:
A+((B*(C-D)^E)+F)/G)
Symbol Stack Expression
(
A ( A
+ (+ A
( (+( A
( (+(( A
B (+(( AB
* (+((* AB
( (+((*( AB
C (+((*( ABC
- (+((*(- ABC
D (+((*(- ABCD
) (+((* ABCD-
^ (+((*^ ABCD-
E (+((*^ ABCD-E
) (+( ABCD-E^*
+ (+(+ ABCD-E^*
F (+(+ ABCD-E^*F
) (+ ABCD-E^*F+
/ (+/ ABCD-E^*F+
G (+/ ABCD-E^*F+G
) ABCD-E^*F+G/+
Finally the expression is displayed in the same manner.
Answer: ABCD-E^*F+G/+

Example 2: Given “E”: A*(B+C)-(G+H)/L+P

Append a right parenthesis at the end: (A*(B+C)-(G+H)/L+P
Symbol Stack Expression
(
A ( A
* (* A
( (*( A
B (*( AB
+ (*(+ AB
C (*(+ ABC
) (* ABC+
- (- ABC+*
( (-( ABC+*
G (-( ABC+*G
+ (-(+ ABC+*G
H (-(+ ABC+*GH
) (- ABC+*GH+
/ (-/ ABC+*GH+
L (-/ ABC+*GH+L
+ (+ ABC+*GH+L/-
P (+ ABC+*GH+L/-P
) ABC+*GH+L/-P+
Finally the expression is displayed in the same manner.
Answer: ABC+*GH+L/-P+

S. V. Patel College Page | 8

By: Dr. Piyush Arora Data Structures using C
Example 3: Given “E”: A^B*C-D+E/F/(G+H)
Append a right parenthesis at the end: (A^B*C-D+E/F/(G+H))
Symbol Stack (S1) Stack (S2) / Expression
(
A ( A
^ (^ A
B (^ AB
* (* AB^
C (* AB^C
- (- AB^C*
D (- AB^C*D
+ (+ AB^C*D-
E (+ AB^C*D-E
/ (+/ AB^C*D-E
F (+/ AB^C*D-EF
/ (+/ AB^C*D-EF/
( (+/( AB^C*D-EF/
G (+/( AB^C*D-EF/G
+ (+/(+ AB^C*D-EF/G
H (+/(+ AB^C*D-EF/GH
) (+/ AB^C*D-EF/GH+
) AB^C*D-EF/GH+/+
Finally the expression is displayed in the same manner.
Answer: AB^C*D-EF/GH+/+

Example 4: Given “E”: (A+B)*C*((C-D^E/F)+G)+H-I

Append a right parenthesis at the end: (A+B)*C*((C-D^E/F)+G)+H-I)
Symbol Stack (S1) Stack (S2) / Expression
(
( ((
A (( A
+ ((+ A
B ((+ AB
) ( AB+
* (* AB+
C (* AB+C
* (* AB+C*
( (*( AB+C*
( (*(( AB+C*
C (*(( AB+C*C
- (*((- AB+C*C
D (*((- AB+C*CD
^ (*((-^ AB+C*CD
E (*((-^ AB+C*CDE
/ (*((-/ AB+C*CDE^
F (*((-/ AB+C*CDE^F
) (*( AB+C*CDE^F/-
+ (*(+ AB+C*CDE^F/-
G (*(+ AB+C*CDE^F/-G
) (* AB+C*CDE^F/-G+
+ (+ AB+C*CDE^F/-G+*
H (+ AB+C*CDE^F/-G+*H
- (- AB+C*CDE^F/-G+*H+
I (- AB+C*CDE^F/-G+*H+I
) AB+C*CDE^F/-G+*H+I-

S. V. Patel College Page | 9

By: Dr. Piyush Arora Data Structures using C
Finally the expression is displayed in the same manner.
Answer: AB+C*CDE^F/-G+*H+I-

Example 5: Given “E”: (A^B*(((C+D)+(E-F))+G)/(H+W)

Append a right parenthesis at the end: (A^B*(((C+D)+(E-F))+G)/(H+W))
Symbol Stack (S1) Stack (S2) / Expression
(
A ( A
^ (^ A
B (^ AB
* (* AB^
( (*( AB^
( (*(( AB^
( (*((( AB^
C (*((( AB^C
+ (*(((+ AB^C
D (*(((+ AB^CD
) (*(( AB^CD+
+ (*((+ AB^CD+
( (*((+( AB^CD+
E (*((+( AB^CD+E
- (*((+(- AB^CD+E
F (*((+(- AB^CD+EF
) (*((+ AB^CD+EF-
) (*( AB^CD+EF-+
+ (*(+ AB^CD+EF-+
G (*(+ AB^CD+EF-+G
) (* AB^CD+EF-+G+
/ (/ AB^CD+EF-+G+*
( (/( AB^CD+EF-+G+*
H (/( AB^CD+EF-+G+*H
+ (/(+ AB^CD+EF-+G+*H
W (/(+ AB^CD+EF-+G+*HW
) (/ AB^CD+EF-+G+*HW+
) AB^CD+EF-+G+*HW+/
Finally the expression is displayed in the same manner.
Answer: AB^CD+EF-+G+*HW+/

Program to convert Infix expression to Postfix expression / Infix to Reverse Polish Notation
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
enum item_list{opernd, oper, leftbrack, rightbrack};

enum item_list symbol_type(char c); // Function - name is symbol_type

int top=-1, stempty=1, stfull=0, loop_yn;

char stack[100];

void push(char c);

char pop();
int precedence(char c);

S. V. Patel College Page | 10

By: Dr. Piyush Arora Data Structures using C
void main()
{
char infix[100], post[100], item, x;
int i=0, len=0, k=0;

printf("\n Enter infix expression : ");

gets(infix);
len=strlen(infix);

while(i < len)

{
loop_yn=1;
item=infix[i];
switch(symbol_type(item)) A*B+((C-D)^E) = 15
{ Stack: Output: AB*CD-E^+
case opernd: item = x=
post[k] = item;
k = k+1;
break;

case oper:
if(stempty == 1)
{
push(item);
}
else
{
do
{
x = pop();
if(precedence(x) >= precedence(item))
{
post[k] = x;
k = k+1;
loop_yn=0;
}
else
{
loop_yn=1;
}
}
while((stempty==0) && (loopyn==0));

if(loopyn == 1)
{
push(x);
push(item);
}
else
{
push(item);
}
}
break;

case leftbrack:
S. V. Patel College Page | 11
By: Dr. Piyush Arora Data Structures using C
push(item);
break;

case rightbrack:
x=pop();
while(x != '(')
{
post[k] = x;
k = k+1;
x=pop();
}
break;
} // ---switch case complete---
++i;
}

while(top != -1)
{
post[k] = pop();
k = k+1;
}

printf("\n\n Postfix Expression is : ");

for(i=0 ; i<=k-1 ; i++)
{
printf("%c", post[i]);
}
}

void push(char c)
{
if(top == 100-1)
{
printf("\n Stack is Full");
stfull = 1;
return;
}
else
{
top=top+1;
stack[top] = c;
stempty = 0;
}
}

char pop()
{
char x;
if(top == -1)
{
stempty = 1;
x = ' '; // Used when -1 location is popped.
}
else
{
x = stack[top];
S. V. Patel College Page | 12
By: Dr. Piyush Arora Data Structures using C
top=top-1;
}
return(x);
}

enum item_list symbol_type(char c) ‘A’

{
enum item_list symbol;
if(isalpha(c))
{
symbol = opernd;
}
else if(c == '(')
{
symbol = leftbrack;
}
else if(c == ')')
{
symbol = rightbrack;
}
else
{
symbol = oper;
}
return symbol;
}

int precedence(char c) ^, *,/,+,-, (

{
int priority;
switch(c)
{
case '(':
priority = 0;
break;
case '+':
case '-':
priority = 1;
break;
case '*':
case '/':
priority = 2;
break;
case '^':
priority = 3;
break;
}
return priority;
}

S. V. Patel College Page | 13

By: Dr. Piyush Arora Data Structures using C
Conversion of Infix to Prefix / Polish Notation:
Algorithm to convert Infix expression to Prefix expression / Infix to Polish Notation
Input: “E” is an arithmetic expression in infix notation.
Output: An arithmetic expression in prefix notation. It is stack and elements are popped and displayed in
reverse order in the end.
“item” is the symbol scanned.
“x” is the symbol popped from stack.
ReverseOrderScan_ch( ): The method used to scan one item from right.
Data Structure: Two stacks are used. Since two stacks are used:
Push(s1, x) means adding “x” to stack s1.
Push(s1, item) means adding an “item” to stack s1.
Push(s2, x) means adding “x” to stack s2.
Push(s2, item) means adding an “item” to stack s2.
Pop(s1) means removing the top most element from the stack s1.
Pop(s2) means removing the top most element from the stack s2.
Write(x): The method used to write the variable “x” in final output expression.
Precedence( ): The method used to check the precedence of operators.

Step 1: [Initially add a left parenthesis “(” at the beginning of the infix expression E].
Step 2: [Push right parenthesis “)” on to the stack s1]
Push (s1, “)”)
Step 3: [Repeat steps 4 to 21 while stack s1 is not empty]
Step 4: [Scan the symbol from Infix Expression “E” in right to left manner]
Set item = E.ReverseOrderScan_ch( )
Step 5: If (item == operand)
Step 6: [Push “item” into the stack s2]
Push(s2, item)
[End of step 5 if structure]
Step 7: If (item == “)”)
Step 8: [Push “item” into the stack s1]
Push(s1, item)
[End of step 7 if structure]
Step 9: If (item == operator)
Step 10: x = Pop(s1)
Step 11: If precedence (x) > precedence (item)
Step 12: Repeat steps 13 and 14 while (precedence (x) > precedence (item))
Step 13: Push(s2, x)
Step 14: x = Pop(s1)
[End of step 12 loop]
[End of step 11 if structure]
Step 15: Push (s1, x)
Step 16: Push (s1, item)
[End of step 9 if structure]
Step 17: If (item == “(“)
Step 18: x = Pop(s1)
Step 19: Repeat steps 20 and 21 while x ≠ “)”
Step 20: Push(s2, x)
Step 21: x = Pop(s1)
[End of step 19 loop]
[End of step 17 if structure]
[End of step 3 loop]
Step 22: [Repeat steps 23 and 24 while stack s2 is not empty]
Step 23: x = Pop(s2)
Step 24: Write(x)
[End of step 22 loop]
Step 25: Exit
S. V. Patel College Page | 14
By: Dr. Piyush Arora Data Structures using C
Example 1: Given “E”: A+((B*(C-D)^E)+F)/G
Append a left parenthesis at the beginning of the expression, so it looks like:
(A+((B*(C-D)^E)+F)/G
Symbol Stack (S1) Stack (S2) / Expression
)
G ) G
/ )/ G
) )/) G
F )/) GF
+ )/)+ GF
) )/)+) GF
E )/)+) GFE
^ )/)+)^ GFE
) )/)+)^) GFE
D )/)+)^) GFED
- )/)+)^)- GFED
C )/)+)^)- GFEDC
( )/)+)^ GFEDC-
* )/)+)* GFEDC-^
B )/)+)* GFEDC-^B
( )/)+ GFEDC-^B*
( )/ GFEDC-^B*+
+ )+ GFEDC-^B*+/
A )+ GFEDC-^B*+/A
( GFEDC-^B*+/A+
Finally pop all the elements from the stack S2, until it is empty.
Answer: +A/+*B^-CDEFG

Example 2: Given “E”: A*(B+C)-(G+H)/L+P

Append a left parenthesis at the beginning: (A*(B+C)-(G+H)/L+P
Symbol Stack (S1) Stack (S2) / Expression
)
P ) P
+ )+ P
L )+ PL
/ )+/ PL
) )+/) PL
H )+/) PLH
+ )+/)+ PLH
G )+/)+ PLHG
( )+/ PLHG+
- )+- PLHG+/
) )+-) PLHG+/
C )+-) PLHG+/C
+ )+-)+ PLHG+/C
B )+-)+ PLHG+/CB
( )+- PLHG+/CB+
* )+-* PLHG+/CB+
A )+-* PLHG+/CB+A
( PLHG+/CB+A*-+
Finally pop all the elements from the stack S2, until it is empty.
Answer: +-*A+BC/+GHLP

S. V. Patel College Page | 15

By: Dr. Piyush Arora Data Structures using C
Example 3: Given “E”: A^B*C-D+E/F/(G+H)
Append a left parenthesis at the beginning: (A^B*C-D+E/F/(G+H)
Symbol Stack (S1) Stack (S2) / Expression
)
) ))
H )) H
+ ))+ H
G ))+ HG
( ) HG+
/ )/ HG+
F )/ HG+F
/ )// HG+F
E )// HG+FE
+ )+ HG+FE//
D )+ HG+FE//D
- )+- HG+FE//D
C )+- HG+FE//DC
* )+-* HG+FE//DC
B )+-* HG+FE//DCB
^ )+-*^ HG+FE//DCB
A )+-*^ HG+FE//DCBA
( HG+FE//DCBA^*-+
Finally pop all the elements from the stack S2, until it is empty.
Answer: +-*^ABCD//EF+GH

Example 4: Given “E”: (A+B)*C*((C-D^E/F)+G)+H-I

Append a left parenthesis at the beginning: ((A+B)*C*((C-D^E/F)+G)+H-I
Symbol Stack (S1) Stack (S2) / Expression
)
I ) I
- )- I
H )- IH
+ )-+ IH
) )-+) IH
G )-+) IHG
+ )-+)+ IHG
) )-+)+) IHG
F )-+)+) IHGF
/ )-+)+)/ IHGF
E )-+)+)/ IHGFE
^ )-+)+)/^ IHGFE
D )-+)+)/^ IHGFED
- )-+)+)- IHGFED^/
C )-+)+)- IHGFED^/C
( )-+)+ IHGED^/C-
( )-+ IHGFED^/C-+
* )-+* IHGFED^/C-+
C )-+* IHGFED^/C-+C
* )-+** IHGFED^/C-+C
) )-+**) IHGFED^/C-+C
B )-+**) IHGFED^/C-+CB
+ )-+**)+ IHGFED^/C-+CB
A )-+**)+ IHGFED^/C-+CBA
( )-+** IHGFED^/C-+CBA+
( IHGFED^/C-+CBA+**+-

S. V. Patel College Page | 16

By: Dr. Piyush Arora Data Structures using C
Finally pop all the elements from the stack S2, until it is empty.
Answer: -+**+ABC+-C/^DEFGHI

Example 5: Given “E”: (A^B*(((C+D)+(E-F))+G)/(H+W)

Append a left parenthesis at the beginning: ((A^B*(((C+D)+(E-F))+G)/(H+W)
Symbol Stack (S1) Stack (S2) / Expression
)
) ))
W )) W
+ ))+ W
H ))+ WH
( ) WH+
/ )/ WH+
) )/) WH+
G )/) WH+G
+ )/)+ WH+G
) )/)+) WH+G
) )/)+)) WH+G
F )/)+)) WH+GF
- )/)+))- WH+GF
E )/)+))- WH+GFE
( )/))+ WH+GFE-
+ )/)+)+ WH+GFE-
) )/)+)+) WH+GFE-
D )/)+)+) WH+GFE-D
+ )/)+)+)+ WH+GFE-D
C )/)+)+)+ WH+GFE-DC
( )/)+)+ WH+GFE-DC+
( )/)+ WH+GFE-DC++
( )/ WH+GFE-DC+++
* )* WH+GFE-DC+++/
B )* WH+GFE-DC+++/B
^ )*^ WH+GFE-DC+++/B
A )*^ WH+GFE-DC+++/BA
( WH+GFE-DC+++/BA^*
Finally pop all the elements from the stack S2, until it is empty.
Answer: *^AB/+++CD-EFG+HW

Program to convert Infix expression to Prefix expression / Infix to Polish Notation

#include<stdio.h>
#include<string.h>
#include<ctype.h>

enum item_list{opernd, oper, leftbrack, rightbrack};

enum item_list symbol_type(char c); // Function - name is symbol_type

int top=-1, stempty=1, stfull=0, loop_yn =1;

char stack[100];

void push(char c);

char pop();
int precedence(char c);

S. V. Patel College Page | 17

By: Dr. Piyush Arora Data Structures using C
void main()
{
char infix[100], pre[100], item, x;
int i=0, len=0, end=0, k=0;

printf("\n Enter infix expression : ");

gets(infix);
len=strlen(infix); len = 7
end = len-1; end = 6

while(end >= i)
{
loop_yn =1;
item=infix[end];
switch(symbol_type(item))
{
case opernd:
pre[k] = item;
k = k+1;
break;
case oper:
if(stempty)
{
push(item);
}
else
{
do
{
x = pop();
if(precedence(x) > precedence(item))
{
pre[k] = x;
k = k+1;
loop_yn =0;
}
else
{
loop_yn =1;
}
}
while((stempty == 0) && (loop_yn == 0));

if(loop_yn )
{
push(x);
push(item);
}
else
{
push(item);
}
}
break;

S. V. Patel College Page | 18

By: Dr. Piyush Arora Data Structures using C
case rightbrack:
push(item);
break;

case leftbrack:
x=pop();
while(x != ')')
{
pre[k] = x;
k = k+1;
x=pop();
}
break;
} // ---switch case complete---
--end;
}

while(top != -1)
{
pre[k] = pop();
k = k+1;
}

printf("\n\n Prefix Expression is : ");

for(i=k ; i>=0 ; i--)
{
printf("%c", pre[i]);
}
}

void push(char c)
{
if(top == 100)
{
printf("\n Stack is Full");
stfull = 1;
return;
}
else
{
++top;
stack[top] = c;
stempty = 0;
}
}

char pop()
{
char item;
if(top == -1)
{
stempty = 1;
item = ' '; // used when -1 location is popped
}
else
{
S. V. Patel College Page | 19
By: Dr. Piyush Arora Data Structures using C
item = stack[top];
--top;
}
return(item);
}

enum item_list symbol_type(char c)

{
enum item_list symbol;
if(isalpha(c))
{
symbol = opernd;
}
else if(c == '(')
{
symbol = leftbrack;
}
else if(c == ')')
{
symbol = rightbrack;
}
else
{
symbol = oper;
}
return symbol;
}

int precedence(char c)
{
int priority;
switch(c)
{
case ')':
priority = 0;
break;
case '+':
case '-':
priority = 1;
break;
case '*':
case '/':
priority = 2;
break;
case '^':
priority = 3;
break;
}
return priority;
}

S. V. Patel College Page | 20

By: Dr. Piyush Arora Data Structures using C
Evaluation of Postfix
• If postfix expression is given, scan from left to right.
• Scan one by one each character from postfix expression.
• If it is operand, push into the stack.
• If it is an operator, pop two values from the stack, perform arithmetic on them and again push the
result back into the stack.
Note: Here, the value popped first, becomes the second operand and the value popped second,
becomes the first operand.

Algorithm for evaluation of Postfix expression / Reverse Polish Notation

Input: “P” is an arithmetic expression in postfix notation.
Output: value of the expression.
“item” is the symbol scanned from postfix expression in left to right order.
Scan_ch( ): The method used to scan one item from left.
Data Structure: stack
Push(item) means adding an “item” to stack.
Pop( ) means removing the top most element from the stack.

Step 1: [Initially add a right parenthesis “)” at the end of the postfix expression P].
Step 2: [Repeat steps 3 to 11 while item ≠ “)”]
Step 3: [Scan the symbol from “P” in left to right manner]
Set item = P.Scan_ch( )
Step 4: If (item == operand)
Step 5: [Operand is pushed into the stack]
Push(item)
[End of step 4 if structure]
Step 6: If (item == operator)
Step 7: [a is the second operand of the current operator]
Set a = Pop( ) a = -2
Step 8: [b is the first operand of the current operator]
Set b = Pop( ) b=2
Step 9: Set op = item op = *
Step 10: Set result = b op a
Step 11: push(result)
[End of step 6 if structure]
[End of step 2 loop]
Step 13: Set result = Pop( )
Step 14: Write result
Step 15: Exit

Examples of Postfix Expressions:

1. A B C + * D E / - where A=3 B=16 C=2 D=12 E=6
2. A B C D E – F ^ / * + G + H - where A=8 B=7 C=6 D=5 E=4 F=3 G=2 H=1
Examples of Prefix Expressions:
1. – * A + B C / D E where A=3 B=16 C=2 D=12 E=6
2. + – * A + B C / + G H L P where A=4 B=3 C=2 G=6 H=4 L=2 P=1

Program for evaluation of Postfix expression / Reverse Polish Notation

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
#include<math.h>

int tos = -1, stack[100];

enum item_list{oper, opernd};
S. V. Patel College Page | 21
By: Dr. Piyush Arora Data Structures using C
enum item_list symbol_type(char c);

void push(int item);

int pop();

void main()
{
char post[100], item;
int i, len, val, val1, val2, val3;
//clrscr();
printf("Enter postfix notation : ");
gets(post);
len = strlen(post); len = 9
i=0;
while(i < len)
{
item = post[i];
switch(symbol_type(item))
{
case opernd:
printf("\n Enter the value of %c : ", item);
scanf("%d", &val);
push(val);
break;
case oper:
switch(item)
{
case '+':
val1 = pop();
val2 = pop();
val3 = val2 + val1;
push(val3);
break;
case '-':
val1 = pop();
val2 = pop();
val3 = val2 - val1;
push(val3);
break;
case '*':
val1 = pop();
val2 = pop();
val3 = val2 * val1;
push(val3);
break;
case '/':
val1 = pop();
val2 = pop();
val3 = val2 / val1;
push(val3);
break;
case '^':
val1 = pop();
val2 = pop();
val3 = pow(val2,val1);
push(val3);
S. V. Patel College Page | 22
By: Dr. Piyush Arora Data Structures using C
break;
}
break;
}
++i;
}
printf("\n Value of expression is : %d", pop());
}

void push(int item)

{
if(tos == 100-1)
{
printf("\n Stack is Full");
return 0;
}
else
{
++tos;
stack[tos] = item;
}
}

int pop()
{
int p;
if(tos == -1)
{
printf("\n Stack is empty");
return 0;
}
else
{
p = stack[tos];
--tos;
return p;
}
}

enum item_list symbol_type(char c)

{
enum item_list symbol;
if(isalpha(c))
{
symbol = opernd;
}
else
{
symbol = oper;
}
return symbol;
}

S. V. Patel College Page | 23

By: Dr. Piyush Arora Data Structures using C
Evaluation of Prefix
• If prefix expression is given, scan from right to left.
• Scan one by one each character from prefix expression.
• If it is operand, push into the stack.
• If it is an operator, pop two values from the stack, perform arithmetic on them and again push the
result back into the stack.
Note: Here, the value popped first, becomes the first operand and the value popped second, becomes
the second operand.

Algorithm for evaluation of Prefix expression / Polish Notation

Input: “P” is an arithmetic expression in prefix notation.
Output: value of the expression.
“item” is the symbol scanned from prefix expression in right to left order.
ReverseOrderScan_ch( ): The method used to scan one item from right.
Data Structure: stack
Push(item) means adding an “item” to stack.
Pop( ) means removing the top most element from the stack.
Step 1: [Initially add a left parenthesis “(” at the beginning of the prefix expression P].
Step 2: [Scan the symbol from P in right to left manner]
Set item = P.ReverseOrderScan_ch( )
Step 3: [Repeat steps 4 to 12 while item ≠ “(“]
Step 4: If (item == operand)
Step 5: [Operand is pushed into the stack]
Push(item)
[End of step 4 if structure]
Step 6: If (item == operator)
Step 7: [a is the first operand of the current operator]
Set a = Pop( )
Step 8: [b is the second operand of the current operator]
Set b = Pop( )
Step 9: Set op = item
Step 10: Set result = a op b
Step 11: push(result)
[End of step 6 if structure]
Step 12: Set item = P.ReverseOrderScan_ch( )
[End of Step 3 loop]
Step 13: Set result = Pop( )
Step 14: Write result
Step 15: Exit

Program for evaluation of Prefix expression / Polish Notation

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
#include<math.h>

int tos = -1, stack[100];

enum item_list{oper, opernd};

enum item_list symbol_type(char c);

void push(int item);

int pop();

S. V. Patel College Page | 24

By: Dr. Piyush Arora Data Structures using C
void main()
{
char pre[100], item;
int len=0, end=0, val, val1, val2, val3;
clrscr();
printf("Enter prefix notation : ");
gets(pre);
len = strlen(pre);
end = len-1;
while(end >= 0)
{
item = pre[end];
switch(symbol_type(item))
{
case opernd:
printf("\n Enter the value of %c : ", item);
scanf("%d", &val);
push(val);
break;
case oper:
switch(item)
{
case '+':
val1 = pop();
val2 = pop();
val3 = val1 + val2;
push(val3);
break;
case '-':
val1 = pop();
val2 = pop();
val3 = val1 - val2;
push(val3);
break;
case '*':
val1 = pop();
val2 = pop();
val3 = val1 * val2;
push(val3);
break;
case '/':
val1 = pop();
val2 = pop();
val3 = val1 / val2;
push(val3);
break;
case '^':
val1 = pop();
val2 = pop();
val3 = pow(val1,val2);
push(val3);
break;
}
break;
}
--end;
S. V. Patel College Page | 25
By: Dr. Piyush Arora Data Structures using C
}
printf("\n Value of expression is : %d", pop());
}

void push(int item)

{
if(tos == 100-1)
{
printf("\n Stack is Full");
return 0;
}
else
{
++tos;
stack[tos] = item;
}
}

int pop()
{
int p;
if(tos == -1)
{
printf("\n Stack is empty");
return 0;
}
else
{
p = stack[tos];
--tos;
return p;
}
}

enum item_list symbol_type(char c)

{
enum item_list symbol;
if(isalpha(c))
{
symbol = opernd;
}
else
{
symbol = oper;
}
return symbol;
}

S. V. Patel College Page | 26

By: Dr. Piyush Arora Data Structures using C
Recursion (An application of stack)
• A procedure that calls itself is called as a recursive procedure.
• OR
• A procedure that invokes (calls) a series of other functions and finally invokes the first function again
is called as recursive function. The process of doing this is called as recursion.
• So, when a function is dependent on another function, then recursion can be used.
• Consider four functions namely f1( ), f2( ), f3( ) and f4( ) called by the main( ) function as shown
below:

Calls Calls Calls

main( ) f1( ) f2( ) f3( )

Returns Returns Returns

Calls
f4( )

• When this function call occurs, they can be represented using stack, because the function calls are
maintained in LIFO order.
f3( )
f2( ) f2( ) f2( )
f1( ) f1( ) f1( ) f1( ) f1( ) f4( )
main( ) main( ) main( ) main( ) main( ) main( ) main( ) main( ) main( )

• To find the solution of a large problem, we can divide it into one or more sub-problems of a similar
nature, but smaller in size.
• We continue to find the solution of these sub-problems by dividing them again and again into smaller
sub-problems, until it reaches the simplest case.
• So, every recursive procedure can be divided into two parts:
o Base case: This is the smallest sub-problem obtained, which can be processed without
recursion. So, it tells us directly, what the answer is. There may be one or more than one base
cases.
o Recursive case: In this, we divide a particular problem into one or more sub-problems by
making progress towards the base case. There may be one or more than one recursive cases.
• Types of recursion:
a. Preemptive recursion: In this type of recursion, the function calls itself again and again.
e.g.: factorial, Hemachandra numbers or Fibonacci series, binary search, tower of Hanoi.
b. Non-preemptive recursion: In this type of recursion, the function becomes an argument in a call
of the function. e.g.: Ackerman’s function
• Note: Recursion cannot be used when we pass large amounts of data in the function. The execution
speed will decrease.

Examples of Recursive procedures:

1. Factorial Function
• To find the factorial of an integer “n”, we can write as below:
n!=n * (n-1) * (n-2) *……. * 3 * 2 * 1
• It is written as:
n! = 1 if n = 0

n*(n-1) if n > 0
• This can be represented as below, for n = 5:
5! = 5*(5-1)!
= 5*(4*4-1)!
= 5*(4*(3*3-1)!)
= 5*(4*(3*(2*2-1)!))
S. V. Patel College Page | 27
By: Dr. Piyush Arora Data Structures using C
= 5*(4*(3*(2*(1*1-1)!)))
= 5*(4*(3*(2*(1*(0!))))
= 5*(4*(3*(2*(1*1))))
= 5*(4*(3*(2*1)))
= 5*(4*(3*2))
= 5*(4*6)
= 5*24
= 120
Program to calculate factorial of a given number
#include<stdio.h>
#include<conio.h>
int fact(int n)
{
if(n == 0)
{
return 1;
}
else
{
return n * fact(n-1);
}
}
void main()
{
int n, f;
printf("Enter number to calculate factorial : ");
scanf("%d", &n); n = 5
f=fact(n);
printf("Factorial of %d is %d \n", n, f);
}

2. Hemachandra Numbers (Fibonacci Series)

• Fibonacci series starts from 0 and 1.
• Successive elements are obtained by adding the preceding two elements in the series.
• That is:
0 1 1 2 3 5 8 13 21......
0+1 1+1 1+2 2+3 3+5 5+8 8+13

S. V. Patel College Page | 28

By: Dr. Piyush Arora Data Structures using C

Program to print Fibonacci series for “n” terms

#include<stdio.h>
#include<conio.h>

int fibo(int i)
{
if(i <= 0)
{
return 0;
}
else if(i == 1)
{
return 1;
}
else
{
return fibo(i-1) + fibo(i-2);
}
}
void main()
{
int n, i;
printf("Enter the no. of elements to be printed : ");
scanf("%d", &n);
for(i=0 ; i<n ; i++)
{
printf("%5d", fibo(i));
}
}

3. Binary Search
Program to search the element using binary search.
#include<stdio.h>
#include<conio.h>

int bin_search_recurs(int a[], int low, int high, int key)

{
int mid;
mid = (low+high)/2;

if(key == a[mid])
{
return mid;
}

S. V. Patel College Page | 29

By: Dr. Piyush Arora Data Structures using C
if(key > a[mid])
{
if(key > a[high])
{
printf("\n Element not in the list...");
return 0;
}
if (key == a[high])
{
return high;
}
mid = bin_search_recurs(a, mid, high, key);
}
else
{
if (key == a[low])
{
return low;
}
mid = bin_search_recurs(a, low, mid, key);
}
return mid;
}

int main()
{
int a[30], n, i, ele, flag;
printf("\n Enter no. of elements : ");
scanf("%d", &n);

printf("\n Input elements in Ascending order : \n");

for(i=0 ; i<n ; i++)
{
scanf("%d", &a[i]);
}

printf("\n Enter element to search Recursively : ");

scanf("%d", &ele);

flag = bin_search_recurs(a, 0, n-1, ele);

if(flag == -1)
{
printf("\n Element not found \n");
}
else
{
printf("\n Element found at location %d \n",flag);
}
return 0;
}

S. V. Patel College Page | 30

By: Dr. Piyush Arora Data Structures using C
4. Tower of Hanoi / Disk on a Peg
• Suppose three towers labelled 1, 2 and 3 are given and “n” number of disks with decreasing size, are
placed on tower 1.
• The aim of the game is to move all the disks from tower 1 to tower 3 using a temporary tower 2.
• The rules of the game are as follows:
1. At any point of time, only one disk can be moved from one tower (peg) to another.
2. Only a top most disk can be moved to any other tower (peg).
3. Larger disk cannot be placed on a smaller disk at any point of time.

• Complexity of Tower of Hanoi:

o Here, the size of the problem is the number of disks and the operation of interest is moving
one disk.
o Except for the base case, each recursive call results in calling itself twice more.
o To solve a problem of N disks, we make 2N-1 disk moves.
o Therefore the algorithm is O(2n), which is called exponential complexity.
• The figure shows this representation using three towers. So, n=3.

Program to print steps to implement tower of Hanoi.

#include<stdio.h>
#include<conio.h>
void move(int disk, int start, int end, int temp)
{
if(disk > 0)
{
move(disk-1,start, temp, end);
printf("Move Disk %d From Tower %d to Tower %d\n", disk, start, end);
move(disk-1,temp, end, start);
}
}
void main()
{
int disk;
printf("Enter the number of disks you want to play with : ");
scanf("%d",&disk);
move(disk, 1, 3, 2);
}

The program given above can be traced as below:

Here “S” indicates “start”, “E” indicates “end”, “T” indicates “temp”.
The bold boxes represent the recursive calls to the same method.
The dashed box represents the steps displayed in result of function calls.

S. V. Patel College Page | 31

 By: Dr. Piyush Arora Data Structures using C
Finally, the steps are printed by “Inorder traversal”, as the printf statement appears in the middle of the
function call.
move(3, 1, 3, 2)
S E T

move(2, 1, 2, 3) 3 1 3 move(2, 2, 3, 1)
S T E T E S
S E T S E T

move(1, 1, 3, 2) 2 1 2 move(1, 3, 2, 1) move(1, 2, 1, 3) 2 2 3 move(1, 1, 3, 2)

S T E T E S S T E T E S
S E T S E T S E T S E T

move(0, 1,2,3) 1 1 3 move(0, 2,3,1) move(0, 3,1,2) 1 3 2 move(0, 1,2,3) move(0, 2,3,1) 1 2 1 move(0, 3,1,2) move(0, 1,2,3) 1 1 3 move(0, 2,3,1)
STE TES STE TES STE TES STE TES
SET SET SET SET SET SET SET SET

S. V. Patel College Page | 32

By: Dr. Piyush Arora Data Structures using C
Queue OR Simple Queue OR Ordinary Queue
• Queue is non-primitive, linear, dynamic and homogeneous data structure.
• A queue is a linear list of elements in which insertions can take place only at one end called as rear
and deletions can take place only at the other end called as front.
e.g.: A queue of people waiting at a bus stop, where each new person comes at the rear (end) of the
queue and when the bus comes, people at the front (start) board (get into) the bus first.
• So, queue is also called as First in First out (FIFO) list or First Come First Served (FCFS) list,
because the first element to be added in the queue will be the first element to be removed from the
queue.
• In queue, initially, front is initialized to -1 and rear is initialized to -1.
• front will always be pointing to the first element.
• If front=rear, the queue contains only one element, (except for the condition front = rear = -1).

We can make the following assumptions for a simple queue.

• For insertion, we have to write:
rear = rear + 1;
• For deletion, we have to write:
front = front + 1;
• Underflow condition for simple queue:
If (front == -1)
• Overflow condition for simple queue:
If (rear == SIZE – 1)

Operations on Simple Queue

insert(Q, value): To insert an element “value” in queue ‘Q’ using rear pointer.
delete(Q): To delete an element from queue ‘Q’ using front pointer.
display(): To display the total number of elements in the queue.
0 1 2 3 4
Front = -1 Initially Set Front = Rear = – 1
Rear = -1
0 1 2 3 4
5 10 15 Insertion (Increment Rear)
Front = 0 Rear = 2

0 1 2 3 4
5 10 15 20 25 No more insertion possible
Front = 0 Rear = 4 (Rear == SIZE – 1)

0 1 2 3 4
15 20 25 Deletion (Increment Front)
Front = 2 Rear = 4

0 1 2 3 4
25 (Front == Rear)
Front = 4 So, delete element and set
Rear = 4 Front = Rear = – 1

0 1 2 3 4
Front = -1 Set Front = Rear = – 1
Rear = -1

Algorithms for operations on Simple Queue:

1. Algorithm to insert an element in Simple Queue
“Q” indicates the simple queue for insertion operation.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
“SIZE” is the total number of elements in the simple queue.
“value” is the value inserted in the queue.
S. V. Patel College Page | 33
By: Dr. Piyush Arora Data Structures using C
Step 1: [Check for queue overflow]
If (rear == SIZE – 1)
Output “Queue is Overflow” and Exit
Step 2: [Set the front pointer only for the first time]
If (front == – 1)
front = 0
Step 3: [Input value from the user]
Step 4: [Increment rear pointer by 1]
rear = rear + 1
Step 5: [Insert an element at rear location]
Q[rear] = value
Step 6: Exit

2. Algorithm to delete an element from Simple Queue

“Q” indicates the simple queue for deletion operation.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
“SIZE” is the total number of elements in the simple queue.
“value” is the value deleted from the queue.
Step 1: [Check for queue underflow]
If (front == – 1)
Output “Queue is Underflow” and Exit
Step 2: [Initialize a variable “value” for deletion]
Step 3: [Remove element from front location]
value = Q[front]
Step 4: [Check for empty queue and check whether front and rear are same?]
If (front == rear)
front = – 1
rear = – 1
Else
front = front + 1
Step 5: return value
Step 6: Exit

3. Algorithm to display elements of Simple Queue

“Q” indicates the simple queue for display operation.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
Step 1: [Check for queue underflow]
If (front == – 1)
Output “Queue is Underflow” and Exit
Step 2: [Initialize a counter “i” with front for display operation]
i = front
Step 3: [Check whether counter “i” is less than or equal to rear]
If (i <= rear)
Display element Q[i]
Increment “i” by 1.
Repeat step 3.
Step 4: Exit

Program for operations on simple queue:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 5
int queue[MAX];
int front = - 1;
S. V. Patel College Page | 34
By: Dr. Piyush Arora Data Structures using C
int rear = - 1;
void main()
{
int ch;
while (1)
{
printf("\n 1. Insert in Queue");
printf("\n 2. Delete from Queue");
printf("\n 3. Display elements");
printf("\n 4. Quit");
printf("\n\n Enter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}
}
}

insert()
{
int ele;
if (rear == MAX - 1)
{
printf("\n Queue Overflow \n");
}
else
{
if (front == - 1) // First time only
{
front = 0;
}
printf("Input element for adding in queue : ");
scanf("%d", &ele);
rear = rear + 1;
queue[rear] = ele;
display();
}
}

del()
{
int ele;
if (front == - 1)
{
printf("\n Queue is Underflow \n");
return ;
}
else
S. V. Patel College Page | 35
By: Dr. Piyush Arora Data Structures using C
{
ele = queue[front];
if(front == rear)
{
front = -1;
rear = -1;
}
else
{
front = front + 1;
}
printf("Element deleted from queue : %d \n",ele);
display();
}
}

display()
{
int i;
if (front == - 1)
{
printf("Queue is empty\n");
}
else
{
printf("\n elements of Queue are :\n");
for (i = front; i <= rear; i++)
{
printf("%d ", queue[i]);
}
}
}

Limitations of Simple Queue

• We can see that, though there is enough space in the queue, as front and rear have moved at the end,
we cannot insert any element further.
• It means, the program will give you the message “Queue is full”, though the queue is empty.
• This problem is called as “internal fragmentation”.
• It means that, the element cannot be inserted until the front pointer does not reach till rear pointer and
are initialized to -1.
0 1 2 3 4
Front = -1 Initially Front = Rear = – 1
Rear = -1
0 1 2 3 4
5 10 15 20 25 No more insertion possible
Front = 0 Rear = 4 (Rear == SIZE – 1)

0 1 2 3 4 Rear cannot be incremented further.

20 25 We have space in beginning of Queue
Front = 3 Rear = 4 at 0, 1 and 2, but we cannot insert.

0 1 2 3 4
× 20 25
Insertion Front = 3 Rear = 4
Not
Possible
• We have one solution for this:

S. V. Patel College Page | 36

By: Dr. Piyush Arora Data Structures using C
o We can shift the elements of the queue one by one towards left position and then make space
for a new element. This is easy to implement, if the size of the queue is small.
o In real life, if any element is removed from the queue, the elements shift one position to the
left, so that they can be serviced.
o But, if the size of the queue is large (e.g.: 5000) elements, then it becomes difficult to shift the
elements.
Note: These limitations occur only if you implement queue using array. These limitations do not occur, if
you implement queue using linked list as the nodes can be added and removed as and when required.

S. V. Patel College Page | 37

By: Dr. Piyush Arora Data Structures using C
Circular Queue
• To remove the problems, that occur when we use a simple queue, we need to use circular queue.
• Circular queue is like a circular buffer space.
• Physically, the circular queue is same as ordinary queue, say a[n], but logically we can say that, a[0]
comes after a[n-1].
• Here also, front keeps track of the elements to be deleted, and rear keeps track of the elements to be
inserted. 4 0
• We can represent the circular queue in two ways: 25 5
0 1 2 3 4
5 10 15 20 25
3 20 10 1

15
2
Physical Representation of Circular Queue Logical Representation of Circular Queue

We have to make the following assumptions for a circular queue:

• For insertion, we have to write:
rear = (rear + 1) % SIZE;
• For deletion, we have to write:
front = (front + 1) % SIZE;
• Underflow condition for circular queue:
If (front == -1)
• Overflow condition for circular queue:
If (front == (rear+1) % SIZE)

Insertion and Deletion in Circular Queue

Initially
Front = -1 Front = 0 4 0
4 0 Rear = -1 4 0
5

3 20 1
3 1 3 20 10 1
Rear = 3
Rear = 3 15
15
2
2 2
Front = 2
While inserting first element, set While Deleting an element
Queue is empty Front = 0. Increment
Increment Front = (Front + 1) % SIZE
Rear = (Rear + 1) % SIZE

0
Rear = 0 Front = 4 Rear = 0 Front = 4 0
4 4 0 4
25 30 25 30 25 30

3 20 1 3 35 1
3 1

15 40
2 2 2
Front = 2 Rear = 2
Again, Insertion is possible at 0 Again , deletion is possible Again, Insertion is possible
Increment Increment Increment
Rear = (Rear + 1) % SIZE Front = (Front + 1) % SIZE Rear = (Rear + 1) % SIZE

S. V. Patel College Page | 38

By: Dr. Piyush Arora Data Structures using C
Operations on Circular Queue
insert(Q, value): To insert an element “value” in circular queue ‘Q’ using rear pointer.
delete(Q): To delete an element from circular queue ‘Q’ using front pointer.
display(): To display the total number of elements in the circular queue.

Algorithms for operations on Circular Queue

1. Algorithm to insert an element in Circular Queue
“Q” indicates circular queue for insertion.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
“SIZE” is the total number of elements in the circular queue.
“value” is the value inserted in the circular queue.
Step 1: [Check for queue overflow]
If (front == (rear + 1) % SIZE)
Output “Queue is Overflow” and Exit
Step 2: [Input “value” from the user]
Step 3: [For the first time, check for “front” pointer and set it]
If (front == – 1)
front = 0
rear = 0
Step 4: [Otherwise, increment rear pointer location]
Else
rear = (rear + 1) % SIZE
Step 5: [Insert the element at rear location]
Q[rear] = value
Step 6: Exit

2. Algorithm to delete an element from Circular Queue

“Q” indicates circular queue for insertion.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
“SIZE” is the total number of elements in the circular queue.
“value” is the value deleted from circular queue.
Step 1: [Check for queue underflow]
If (front == – 1)
Output “Queue is Underflow” and Exit
Step 2: [Initialize the variable “value” for deletion]
Step 3: [Remove the element from Queue]
value = Q[front]
Step 4: [Check whether front and rear are equal]
If (front == rear)
front = – 1
rear = – 1
Step 5: [Otherwise, increment the front pointer by one
location]
Else
front = (front + 1) % SIZE
Step 6: Return (value)
Step 7: Exit

3. Algorithm to display elements of Circular Queue

“Q” indicates the circular queue for display operation.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
“SIZE” is the total number of elements in the circular queue.
Step 1: [Check for queue underflow]
S. V. Patel College Page | 39
By: Dr. Piyush Arora Data Structures using C
If (front == – 1)
Output “Queue is Underflow” and Exit
Step 2: [Initialize a counter “i” with front for display operation]
i = front
Step 3: [Check whether front is less than rear]
If (front <= rear)
Goto Step 4
Else
Goto Step 6
Step 4: [Check whether counter “i” is less than or equal to rear]
If (i <= rear)
Display element Q[i]
Increment “i” by 1.
Repeat step 4.
Step 5: Goto step 9.
Step 6: [Check whether counter “i” is less than or equal to SIZE – 1 to display initial elements]
If (i <= SIZE–1)
Display element Q[i]
Increment “i” by 1.
Repeat step 6.
Step 7: [Initialize a counter “i” with 0 to display remaining elements]
i=0
Step 8: [Check whether counter “i” is less than or equal to rear]
If (i <= rear)
Display element Q[i]
Increment “i” by 1.
Repeat step 8.
Step 9: Exit
Program for operations on simple queue:
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
#define MAX 5
int q[MAX], front=-1, rear=-1;
void insert(int value);
void deletion();
void display();
void main()
{
int ch, value;
do
{
printf("\n 1. Insert in circular queue");
printf("\n 2. Delete from circular queue");
printf("\n 3. Display the elements");
printf("\n 4. To exit");
printf("\n\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n Enter value: ");
scanf("%d",&value);
insert(value);
break;
case 2:
deletion();
break;
S. V. Patel College Page | 40
By: Dr. Piyush Arora Data Structures using C
case 3:
display();
break;
case 4:
exit(0);
default:
printf("---wrong choice---");
break;
}
}
while(ch != 4);
}
int is_empty()
{
if (front == -1)
{
return 1;
}
else
{
return 0;
}
}
int is_full()
{
if(front == (rear+1)%MAX)
{
return 1;
}
else
{
return 0;
}
}
void insert(int value)
{
if(is_full() == 1)
{
printf("\n---Queue is Overflow---\n");
return;
}
if(front == -1)
{
front = 0;
rear = 0;
}
else
{
rear = (rear+1)%MAX;
}
q[rear]=value;
display();
}
void deletion()
{
int x;
if(is_empty())
{
printf("\n---Circular Queue is Underflow---\n");
return;
}
S. V. Patel College Page | 41
By: Dr. Piyush Arora Data Structures using C
x = q[front];
if(front == rear)
{
front = -1;
rear = -1;
}
else
{
front = (front+1)%MAX;
}
printf("\n Element deleted : %d \n",x);
display();
}
void display(void)
{
int i;
if(is_empty())
{
printf("\n Queue is empty..... \n");
return;
}
printf("\n Elements are : \n");
if(front <= rear)
{
for(i=front ; i<=rear ; i++)
{
printf("\t %d \n", q[i]);
}
}
else
{
for(i=front ; i<=MAX-1 ; i++)
{
printf("\t %d \n", q[i]);
}
for(i=0 ; i<=rear ; i++)
{
printf("\t %d \n", q[i]);
}
}
}

Limitations of Circular queue

• As can be seen from the figure, a circular queue has limited buffer space. So, a situation arises, where
we are not able to insert any element further into the circular queue.
• This occurs, when we implement circular queue using array.
• So, we can implement circular queue using linked list to remove this problem.

DEQUE (Double Ended Queue)

• A DEQUE is a linear list in which the elements can be added or removed at both the ends.
• DEQUE is often called as “Head–Tail Linked list”.
• Note: we cannot insert or delete the element in the middle.
• As insertion and deletion can be performed at both the ends, we need to design algorithms to perform
the following operations:
Insert at Front 0 1 2 3 4 Insert at Rear

Delete from Front Delete from Rear

S. V. Patel College Page | 42

By: Dr. Piyush Arora Data Structures using C
We Insert at right using rear
0 1 2 3 4
Front = -1 Initially Front == Rear == – 1
Rear = -1
0 1 2 3 4
5 10 15 Set Front = 0 for First time
Front = 0 Rear = 2 Increment Rear = Rear + 1 for every insertion

0 1 2 3 4 Now “Queue is Overflow” on Right side,

5 10 15 20 25 When Rear == SIZE – 1
Front = 0 Rear = 4 Similarly “Queue is Overflow” on Left Side,
When Front = 0
We Delete from right using rear
0 1 2 3 4
5 10 15 20 25 For every deletion from Rear, decrement Rear.
Front = 0 Rear = 4 Rear = Rear – 1

0 1 2 3 4
5 10 15 Rear = Rear – 1
Front = 0 Rear = 2

0 1 2 3 4 Finally, we get Front = Rear = 0

5 So, “Queue is Underflow” on Left Side
Front = 0 Now we set back Front = Rear = – 1 after
Rear = 0 deleting the First element

We Delete from left using front

0 1 2 3 4
5 10 15 20 25 For every deletion from Front, increment Front.
Front = 0 Rear = 4 Front = Front + 1

0 1 2 3 4
15 20 25 Front = Front + 1
Front = 2 Rear = 4

0 1 2 3 4 Finally, we get Front = Rear = SIZE – 1

25 So, “Queue is Underflow” on Right Side
Front = 4 Now we set back Front = Rear = – 1 after
Rear = 4 deleting the Last element
We Insert at left using front
0 1 2 3 4
25 Suppose we have one element at the Rear end.
Front = 4 We Insert the element at Left using Front
Rear = 4 For Insertion, Front = Front – 1

0 1 2 3 4
15 20 25 Front = Front – 1
Front = 2 Rear = 4
Now “Queue is Overflow” on Left side,
0 1 2 3 4 When Front == 0
5 10 15 20 25 Similarly “Queue is Overflow” on Right Side,
Front = 0 Rear = 4 When Rear == SIZE – 1

Operations on DEQUE
insert_front(Q, value): To insert an element “value” in deque ‘Q’ using front pointer (at Left).
insert_rear(Q, value): To insert an element “value” in deque ‘Q’ using rear pointer (at Right).
delete_front(Q): To delete an element from deque ‘Q’ using front pointer (from Left).
delete_rear(Q): To delete an element from deque ‘Q’ using rear pointer (from Right).

S. V. Patel College Page | 43

By: Dr. Piyush Arora Data Structures using C
Algorithms for operations on DEQUE
1. Algorithm to insert an element using rear (at right side) of DEQUE
“deque” indicates the DEQUE for insertion at right.
“rear” pointer indicates position for insertion at right.
“front” pointer indicates position for insertion and deletion from left.
“SIZE” is the total number of elements in DEQUE.
“value” is the value inserted at rear end in DEQUE.
Step 1: [Check for queue overflow]
If (rear == SIZE – 1)
Output “Deque is Overflow on Right” and Exit
Step 2: [Set the front pointer only for the first time]
If (front == – 1)
front = 0
Step 3: [Input value from the user]
Step 4: [Increment rear pointer for insertion at right]
rear = rear + 1
Step 5: [Insert an element at rear location]
deque[rear] = value
Step 6: Exit

2. Algorithm to delete an element using rear (from right side) of DEQUE

“deque” indicates the DEQUE for deletion from right.
“rear” pointer indicates position for deletion from right.
“front” pointer indicates position for insertion and deletion from left.
“SIZE” is the total number of elements in DEQUE.
“value” is the value deleted from rear end in DEQUE.
Step 1: [Check for queue underflow]
If (rear == – 1)
Output “Deque is Underflow on Right” and Exit
Step 2: [Initialize a variable “value” for deletion]
Step 3: [Delete an element from right end of DEQUE]
value = deque[rear]
Step 4: [Check whether front and rear are same (when rear reaches till front)]
If (front == rear)
front = – 1
rear = – 1
Step 5: [Otherwise, if step 4 is not correct, decrement rear pointer after deletion]
Else
rear = rear – 1
Step 6: Exit

3. Algorithm to delete an element using front (from left side) of DEQUE

“deque” indicates the DEQUE for deletion from left.
“rear” pointer indicates position for insertion and deletion at right.
“front” pointer indicates position for deletion.
“SIZE” is the total number of elements in DEQUE.
“value” is the value deleted from front end in DEQUE.
Step 1: [Check for queue underflow]
If (front == – 1)
Output “Deque is Underflow on Left” and Exit
Step 2: [Initialize a variable “value” for deletion]
Step 3: [Delete an element from left end of DEQUE]
value = deque[front]
Step 4: [Output the deleted element “value”]
Step 5: [Check whether front and rear are same (when front reaches till rear)]
If (front == rear)
S. V. Patel College Page | 44
By: Dr. Piyush Arora Data Structures using C
front = – 1
rear = – 1
Step 6: [Otherwise, if step 5 is not correct, increment front pointer after deletion]
Else
front = front + 1
Step 7: Exit

4. Algorithm to insert an element using front (at left side) of DEQUE

“deque” indicates the DEQUE for insertion at left.
“rear” pointer indicates position for insertion and deletion at right.
“front” pointer indicates position for insertion.
“SIZE” is the total number of elements in DEQUE.
“value” is the value inserted at front end in DEQUE.
Step 1: [Check for queue overflow]
If (front == 0)
Output “Deque is Overflow on Left” and Exit
Step 2: [Check rear pointer position initially, for insertion at left]
If (rear == – 1)
front = SIZE
rear = SIZE
Step 3: [Input value from the user]
Step 4: [Decrement front pointer for insertion at left]
front = front – 1
Step 5: [Insert an element at front location]
deque[front] = value
Step 6: [Set the rear pointer only for the first time]
If (rear == SIZE)
rear = SIZE – 1
Step 7: Exit

5. Algorithm to display elements of DEQUE

“deque” indicates the simple queue for display operation.
“rear” pointer indicates position for insertion.
“front” pointer indicates position for deletion.
Step 1: [Check for queue underflow]
If (front == – 1)
Output “Queue is Underflow” and Exit
Step 2: [Initialize a counter “i” with front for display operation]
i = front
Step 3: [Check whether counter “i” is less than or equal to rear]
If (i <= rear)
Display element deque[i]
Increment “i” by 1.
Repeat step 3.
Step 4: Exit

Types of DEQUE
• There are two types of deque.
a. Input restricted DEQUE – In this deque, we can insert only at one end, but we can delete from
both the ends of the list.
So, we have algorithms to perform insertion at one end and deletion from both the ends.
b. Output restricted DEQUE – In this deque, we can delete only from one end, but we can insert at
both the ends of the list.
So, we have algorithms to perform deletion from one end and insertion at both the ends.
Note: It is up to the programmer to decide, at which end he wants to perform insertion and
deletion.
S. V. Patel College Page | 45
By: Dr. Piyush Arora Data Structures using C

Insert at Front 0 1 2 3 4
5 10 15 20 25
Delete from Front
Input Restricted from Right Delete from Rear

OR
0 1 2 3 4 Insert at Rear

5 10 15 20 25
Delete from Front Delete from Rear
Input Restricted from Left
Figure: Input Restricted DEQUE
Insert at Front 0 1 2 3 4 Insert at Rear

5 10 15 20 25
Delete from Rear
Output Restricted from Left
OR
Insert at Front 0 1 2 3 4 Insert at Rear

5 10 15 20 25
Delete from Front
Output Restricted from Right

Figure: Output Restricted DEQUE

Algorithms for operations on Input Restricted DEQUE

Note: For Input Restricted DEQUE, write any one algorithm for Insertion and two algorithms for
Deletion
e.g.: Insert at right, Delete from left and Delete from right.
e.g.: Insert at left, Delete from left and Delete from right.

Algorithms for operations on Output Restricted DEQUE

Note: For Output Restricted DEQUE, write any one algorithm for Deletion and two algorithms for
Insertion
e.g.: Delete from left, Insert at left and Insert at right.
e.g.: Delete from right, Insert at left and Insert at right.

S. V. Patel College Page | 46