18CSC201J

DATA STRUCTURES AND

ALGORITHMS
UNIT 3

22/01/2023 1
Syllabus
• S1- Stack ADT, Stack - Array Implementation
• S2- Stack Linked List Implementation, Applications of Stack-Infix to Postfix
Conversion
• S3- Applications of Stack-Postfix Evaluation, Balancing symbols
• S6- Applications of Stack- Nested Function Calls, Recursion concept using
stack
• S7- Tower of Hanoi, Queue ADT
• S8- Queue implementation using array and Linked List
• S11- Circular Queue and implementation
• S12- Applications of Queue and double ended queue
• S13- Priority Queue and its applications

22/01/2023 2
SESSION 1

22/01/2023 3
STACK ADT
• Abstract Data Type (ADT)

– It is a mathematical model for data types

– An abstract data type is defined by its behavior (semantics) from the point
of view of a user, of the data, specifically in terms of possible values, possible
operations on data of this type, and the behavior of these operations. Set of
values and set of operations
• A stack is an ADT
– It follows Last In First Out (LIFO) methodology perform operations push,
pop, etc.
22/01/2023 4
What is STACK?

Diagram Reference : http://www.firmcodes.com/write-a-c-program-to-implement-a-stack-using-an-array-and-linked-list/

• Stack works on “Last in First out” or “First in Last Out”, principle.

• Plates placed one over another
• The plate at the top is removed first & the bottommost plate kept longest
period of time.
• So, it follows LIFO/FILO order.

22/01/2023 5
Stack Example

Diagram Reference:https://www.codesdope.com/course/data-structures-stacks/

• Always new items are added at top of the stack and also removed from the
top of the stack only.

• Entry and Exit at same point

22/01/2023 6
STACK – Data Structure
• Stack is a Linear Data Structure
• Follows a particular order to perform the operations.
• The order are either
LIFO(Last In First Out)
OR
FILO(First In Last Out).

22/01/2023 7
STACK - Operations
TWO PRIMARY OPERATIONS
• push
– Pushing (storing) an element on the stack
– If the stack is full, Overflow condition is enabled.
• Pop
– Removing (accessing) an element from the stack.
– The elements are popped in the decreasing order.
– If the stack is empty, Underflow condition enabled.

22/01/2023 8
STACK – Additional Functionality
• For effective utilization of the stack, Status of the stack should be checked.
For that additional functionality is of the stack is given below
• Peek or Top 
– Accessing the top element. Without removing the top element.
• isFull
– check if stack is full.
• isEmpty 
– check if stack is empty.

22/01/2023 9
Stack Operation Example

22/01/2023 10
Stack Implementation - Array

22/01/2023 11
Stack - Array
• One dimensional array is enough to implement the stack

• Array size always fixed

• Easy to implement
• Create fixed size one dimensional array
– insert or delete the elements into the array using LIFO principle using the
variable 'top‘

22/01/2023 12
Stack - top
• About top

– Initial value of the top is -1

– To insert a value into the stack, increment the top value by one and then
insert

– To delete a value from the stack, delete the top value and decrement the
top value by one

22/01/2023 13
Steps to create an empty stack
1. Declare the functions like push, pop, display etc. need to implement the
stack.

2. Declare one dimensional array with fixed size

3. Declare a integer variable 'top' and initialize it with '-1'. (int top = -1)

22/01/2023 14
push(Value)
Inserting value into the stack
• push() is a function used to insert a new element into stack at top position.
• Push function takes one integer value as parameter
1. Check whether stack is FULL based on (top == SIZE-1)

2. If stack is FULL, then display "Stack is FULL Nota able to Insert element”  and
terminate the function.

3. If stack is NOT FULL, then increment top value by one (top=top+1) and set

(stack[top] = value)

22/01/2023 15
void push()
int main()
{
#define SIZE 10 int n, x;
int stack[SIZE]; for(int i=0;i<n;i++)
Int top=-1; {
void push(int value) scanf(“%d”,&x);
{ push(x);
}
if(top == SIZE-1)
}
printf("\nStack is Full!!! Insertion is not possible!!!");
else
{
top++;
stack[top] = value;
printf("\nInsertion success!!!");
}
}

22/01/2023 16
pop() –
Delete a value from the Stack
• pop() is a function used to delete an element from the stack
from top position
• Pop function does not take any value as parameter
1. Check whether stack is EMPTY using (top == -1)

2. If stack is EMPTY, then display "Stack is EMPTY No elements to delete" and

terminate the function

3. If stack is NOT EMPTY, then delete stack[top] and decrement top value by one

(top=top-1)

22/01/2023 17
void pop()
int main()
{
void pop() int n, x;
{ for(int i=0;i<n;i++)
{
if(top == -1)
pop();
printf("\nStack is Empty!!! Deletion is not possible!!!"); }
else }
{
printf(“\n Deleted element: %d”,stack[top]);
top--;
}
}

22/01/2023 18
display()
Displays the elements of a Stack

• display() – function used to Display the elements of a Stack

1. Check whether stack is EMPTY based on (top == -1)

2. If stack is EMPTY, then display "Stack is EMPTY" and terminate the function

3. If stack is NOT EMPTY, display the value in decreasing order of array

22/01/2023 19
void display()
void display()
{
if(top == -1)
printf("\nStack is Empty!!!");
else
{
int i;
printf("\nStack elements are:\n");
for(i=top; i>=0; i--)
printf("%d\n",stack[top--]);
} Stack elements are:
40
} 30
20
22/01/2023 20
Stack Push Example

Diagram reference :http://www.exploredatabase.com/2018/01/stack-abstract-data-type-data-structure.html

22/01/2023 21
Stack Pop Example

22/01/2023 22
Another Example of Stack
Push & Pop

Image Reference : https://www.hackerearth.com/practice/notes/stacks-and-queues/

22/01/2023 23
Cons Stack - Array
• The size of the array should be mentioned at the beginning of the
implementation

• If more memory needed or less memory needed that time this array
implementation is not useful

22/01/2023 24
SESSION 2

22/01/2023 25
Stack Implementation – Linked List

22/01/2023 26
Pros Stack – Linked List
• A stack data structure can be implemented by using a linked list

• The stack implemented using linked list can work for the variable size of data.
So, there is no need to fix the size at the beginning of the implementation

22/01/2023 27
Stack – Linked list
• Dynamic Memory allocation of Linked list is followed
• The nodes are scattered and non-contiguously in the memory
• Each node contains a pointer to its immediate successor node
in the stack
• Stack is said to be overflown if the space left in the memory
heap is not enough to create a node

22/01/2023 28
Stack – Linked list
• In linked list implementation of a stack, every new element is inserted as 'top'
element.
• That means every newly inserted element is pointed by 'top'.
• To remove an element from the stack, simply remove the node which is
pointed by 'top' by moving 'top' to its previous node in the list.
• The next field of the First element must be always NULL.

22/01/2023 29
Example Stack – Linked List

Diagram Reference :http://www.btechsmartclass.com/data_structures/stack-using-linked-list.html

22/01/2023 30
Create Node – Linked List
1. Include all the header files which are used in the program. And declare all
the user defined functions
2. Define a 'Node' structure with two members data and next
3. Define a Node pointer 'top' and set it to NULL
4. Implement the main method by displaying Menu with list of operations and
make suitable function calls in the main method

22/01/2023 31
push(value)
Inserting an element into the Stack
1. Create a newNode with given value

2. Check whether stack is Empty (top == NULL)

3. If it is Empty, then set newNode → next = NULL

4. If it is Not Empty, then set newNode → next = top

5. Finally, set top = newNode

22/01/2023 32
void push()
struct Node
{
Int data;
struct Node *next;
}
struct Node *top=NULL;

void push(int value)

{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(top == NULL)
{ top=newNode;}
else
{
newNode->next = top;
top = newNode;
}
printf("\nInsertion is Success!!!\n");
}22/01/2023 33
pop()
Deleting an Element from a Stack
1. Check whether stack is Empty (top == NULL)

2. If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and

terminate the function

3. If it is Not Empty, then define a Node pointer 'temp' and set it to 'top‘

4. Then set 'top = top → next‘

5. Finally, delete 'temp'. (free(temp))

22/01/2023 34
void pop()
void pop()
{
struct Node *temp;
if(top == NULL)
printf("\nStack is Empty!!!\n");
else
{
temp=top;
printf("\nDeleted element: %d", top->data);
top = top->next;
free(temp);
}
}
22/01/2023 35
display()
Displaying stack of elements
1. Check whether stack is Empty (top == NULL)
2. If it is Empty, then display 'Stack is Empty!!!' and terminate the function
3. If it is Not Empty, then define a Node pointer 'temp' and initialize with top
4. Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack. (temp → next != NULL)
5. Finally! Display 'temp → data ---> NULL'

22/01/2023 36
void display()
void display()
{
struct Node *temp;
if(top == NULL)
printf("\nStack is Empty!!!\n");
else
{
temp=top;
while(temp->next != NULL)
{
printf("%d--->",temp->data);
temp = temp -> next;
} 102030
}
}
22/01/2023 37
Stack - Applications
1. Infix to Postfix Conversion
2. Postfix Evaluation
3. Balancing Symbols
4. Nested Functions
5. Tower of Hanoi

22/01/2023 38
Infix to Postfix Conversion

22/01/2023 39
Introduction
• Expression conversion is the most important application of stacks

• Given an infix expression can be converted to both prefix and postfix

notations

• Based on the Computer Architecture either Infix to Postfix or Infix to Prefix

conversion is followed

22/01/2023 40
Expression
• Made of values and operators
• Values are called operands
• Example:
2*3+5
Operands: 2, 3, 5
Operators: *, +

22/01/2023 41
What is Infix, Postfix & Prefix?
• Infix Expression : The operator appears in-between every pair of operands.
operand1 operator operand2 (a+b)

• Postfix expression: The operator appears in the expression after the

operands. operand1 operand2 operator (ab+)

• Prefix expression: The operator appears in the expression before the

operands. operator operand1 operand2 (+ab)

22/01/2023 42
Example – Infix, Prefix & Postfix

Infix Prefix Postfix

(A + B) / D / +ABD AB+ D /

(A + B) / (D + E) / +AB+ D E AB+ D E+ /

(A - B / C + E)/(A + B) / + - A / B C E + A B ABC /- E+AB+ /

B ^ 2  - 4 * A * C - ^ B2* * 4AC B2 ^4A* C *-

22/01/2023 43
Why postfix representation of the expression?

• Infix expressions are readable and solvable by humans because of easily

distinguishable order of operators, but compiler doesn't have integrated
order of operators.

• The compiler scans the expression either from left to right or from right to
left.

22/01/2023 44
Why postfix representation of the expression?

• Consider the below expression: a op1 b op2 c op3 d

If op1 = +, op2 = *, op3 = +

a + b *c +d

• The compiler first scans the expression to evaluate the expression b * c, then
again scan the expression to add a to it. The result is then added to d after
another scan.

22/01/2023 45
Why postfix representation of the expression?

• The repeated scanning makes it very in-efficient. It is better to convert the

expression to postfix(or prefix) form before evaluation.

• The corresponding expression in postfix form is: abc*+d+.

• The postfix expressions can be evaluated easily in a single scan using a stack.

22/01/2023 46
ALGORITHM
Step 1 : Scan the Infix Expression from left to right.
Step 2 : If the scanned character is an operand, append it with final Infix to Postfix string.
Step 3 : Else,
Step 3.1 : If the precedence order of the scanned(incoming) operator is greater than the precedence
order of the operator in the stack (or the stack is empty or the stack contains a ‘(’ ), push it on stack.
Step 3.2 : Else, Pop all the operators from the stack which are greater than or equal to in precedence
than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you
encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
Step 4 : If the scanned character is an ‘(‘ , push it to the stack.
Step 5 : If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and
discard both the parenthesis.
Step 6 : Repeat steps 2-6 until infix expression is scanned.
Step 7 : Print the output
Step 8 : Pop and output from the stack until it is not empty.

22/01/2023 47
Conversion of infix to postfix expression:

a + b *c + (d* e + f) * g Postfix: abc*+de*f+g*+

22/01/2023 48
> 2^3^4;

The exponentiation operator is non-associative. If you wish to

do more than one exponentiation in an expression, you must
use parentheses.

> (2^3)^4;

or

> 2^(3^4);

Image from Data Structures by Mark Allen Weiss book

22/01/2023 49
Exercise Problems to Solve
Infix to Postfix conversion
1. A+B-C
2. A+B*C
3. (A+B)*C
4. (A+B)*(C-D)
5. ((A+B)*C-(D-E))%(F+G)
6. A*(B+C/D)
7. ((A*B)+(C/D))
8. ((A*(B+C))/D)
9. (A*(B+(C/D)))
10.(2+((3+4)*(5*6)))
11.B ^ 2 - 4 * A * C
12.(A - B / C + E)/(A + B)

22/01/2023 50
Program: Infix to Postfix Conversion

#include <stdio.h> /* Main Program */

#include <ctype.h>
void main()
#define SIZE 50
{
char stack[SIZE];
char infix[50],postfix[50],ch,elem;
int top=-1; /* Global declarations */
int i=0,k=0;
push(char elem)
printf("Enter Infix Expression : ");
{ /* Function for PUSH operation */
scanf("%s",infix);
stack[++top]=elem;
push('#');
}
while( (ch=infix[i++]) != '\0')
char pop()
{
{ /* Function for POP operation */
if( ch == '(') push(ch);
return(stack[top--]);
else
}
if(isalnum(ch)) postfix[k++]=ch;
int pr(char symbol)
else
{ /* Function for precedence */
if( ch == ')')
if(symbol == '^')/* exponent operator, highest precedence*/
{
{
while( stack[top] != '(') Output:
return(3);
postfix[k++]=pop();
}
elem=pop(); /* Remove ( */
else if(symbol == '*' || symbol == '/')
} Enter Infix Expression :
{
return(2);
else a+b*(c-d)
{ /* Operator */
}
while( pr(stack[top]) >= pr(ch) )
else if(symbol == '+' || symbol == '-') /* lowest precedence */
{
postfix[k++]=pop(); Postfix Expression = abcd-*+
push(ch);
return(1);
}
}
}
else
while( stack[top] != '#') /* Pop from stack till empty */
{
postfix[k++]=pop();
return(0);
postfix[k]='\0'; /* Make postfix as valid string */
}
printf("\nPostfix Expression = %s\n",postfix);
}
22/01/2023 } 51
SESSION 3

22/01/2023 52
Postfix Expression Evaluation

22/01/2023 53
Postfix Expression
• A postfix expression is a collection of operators and operands
in which the operator is placed after the operands.

Image Reference : http://www.btechsmartclass.com/data_structures/expressions.html

22/01/2023 54
Postfix Expression Evaluation using
Stack 

22/01/2023 55
Algorithm
1. Read all the symbols one by one from left to right in the given Postfix
Expression
2. If the reading symbol is operand, then push it on to the Stack.
3. If the reading symbol is operator (+ , - , * , / etc.,), then perform TWO pop
operations and store the two popped operands in two different variables
(operand1 and operand2). Then perform reading symbol operation
using operand1 and operand2 and push result back on to the Stack.
a. Operand2=pop()
b. Operand1=pop()
c. Ans=operand1 (op) operand2
4. Finally! perform a pop operation and display the popped value as final
result.
22/01/2023 56
22/01/2023 57
Example 1

22/01/2023 58
Example 2

Image from Data Structures by Mark Allen Weiss book

22/01/2023 59
Program: Postfix Evaluation
while(*e != '\0') case '*':
#include<stdio.h>
{ {
int stack[20];
int top = -1;
if(isdigit(*e)) n3 = n2 * n1;
{ break;
void push(int x)
num = *e - 48; }
{ push(num);
stack[++top] = x; case '/':
}
} else {
int pop() { n3 = n2 / n1;
{ n1 = pop(); break;
return stack[top--]; n2 = pop(); }
switch(*e)
Output:
} }
{ Enter the expression :: 8432-*+
int main() push(n3);
case '+': The result of expression 8432-*+ = 12
{ }
{
char exp[20]; e++;
n3 = n2 + n1;
char *e; break; }
int n1,n2,n3,num; } printf("\nThe result of expression %s = %d\n\n",exp,pop());
printf("Enter the expression :: "); case '-': return 0;
scanf("%s",exp); {
}
e = exp; n3 = n2 - n1;
22/01/2023 break; 60
}
Balancing Symbols

22/01/2023 61
Introduction
• Stacks can be used to check if the given expression has balanced symbols or
not.
• The algorithm is very much useful in compilers.
• Each time parser reads one character at a time.
– If the character is an opening delimiter like ‘(‘ , ‘{‘ or ‘[‘ then it is PUSHED in to the
stack.
– When a closing delimiter is encountered like ‘)’ , ‘}’ or ‘]’ is encountered, the stack is
popped.
– The opening and closing delimiter are then compared.
– If they match, the parsing of the string continues.
– If they do not match, the parser indicates that there is an error on the line.

22/01/2023 62
Balancing Symbols - Algorithm

• Create a stack
• while ( end of input is not reached ) {
– If the character read is not a symbol to be balanced, ignore it.
– If the character is an opening delimiter like ( , {  or [ , PUSH it into the stack.
– If it is a closing symbol like ) , } , ] , then if the stack is empty report an
error, otherwise POP the stack.
– If the symbol POP-ed is not the corresponding delimiter, report an error.
• At the end of the input, if the stack is not empty report an error.

22/01/2023 63
Example 1
Expression Valid? Description

The expression is having

(A+B) + (C-D) Yes
balanced symbol

((A+B) + (C-D) No One closing brace is missing.

Opening and closing braces

((A+B) + [C-D]) Yes
correspond

The last brace does not

((A+B) + [C-D]] No correspond with the first
opening brace.

22/01/2023 64
Example

Image Reference : https://github.com/niinpatel/Parenthesis-Matching-with-Reduce-Method

22/01/2023 65
Example: {(A+B)*C

22/01/2023 66
Program else
{
printf("\nUNBALANCED EXPRESSION\n");
#include<stdio.h> int main() break;
#include<stdlib.h> { }}
#include<string.h> char exp[MAX]; if(exp[i] == '}')
#define MAX 20 int i = 0; {
s.top = -1; if(s.stk[s.top] == '{')
struct stack printf("\nINPUT THE EXPRESSION : "); {
{ scanf("%s", exp); pop(); // Pop the stack until closed bracket is found
char stk[MAX]; for(i = 0;i < strlen(exp);i++) }
int top; { else
}s; if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
{ printf("\nUNBALANCED EXPRESSION\n");
void push(char item) push(exp[i]); // Push the open bracket break;
{ continue; }}}}
if (s.top == (MAX - 1)) } if(s.top == -1)
printf ("Stack is Full\n"); else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}') // If {
else a closed bracket is encountered printf("\nBALANCED EXPRESSION\n"); // Finally if the stack is empty,
{ { display that the expression is balanced
s.top = s.top + 1; // Push the char and increment top if(exp[i] == ')') }}
s.stk[s.top] = item; {
}}
if(s.stk[s.top] == '(')
{
pop(); // Pop the stack until closed bracket is found
void pop()
}
{
else
if (s.top == - 1)
{
{
printf("\nUNBALANCED EXPRESSION\n");
printf ("Stack is Empty\n");
break;
}
}}
else
if(exp[i] == ']')
{
{
s.top = s.top - 1; // Pop the char and decrement top if(s.stk[s.top] == '[')
}} {
pop(); // Pop the stack until closed bracket is found
22/01/2023 } 67
References

1. https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
2. https://www.codesdope.com/course/data-structures-stacks/
3. http://www.firmcodes.com/write-a-c-program-to-implement-a-stack-using-an-array-and-linked-list/
4. http://www.btechsmartclass.com/data_structures/stack-using-linked-list.html
5. http://www.exploredatabase.com/2018/01/stack-abstract-data-type-data-structure.html
6.  https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
7.  https://www.hackerearth.com/practice/notes/stacks-and-queues/
8. https://github.com/niinpatel/Parenthesis-Matching-with-Reduce-Method
9. https://www.studytonight.com/data-structures/stack-data-structure
10. https://www.programming9.com/programs/c-programs/230-c-program-to-convert-infix-to-postfix-expression-using-stack

22/01/2023 68
SESSION 6

22/01/2023 69
Applications of Stack: Function Call and Return
• 2 types of Memory
– Stack
– Heap
• Stack memory stores the data (variables) related to
each function.
• Why is it called stack memory?
– The last function to be called is the first to return (LIFO)
– The data related to a function are pushed into the stack
when a function is called and popped when the function
returns
22/01/2023 70
Function Calls
• Function calls another function
->We are executing function A. In the course of its execution,
function A calls another function B. Function B in turn calls another
function C, which calls function D.
Function A
Function B
Function C
Function D
Function E
22/01/2023 71
• When A calls B, A is pushed on top of the system stack. When the
execution of B is complete, the system control will remove A from
the stack and continue with its execution.

• When B calls C, B is pushed on top of the system stack. When the

execution of C is complete, the system control will remove B from
the stack and continue with its execution.

• When C calls D, C is pushed on top of the system stack. When the

execution of D is complete, the system control will remove C from
the stack and continue with its execution.

22/01/2023 72
• When D calls E, D is pushed on top of the system stack. When the
execution of E is complete, the system control will remove D from
the stack and continue with its execution.

• When E has executed, D will be removed for execution.

• When C has executed, B will be removed for execution.
• When D has executed, C will be removed for execution.
• When B has executed, A will be removed for execution.

22/01/2023 73
Nested Function Calls
• Consider the code snippet below:
main() foo() bar()
{ { {
... ... ...
foo(); bar(); }
...
bar(); }
}

22/01/2023 74
Nested Function Calls and Returns in Stack Memory

• Stack memory when the code executes:

Direction of Stack growth

Image Source: https://loonytek.com/2015/04/28/call-stack-internals-part-1/
22/01/2023 75
Function Call and Return in Stack Memory
• Each call to a function pushes the function’s activation record
(or stack frame) into the stack memory
• Activation record mainly consists of: local variables of the
function and function parameters
• When the function finishes execution and returns, its activation
record is popped

22/01/2023 76
Recursion
• A recursive function is defined as a function that calls itself.

• Since a recursive function repeatedly calls itself, it makes use of the system stack
to temporarily store the return address and local variables of the calling function.

• Every recursive solution has two major cases. They are

 Base case, in which the problem is simple enough to be solved directly without making any
further calls to the same function.

 Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second
the function calls itself but with sub-parts of the problem obtained in the first step. Third,
the result is obtained by combining the solutions of simpler sub-parts.

22/01/2023 77
Recursion
• A recursive function is a function that calls itself during its
execution.
• Each call to a recursive function pushes a new activation record
(a.k.a stack frame) into the stack memory.
• Each new activation record will consist of freshly created local
variables and parameters for that specific function call.
• So, even though the same function is called multiple times, a new
memory space will be created for each call in the stack memory.

22/01/2023 78
Recursion Handling by Stack Memory
• Factorial
program
int fact( int n)

Direction of Stack growth

{
if (n==1)
return 1;
else
return (n*fact(n-1));
}

fact(4);

22/01/2023 Image Source: https://stackoverflow.com/questions/19865503/can-recursion-be-named-as-a-simple-function-call 79

Example : Factorial Of a Number
To calculate n!, we multiply the number with factorial of the number that is 1
less than that number.
n! = n * (n–1)!
5! = 5 * 4! Where 4! = 4 * 3!
= 5 * 4 * 3! Where 3! = 3 * 2!
= 5 * 4 * 3 * 2! Where 2! = 2*1!
= 5 * 4 * 3 * 2 * 1! Where 1! = 1
=5*4*3*2*1
= 120

22/01/2023 80
Base case and Recursive Case
• Base case
When n = 1, because if n = 1, the result will be 1 as 1! = 1.
• Recursive case
Factorial function will call itself but with a smaller value of n,
this case can be given as
factorial(n) = n × factorial (n–1)

22/01/2023 81
Advantages of using a recursive program
• Recursive solutions often tend to be shorter and simpler than
non-recursive ones.
• Code is clearer and easier to use.
• Recursion works similar to the original formula to solve a
problem.
• Recursion follows a divide and conquer technique to solve
problems.
• In some (limited) instances, recursion may be more efficient.

22/01/2023 82
Drawbacks/Disadvantages of using a recursive program

• For some programmers and readers, recursion is a difficult concept.

• Recursion is implemented using system stack. If the stack space on the system
is limited,
• Recursion to a deeper level will be difficult to implement.
• Aborting a recursive program in midstream can be a very slow process.
• Using a recursive function takes more memory and time to execute as
compared to its nonrecursive counterpart.
• It is difficult to find bugs, particularly while using global variables.

22/01/2023 83
Factorial using recursion

22/01/2023 84
Towers of Hanoi
• Figure below shows three rings mounted on pole A. The problem is
to move all these rings from pole A to pole C while maintaining the
same order. The main issue is that the smaller disk must always come
above the larger disk
A-> Source pole
B-> Spare pole
C-> Destination pole

22/01/2023 85
• To transfer all the three rings from A to C, we will
first shift the upper
two rings (n–1 rings) from the source pole to the
spare pole.
1) Source pole -> Destination pole
2) Source pole -> Spare pole
3) Destination pole -> Spare pole
• n–1 rings have been removed from pole A, the nth
ring can be easily moved from the source pole (A)
to the destination pole (C).
4) Source pole -> Destination pole
22/01/2023 86
• The final step is to move the n–1 rings from the spare pole
(B) to
the destination pole (C).
5) Spare pole -> Source pole
6) Spare pole -> Destination pole
7) Source pole -> Destination pole
Base case: if n=1
Move the ring from A to C using B as spare
Recursive case:
Move n – 1 rings from A to B using C as spare
Move the one ring left on A to C using B as spare
Move n – 1 rings from B to C using A as spare
22/01/2023 87
Step by Step Illustration

22/01/2023 88
Code Snippet
• Function Call:
move(n,'A', 'C', 'B');
• Function Definition:

22/01/2023 89
Session 7

22/01/2023 90
Applications of Recursion: Towers of Hanoi
Towers of Hanoi Problem:
There are 3 pegs and n disks. All the n disks are stacked in 1 peg in the order of
their sizes with the largest disk at the bottom and smallest on top. All the disks
have to be transferred to another peg.
Rules for transfer:
• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack i.e. a disk can only be moved if it is the
uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

22/01/2023 91
• Rules to be followed:
• Our objective in this puzzle is to move all these disks to
another pillar without changing the order in which the
disks are placed in the initial state. The rules for this
puzzle are:
• 1. We can move only one disk at a time.
• 2. We can remove only the top disk.
• 3. We can only place a disk above a disk of a larger size.

22/01/2023 92
Towers of Hanoi
• Initial Position:

A B
C
• All disks from peg A have to be transferred to peg C

22/01/2023 93
Towers of Hanoi Solution for 3 disks

Image Source: https://www.includehelp.com/data-structure-tutorial/tower-of-

hanoi-using-recursion.aspx
22/01/2023 94
Towers of Hanoi – Recursive Solution
/* N = Number of disks
Beg, Aux, End are the pegs */

Tower(N, Beg, Aux, End)

Begin
if N = 1 then
Print: Beg --> End;
else
Call Tower(N-1, Beg, End,
Aux);
Print: Beg --> End;
Call Tower(N-1, Aux, Beg,
End);
endif
22/01/2023 End 95
// Function to implement legal movement between
Tower of Hanoi Program // two poles
void moveDisksBetweenTwoPoles(struct Stack *src,
#include <iostream> // Function to add an item to stack. It increases struct Stack *dest, char s, char d)
#include <bits/stdc++.h> // top by 1 {
using namespace std; void push(struct Stack *stack, int item) int pole1TopDisk = pop(src);
{ int pole2TopDisk = pop(dest);
// A structure to represent a stack if (isFull(stack))
struct Stack return; // When pole 1 is empty
{ stack -> array[++stack -> top] = item; if (pole1TopDisk == INT_MIN)
unsigned capacity; } {
int top;
push(src, pole2TopDisk);
int *array; // Function to remove an item from stack. It moveDisk(d, s, pole2TopDisk);
}; // decreases top by 1 }
int pop(struct Stack* stack)
// function to create a stack of given capacity. { // When pole2 pole is empty
struct Stack* createStack(unsigned capacity) if (isEmpty(stack)) else if (pole2TopDisk == INT_MIN)
{ return INT_MIN; {
struct Stack* stack = return stack -> array[stack -> top--]; push(dest, pole1TopDisk);
(struct Stack*) malloc(sizeof(struct Stack)); } moveDisk(s, d, pole1TopDisk);
stack -> capacity = capacity;
}
stack -> top = -1; //Function to show the movement of disks
stack -> array = void moveDisk(char fromPeg, char toPeg, int disk) // When top disk of pole1 > top disk of pole2
(int*) malloc(stack -> capacity * sizeof(int)); { else if (pole1TopDisk > pole2TopDisk)
return stack; cout <<"Move the disk " << disk <<" from " << {
} fromPeg << " to "<< toPeg << endl; push(src, pole1TopDisk);
} push(src, pole2TopDisk);
// Stack is full when top is equal to the last index
moveDisk(d, s, pole2TopDisk);
int isFull(struct Stack* stack)
}
{
return (stack->top == stack->capacity - 1);
// When top disk of pole1 < top disk of pole2
}
else
{
// Stack is empty when top is equal to -1
push(dest, pole2TopDisk);
int isEmpty(struct Stack* stack)
push(dest, pole1TopDisk);
{
moveDisk(s, d, pole1TopDisk);
return (stack->top == -1);
}
}
}
22/01/2023 96
Program

//Function to implement TOH puzzle

void tohIterative(int num_of_disks, struct Stack
*src, struct Stack *aux,
struct Stack *dest)
// Driver Program
{ int main()
int i, total_num_of_moves; {
char s = 'S', d = 'D', a = 'A';

//If number of disks is even, then interchange // Input: number of disks

//destination pole and auxiliary pole unsigned num_of_disks = 3;
if (num_of_disks % 2 == 0)
{ struct Stack *src, *dest, *aux;
char temp = d;
d = a;
a = temp; // Create three stacks of size 'num_of_disks'
} // to hold the disks Output:
total_num_of_moves = pow(2, num_of_disks) - 1; src = createStack(numofdisks);
//Larger disks will be pushed first aux = createStack(numofdisks); Move the disk 1 from 'S' to 'D'
for (i = num_of_disks; i >= 1; i--) dest = createStack(numofdisks);
push(src, i); Move the disk 2 from 'S' to 'A'
tohIterative(numofdisks, src, aux, dest); Move the disk 1 from 'D' to 'A'
for (i = 1; i <= total_num_of_moves; i++)
{ return 0; Move the disk 3 from 'S' to 'D'
if (i % 3 == 1) }
moveDisksBetweenTwoPoles(src, dest, s, d);
Move the disk 1 from 'A' to 'S'
Move the disk 2 from 'A' to 'D'
else if (i % 3 == 2)
moveDisksBetweenTwoPoles(src, aux, s, a); Move the disk 1 from 'S' to 'D'
else if (i % 3 == 0)
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
22/01/2023 97
The Queue ADT
• With a queue, insertion is done at one end whereas deletion is performed at
the other end.
• It is a First In First Out (FIFO) Structure. That is, the first element to enter into
the queue will be the first element to get out of the queue.

Front Rear

22/01/2023 98
Image Source: https://www.codesdope.com/course/data-structures-queue/
QUEUE
• Queue is a linear data structure in which the insertion and deletion operations are
performed at two different ends.
• In a queue data structure, adding and removing elements are performed at two
different positions.
• The insertion is performed at one end and deletion is performed at another end.
• In a queue data structure, the insertion operation is performed at a position which is
known as 'rear' and the deletion operation is performed at a position which is
known as 'front’.
• In queue data structure, the insertion and deletion operations are performed based
on FIFO (First In First Out) principle.

22/01/2023 99
QUEUE

Let us explain the concept of queues using the analogies given below.
 People moving on an escalator. The people who got on the escalator first will be the first one to step
out of it.
 People waiting for a bus. The first person standing in the line will be the first one to get into the bus.
 People standing outside the ticketing window of a cinema hall. The first person in the line will get the
ticket first and thus will be the first one to move out of it.
 Luggage kept on conveyor belts. The bag which was placed first will be the first to come out at the
other end.
 Cars lined at a toll bridge. The first car to reach the bridge will be the first to leave.

22/01/2023 100
The basic operations on a Queue
• Enqueue: inserts an element at the end of the list (called
the rear)
• Dequeue: deletes (and returns) the element at the start of
the list (called the front).

• Peek: Get the front element

22/01/2023 101
SESSION 8

22/01/2023 102
Queue Representations
• Queues can be represented using:
– Arrays
– Linked Lists

22/01/2023 103
ARRAY REPRESENTATION OF QUEUES

• Queues can be implemented by using either arrays or

linked lists.

ARRAY REPRESENTATION OF QUEUES:

• Array is the easiest way to implement a queue. Queue can
be also implemented using Linked List or Stack.

• Queues can be easily represented using linear arrays. As

stated earlier, every queue has FRONT and REAR variables
that point to the position from where deletions and
insertions can be done, respectively.

22/01/2023
Implementation of queue using an array 104
Enqueue operation(Insertion)
Algorithm to insert an element in a queue
Step 1: IF REAR = MAX-1
Write OVERFLOW Goto step 4
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR =0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT

22/01/2023 105
Dequeue operation(Deletion)
Algorithm to delete an element from a
queue
Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1 [END OF
IF]
Step 2: EXIT

22/01/2023 106
Program
#include<stdio.h> //Function created to handle dequeue //function to print the queue
#define SIZE 5 void dequeue(){ void printQueue(){
if(front == -1){ if(rear == -1)
//Basic value initialisation printf("Can't dequeue as the queue is empty\n");
int queue[SIZE], front = -1, rear = -1; printf("\nUnable to display as queue is empty");
}
else{ else{
//Function created to handle enqueue
printf("We have dequeued : %d\n", queue[front]); int i;
void enqueue(int item){
front = front + 1; printf("\nThe queue after enqueue & dequeue ops looks
if(rear == SIZE-1){ like :");
printf("Can't enqueue as the queue is full\n"); //Only happens when the last element was
} dequeued for(i = front; i <= rear; i++)
if(front > rear){
else{ printf("%d ",queue[i]);
front = -1;
//The first element condition rear = -1; }
if(front == -1){ } }
front = 0; } int main()
} {
}
//enqueue begins here
enqueue(2);
rear = rear + 1;
enqueue(4);
queue[rear] = item;
enqueue(6);
printf("We have enqueued %d\n",item);
enqueue(8);
}
//dequeue beings here
} dequeue();
dequeue();
printQueue();
return 0;
}
22/01/2023 107
Drawback of array implementation
• Although, the technique of creating a queue is easy, but there are some drawbacks of using
this technique to implement a queue.
• Memory wastage: The space of the array, which is used to store queue elements, can never
be reused to store the elements of that queue because the elements can only be inserted at
front end and the value of front might be so high so that, all the space before that, can never
be filled.
• Deciding the array size: One of the most common problem with array implementation is the
size of the array which requires to be declared in advance. Due to the fact that, the queue can
be extended at runtime depending upon the problem, the extension in the array size is a time
taking process and almost impossible to be performed at runtime since a lot of reallocations
take place. Due to this reason, we can declare the array large enough so that we can store
queue elements as enough as possible but the main problem with this declaration is that,
most of the array slots (nearly half) can never be reused. It will again lead to memory wastage.

22/01/2023 108
LINKED LIST REPRESENTATION OF QUEUES
• Due to the drawbacks discussed in the previous section, the array implementation can not be used
for the large scale applications where the queues are implemented. One of the alternative of array
implementation is linked list implementation of queue.
• The storage requirement of linked representation of a queue with n elements is o(n) while the time
requirement for operations is o(1).
• In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each
element of the queue points to its immediate next element in the memory.
• In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear
pointer. The front pointer contains the address of the starting element of the queue while the rear
pointer contains the address of the last element of the queue.
• Insertion and deletions are performed at rear and front end respectively. If front and rear both are
NULL, it indicates that the queue is empty.

22/01/2023 109
LINKED LIST REPRESENTATION OF QUEUES

The linked representation of queue is shown in the Operations on Linked Queue

following figure.
• There are two basic operations
which can be implemented on the
linked queues.
• The operations are Insertion and
Deletion.

22/01/2023 110
Operations on Linked Queue

Insertion operation Deletion operation

Algorithm
Step 1: Allocate the space for the new node PTR
Algorithm
Step2:SET PTR->DATA=VAL Step 1: IF FRONT = NULL
Step 3: IF FRONT = NULL Write " Underflow " Go to Step 5
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR ->NEXT = NULL
[END OF IF]
ELSE Step 2: SET PTR = FRONT
SET REAR -> NEXT = PTR
SET REAR = PTR
Step 3: SET FRONT = FRONT -> NEXT
SET REAR -> NEXT = NULL Step 4: FREE PTR
[END OF IF] Step 5: END
• Step 4: END

22/01/2023 111
Array Implementation of Queues
• Queue can be implemented using a one-dimensional array.
• We need to keep track of 2 variables: front and rear
• front is the index in which the first element is present
• rear is the index in which the last element is present

https://www.javatpoint.com/array-representation-of-queue

22/01/2023 112
Enqueue in Array Implementation of Queue
//Basic Idea
Time Complexity:
enqueue(num): O(1)
rear++
queue[rear]=num
return

22/01/2023 113
Dequeue in Array Implementation of Queue
//Basic Idea Time Complexity: O(1)
O(n) if elements are
dequeue(): shifted
num = queue[front]
front++
return num

22/01/2023 114
Enqueue and Dequeue in Queue

Image Source: https://slideplayer.com/slide/4151401/

22/01/2023 115
Disadvantage of Array Implementation of Queue
• Multiple enqueue and dequeue operations may
lead to situation like this:

https://www.tutorialride.com/data-structures/queue-in-data-
structure.htm

• No more insertion is possible (since rear cannot

be incremented anymore) even though 2 spaces
are free.
• Workaround: Circular Queue, Shifting elements
after each dequeue
22/01/2023 116
Linked List Implementation of Queue

• In the linked list implementation of queue,

two pointers are used, namely, front and rear
• New nodes are created when an element has
to be inserted.
• Each node consists of queue element and a
pointer to the next node

22/01/2023 117
Enqueue Operation in Linked List Implementation of Queue
• Enqueue basic code: Time Complexity: O(1)
ptr -> data = item;
rear -> next = ptr;  
rear = ptr;  
rear -> next = NULL;  

22/01/2023 118
Image Source: https://www.log2base2.com/data-structures/queue/queue-
Dequeue Operation in Linked List Implementation of Queue
• Dequeue basic code: Time Complexity:
ptr = front;   O(1)

front = front -> next;  
free(ptr);  
Rear

Front

Image Source:
22/01/2023 https://learnersbucket.com/tutorials/data-structures/implement-queue-using- 119
linked-list/
References
• Seymour Lipschutz, Data Structures, Schaum’s Outlines, 2014.

22/01/2023 120
SESSION 11

22/01/2023 121
Circular Queue

22/01/2023 122
CIRCULAR QUEUES
• Circular Queue is a linear data structure in which the
operations are performed based on FIFO (First In First Out)
principle and the last position is connected back to the first
position to make a circle. It is also called ‘Ring Buffer’.
• In a normal Queue, we can insert elements until queue
becomes full. But once queue becomes full, we cannot
insert the next element even if there is a space in front of
queue.
• Deletions and insertions can only be performed at front and
rear end respectively, as far as linear queue is concerned.

22/01/2023 123
CIRCULAR QUEUES
Consider the queue shown in the following figure.
• However, if we delete 2 elements at the front end
of the queue, we still can not insert any element
since the condition rear = max -1 still holds.
• This is the main problem with the linear queue,
although we have space available in the array, but
we can not insert any more element in the queue.
This is simply the memory wastage and we need
to overcome this problem.
• The Queue shown in above figure is completely
filled and there can't be inserted any more
element due to the condition rear == max - 1
becomes true.
• One of the solution of this problem is circular
queue. In the circular queue, the first index
comes right after the last index. You can think of a
circular queue as shown in the following figure.
22/01/2023 124
CIRCULAR QUEUES
• One of the solution of this problem is circular
queue. In the circular queue, the first index
comes right after the last index. You can think of
a circular queue as shown in the following
figure.
• Circular queue will be full when front = -1
and rear = max-1. Implementation of circular
queue is similar to that of a linear queue.

• Only the logic part that is implemented in

the case of insertion and deletion is different
from that in a linear queue.

22/01/2023 125
CIRCULAR QUEUE OPERATIONS
Algorithm to insert an element in circular queue
Insertion in Circular queue Step 1: IF (REAR+1)%MAX = FRONT
• There are three scenario of inserting an element in a Write " OVERFLOW "
Goto step 4
queue.
[End OF IF]

• If (rear + 1)%maxsize = front, the queue is full. In that Step2:IF FRONT=-1 and REAR=-1
case, overflow occurs and therefore, insertion can not SET FRONT = REAR = 0
be performed in the queue.
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
• If rear != max - 1, then rear will be incremented to the
mod(maxsize) and the new value will be inserted at
ELSE
the rear end of the queue. SET REAR = (REAR + 1) % MAX
[END OF IF]
• If front != 0 and rear = max - 1, then it means that
queue is not full therefore, set the value of rear to 0 Step 3: SET QUEUE[REAR] = VAL
and insert the new element there.
Step 4: EXIT
22/01/2023 126
CIRCULAR QUEUE OPERATIONS
Algorithm to delete an element in circular queue
Deletion in Circular queue Step 1: IF FRONT = -1
• To delete an element from the circular queue, we Write " UNDERFLOW " Goto Step 4
must check for the three following conditions. [END of IF]
• If front = -1, then there are no elements in the Step 2: SET VAL = QUEUE[FRONT]
queue and therefore this will be the case of an Step 3: IF FRONT = REAR
underflow condition. SET FRONT = REAR = -1
• If there is only one element in the queue, in this ELSE
case, the condition rear = front holds and therefore, IF FRONT = MAX -1
both are set to -1 and the queue is deleted
SET FRONT = 0
completely.
ELSE
• If front = max -1 then, the value is deleted from the SET FRONT = FRONT + 1
front end the value of front is set to 0. [END of IF]
• Otherwise, the value of front is incremented by 1 [END OF IF]
and then delete the element at the front end. Step 4: EXIT

22/01/2023 127
Operations Involved
• Enqueue
• Dequeue

22/01/2023 128
Variables Used
• MAX- Number of entries in the array
• Front – is the index of front queue entry in an array (Get the front item
from queue)
• Rear – is the index of rear queue entry in an array.(Get the last item from
queue)

22/01/2023 129
Concepts of Circular Queue

22/01/2023 130
Illustration of Enqueue and Dequeue

22/01/2023 131
Applications of Queue
• Queue, as the name suggests is used whenever we need to manage any
group of objects in an order in which the first one coming in, also gets out
first while the others wait for their turn, like in the following scenarios:
• Serving requests on a single shared resource, like a printer, CPU task
scheduling etc.
• In real life scenario, Call Center phone systems uses Queues to hold
people calling them in an order, until a service representative is free.
• Handling of interrupts in real-time systems. The interrupts are handled in
the same order as they arrive i.e First come first served.

22/01/2023 132
Review Questions
1. Explain the concept of a circular queue? How is it better than a linear queue?
2. Draw the queue structure in each case when the following operations are performed on an empty queue.
(a)Add A, B, C, D, E, F. (b) Delete two letters
(c) Add G (d) Add H
(e) Delete four letters (f) Add I
3. The circular queue will be full only when _____.
(a) FRONT=MAX-1 and REAR=MAX-1 (b) FRONT=0 and REAR=MAX-1
(c) FRONT=MAX-1 and REAR=0. (d) FRONT=0 and REAR=0
4. The function that deletes values from a queue is called ______.
(a) Enqueue (b)dequeue
(c) Pop (d) peek
5. New nodes are added at of the queue.
6. _________ allows insertion of elements at either ends but not in the middle.
7. A queue is a _____ data structure in which the element that is inserted first is the first one to be taken out.
8. In a circular queue, the first index comes after the ______ index.
9. In the computer’s memory, queues can be implemented using _________ and _______.
10. The storage requirement of linked representation of queue with n elements is ____ and the typical time requirement for
operations is _______.

22/01/2023 133
Difference between Queue and Circular Queue
• In a normal Queue, we can insert elements until queue becomes full. But
once queue becomes full, we can not insert the next element even if there
is a space in front of queue.

• The unused memory locations in the case of ordinary queues can be

utilized in circular queues.

22/01/2023 134
SESSION 12

22/01/2023 135
Circular Queue Example-ATM
ATM is the best example for the circular queue. It does the following
using circular queue
1. ATM sends request over private network to central server
2. Each request takes some amount of time to process.
3. More request may arrive while one is being processed.
4. Server stores requests in queue if they arrive while it is busy.
5. Queue processing time is negligible compared to request
processing time.

22/01/2023 136
Josephus problem
Flavius Josephus is a Jewish historian living in the 1st century. According
to his account, he and his 40 comrade soldiers were trapped in a cave,
surrounded by Romans. They chose suicide over capture and decided that
they would form a circle and start killing themselves using a step of three.
As Josephus did not want to die, he was able to find the safe place, and
stayed alive with his comrade, later joining the Romans who captured
them.

22/01/2023 137
Can you find the safe place?
40 41 1 2
38 39 3
4
37
36 5
35 6
7
34
8
33
9
32
Safe place
10
31
11
30 Can you find the safe
12
29 place?
13
28
27 14
26 15
25 16
24 23 19 18 17
22 21 20
22/01/2023 138
The first algorithm: Simulation
• We can find f(n) using simulation.
– Simulation is a process to imitate the real objects,
states of affairs, or process.
– We do not need to “kill” anyone to find f(n).
• The simulation needs
(1) a model to represents “n people in a circle”
(2) a way to simulate “kill every 2nd person”
(3) knowing when to stop

22/01/2023 139
Model n people in a circle
• We can use “data structure” to model it.
• This is called a
“circular linked list”. 1
– Each node is of some 8 2
“struct” data type
– Each link is a “pointer” 7 3
struct node {
int ID; 6 4
struct node *next; 5
}
22/01/2023 140
Kill every 2nd person
• Remove every 2nd node in the circular liked list.
– You need to maintain
the circular linked 1
structure after 8 2
removing node 2
– The process can 7
continue until … 3
6 4
5
22/01/2023 141
Knowing when to stop
• Stop when there is only one node left
– How to know that?
– When the *next is 1
pointing to itself 8
– It’s ID is f(n)
• f(8) = 1 7 3
6 4
5
22/01/2023 142
Double Ended Queue
• Double Ended Queue is also a Queue data structure in which the
insertion and deletion operations are performed at both the ends (front
and rear).

22/01/2023 143
Double Ended Queue

Double Ended Queue can be represented in TWO ways

• Input Restricted Double Ended Queue

• Output Restricted Double Ended Queue

22/01/2023 144
Input Restricted Double Ended Queue

In input restricted double ended queue, the insertion operation is

performed at only one end and deletion operation is performed at
both the ends.

Input Restricted Double Ended Queue

22/01/2023 145
Output Restricted Double Ended Queue

In output restricted double ended queue, the deletion operation is

performed at only one end and insertion operation is performed at both the
ends

Output Restricted Double Ended Queue

22/01/2023 146
Operations on Deque

The following are the operations applied on deque:

1. Insert at front
2. Delete from end
3. insert at rear
4. delete from rear

22/01/2023 147
22/01/2023 148
Enqueue operation

1. Initially, we are considering that the deque is empty, so both front and rear are set to -1,
i.e., f = -1 and r = -1.
2. As the deque is empty, so inserting an element either from the front or rear end would be the same thing.
Suppose we have inserted element 1, then front is equal to 0, and the rear is also equal to 0.

3. Suppose we want to insert the next element from the rear. To insert the element from the rear end, we first need to
increment the rear, i.e., rear=rear+1. Now, the rear is pointing to the second element, and the front is pointing to the
first element.

22/01/2023 149
4. Suppose we are again inserting the element from the rear end. To insert the element, we will first increment the rear,
and now rear points to the third element.

5. If we want to insert the element from the front end, and insert an element from the front, we have to decrement the value
of front by 1. If we decrement the front by 1, then the front points to -1 location, which is not any valid location in an array.
So, we set the front as (n -1), which is equal to 4 as n is 5. Once the front is set, we will insert the value as shown in the
below figure:

22/01/2023 150
Dequeue Operation

1.If the front is pointing to the last element of the array, and we want to perform the delete operation from the front. To
delete any element from the front, we need to set front=front+1. Currently, the value of the front is equal to 4, and if we
increment the value of front, it becomes 5 which is not a valid index. Therefore, we conclude that if front points to the
last element, then front is set to 0 in case of delete operation.

22/01/2023 151
2. If we want to delete the element from rear end then we need to decrement the rear value by 1, i.e., rear=rear-1 as
shown in the below figure:

22/01/2023 152
3. If the rear is pointing to the first element, and we want to delete the element from the rear end then we have to
set rear=n-1 where n is the size of the array as shown in the below figure:

22/01/2023 153
SESSION 13

22/01/2023 154
Priority Queue
Priority Queue is an extension of a queue with following properties:
• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low
priority.
• If two elements have the same priority, they are served according to their
order in the queue.
A priority queue is of two types:
• Ascending Order Priority Queue
• Descending Order Priority Queue

22/01/2023 155
Priority Queue Example

10 20 30 40

40 30 20 10

22/01/2023 156
Operations Involved
• insert(item, priority): Inserts an item with given priority.

• getHighestPriority(): Returns the highest priority item.

• pull_highest_priority_element: remove the element from the queue that

has the highest priority, and return it.

22/01/2023 157
Implementation of priority queue
– Circular array
– Multi-queue implementation
– Double Link List
– Heap Tree

22/01/2023 158
PQ implementation using Arrays/ Circular Queue

22/01/2023 159
PQ implementation using Multi Queue

22/01/2023 160
22/01/2023 161
Node of linked list in priority queue
It comprises of three parts
• Data − It will store the integer value.

• Address − It will store the address of a next node

• Priority −It will store the priority which is an integer value. It can range
from 0-10 where 0 represents the highest priority and 10 represents the
lowest priority.

22/01/2023 162
Example

22/01/2023 163
Applications of Priority Queue
• Dijkstra’s Shortest Path Algorithm – to find the shortest path
from a vertices to other vertices.
• Prim’s algorithm – find the minimum spanning tree.
• Data compression : It is used in Huffman codes which is used to
compresses data.
• Artificial Intelligence : A* Search Algorithm
• Network communication – to manage limited bandwidth
• Job Scheduling
22/01/2023 164