Data Structure

SEM III
Module 2

Prof Jeenal
Stacks

●Stack is a simple data structure that allows adding and removing elements in a
particular order.
●Every time an element is added, it goes on the top of the stack and the only
element that can be removed is the element that is at the top of the stack, just like
a pile of objects.

Prof Jeenal
Stacks

●Stack is an ordered list of similar data type.

●Stack is a LIFO (Last in First out) structure or we can say FILO (First in
Last out).
●push() function is used to insert new elements into the Stack and pop()
function is used to remove an element from the stack. Both insertion and
removal are allowed at only one end of Stack called Top.
●Stack is said to be in Overflow state when it is completely full and is
said to be in Underflow state if it is completely empty.

Prof Jeenal
Stacks

●Stack operations usually are performed for initialization, usage and,

de-initialization of the stack ADT.
●The most fundamental operations in the stack ADT include: push(),
pop(), peek(), isFull(), isEmpty(). These are all built-in operations to
carry out data manipulation and to check the status of the stack.
●Stack uses pointers that always point to the topmost element within
the stack, hence called as the top pointer.

Prof Jeenal
Stacks
Insertion: push()
●push() is an operation that inserts elements into the stack. The following is
an algorithm that describes the push() operation in a simpler way.
Algorithm
1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
3 − If the stack is not full, increments top to point next empty space.
4 − Adds data element to the stack location, where top is pointing.
5 − Returns success.

Prof Jeenal
Stacks
●Deletion: pop()
●pop() is a data manipulation operation which removes elements from the stack. The
following pseudo code describes the pop() operation in a simpler way.
●Algorithm
1 − Checks if the stack is empty.
2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.

Prof Jeenal
Stacks

peek()
●The peek() is an operation retrieves the topmost element within the
stack, without deleting it. This operation is used to check the status of
the stack with the help of the top pointer.
Algorithm
1. START
2. return the element at the top of the stack
3. END
Prof Jeenal
Stacks

isFull()
●isFull() operation checks whether the stack is full. This operation is
used to check the status of the stack with the help of top pointer.
Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack, the
stack is full. Return 1.
3. Otherwise, return 0.
4. END
Prof Jeenal
Stacks

isEmpty()
●The isEmpty() operation verifies whether the stack is empty. This
operation is used to check the status of the stack with the help of top
pointer.

Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END Prof Jeenal
Stacks
push(): When we embed a component in a stack then the activity is known as
a push. On the off chance that the stack is full, at that point the flood condition
happens.
pop(): When we erase a component from the stack, the activity is known as a
pop. In the event that the stack is unfilled implies that no component exists in
the stack, this state is known as an undercurrent state.
isEmpty(): It decides if the stack is unfilled or not.
isFull(): It decides if the stack is full or not.'
peek(): It restores the component at the given position.
count(): It restores the all out number of components accessible in a stack.
change(): It changes the component at the given position.
display(): It prints all the components accessible in the stack.
Prof Jeenal
Array implementation of Stack
#include <stdio.h>
#define MAX 5 // maximum size of stack
int stack[MAX];
int top = -1;
// Function to push an element
void push(int value) {
if(top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
top++;
stack[top] = value;
printf("%d pushed into stack.\n", value);
}
}
// Function to pop an element
void pop() {
if(top == -1) {
printf("Stack Underflow! Cannot pop.\n");
} else {
printf("%d popped from stack.\n", stack[top]);
top--;
}
} Prof Jeenal
Array implementation of Stack
// Function to display the stack
void display() {
int i;
if(top == -1) {
printf("Stack is empty.\n");
} else {
printf("Stack elements are:\n");
for(i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
}
}
int main() {
int choice, value;
while(1) {
printf("\n*** Stack Menu ***\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
Prof Jeenal
Array implementation of Stack
switch(choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Try again.\n");
}
}
}
Prof Jeenal
Applications of Stack-Well form-ness of Parenthesis
• Given a string s representing an expression containing various types of
brackets: {}, (), and [], the task is to determine whether the brackets in the
expression are balanced or not. A balanced expression is one where every
opening bracket has a corresponding closing bracket in the correct order.
Example:
Input: s = "[{()}]"
Output: true
Explanation: All the brackets are well-formed.
Input: s = "[()()]{}"
Output: true
Explanation: All the brackets are well-formed.
Input: s = "([]"
Output: false
Explanation: The expression is not balanced as there is a missing ')' at the end.
Input: s = "([{]})"
Output: false
Explanation: The expression is not balanced because there is a closing ']' before
the closing '}'.
Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis
● The idea is to put all the opening brackets in the stack.
Whenever you hit a closing bracket, search if the top of the stack
is the opening bracket of the same nature. If this holds then pop
the stack and continue the iteration. In the end if the stack is
empty, it means all brackets are balanced or well-formed.
Otherwise, they are not balanced.

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis
● Step-by-step approach:
● Declare a character stack (say temp).
● Now traverse the string s.

○ If the current character is an opening bracket ( '(' or '{' or '[' ) then push it to
stack.
○ If the current character is a closing bracket ( ')' or '}' or ']' ) and the closing
bracket matches with the opening bracket at the top of stack, then pop the
opening bracket. Else s is not balanced.
● After complete traversal, if some starting brackets are left in the stack then the
expression is not balanced, else balanced.

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Applications of Stack-Well form-ness of
Parenthesis

Prof Jeenal
Convert Infix expression to Postfix expression

●Infix expression: The expression of the form “a operator b” (a + b)

i.e., when an operator is in-between every pair of operands.
●Postfix expression: The expression of the form “a b operator” (ab+)
i.e., When every pair of operands is followed by an operator.
●
●Examples
●Input: A + B * C + D
Output: ABC*+D+
●Input: ((A + B) – C * (D / E)) + F
Output: AB+CDE/*-F+ Prof Jeenal
Convert Infix expression to Postfix expression

Why postfix representation of the expression

●The compiler scans the expression either from left to right or from
right to left.
Consider the expression: a + b * c + d
●The compiler first scans the expression to evaluate the expression b *
c, then again scans the expression to add a to it.
●The result is then added to d after another scan.

Prof Jeenal
Convert Infix expression to Postfix expression

●The repeated scanning makes it very inefficient. Infix expressions

are easily readable and solvable by humans whereas the computer
cannot differentiate the operators and parenthesis easily so, 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 using a stack.

Prof Jeenal
Convert Infix expression to Postfix expression

How to convert an Infix expression to a Postfix expression?

To convert infix expression to postfix expression, use the
stack data structure. Scan the infix expression from left to right.
Whenever we get an operand, add it to the postfix expression and if
we get an operator or parenthesis add it to the stack by maintaining
their precedence.

Prof Jeenal
Convert Infix expression to Postfix expression
Below are the steps to implement the above idea:
[Link] the infix expression from left to right.
[Link] the scanned character is an operand, put it in the postfix
expression.
[Link], do the following
●If the precedence and associativity of the scanned operator are
greater than the precedence and associativity of the operator in the
stack [or the stack is empty or the stack contains a ‘(‘ ], then push it
in the stack. [‘^‘ operator is right associative and other operators like
‘+‘,’–‘,’*‘ and ‘/‘ are left-associative].
Prof Jeenal
Convert Infix expression to Postfix expression

●Check especially for a condition when the operator at the top of the
stack and the scanned operator both are ‘^‘. In this condition, the
precedence of the scanned operator is higher due to its right
associativity. So it will be pushed into the operator stack.
● In all the other cases when the top of the operator stack is the same
as the scanned operator, then pop the operator from the stack
because of left associativity due to which the scanned operator
has less precedence.

Prof Jeenal
Convert Infix expression to Postfix expression
●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.)
[Link] the scanned character is a ‘(‘, push it to the stack.
[Link] the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is
encountered, and discard both the parenthesis.
[Link] steps 2-5 until the infix expression is scanned.
[Link] the scanning is over, Pop the stack and add the operators in the
postfix expression until it is not empty.
[Link], print the postfix expression.
Prof Jeenal
Convert Infix expression to Postfix expression
● Print operands as they arrive
● If stack is empty or contains a left parenthesis on top, push the incoming operator
onto the stack
● If incoming symbol is '(', push it onto stack
● If incoming symbol is ')', pop the stack & print the operators until left parenthesis is
found.
● If incoming symbol has higher precedence than the top of the stack, push it on the
stack.
● If incoming symbol has lower precedence than the top of the stack, pop & print the
top. Then test the incoming operator against the new top of the stack.
● If incoming operator has equal precedence with the top of the stack, use
associativity rule.
● At the end of the expression, pop & print all operators of stack.

● Associativity Note:
● If associativity is L to R (Left to Right), then pop & print the top of the stack &
then push the incoming operator.
● If associativity is R to L (Right to Left), then push the incoming operator.
Convert Infix expression to Postfix expression

Consider the infix expression exp = “a+b*c+d” and the infix expression is
scanned using the iterator i, which is initialized as i = 0.
●1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix
expression. Therefore, postfix = “a”.

Prof Jeenal
Convert Infix expression to Postfix expression

●2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the stack.
postfix = “a” and stack = {+}.

Prof Jeenal
Convert Infix expression to Postfix expression

●3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix
expression. postfix = “ab” and stack = {+}.

Prof Jeenal
Convert Infix expression to Postfix expression

●4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the stack.
postfix = “ab” and stack = {+, *}.

Prof Jeenal
Convert Infix expression to Postfix expression

●5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix
expression. postfix = “abc” and stack = {+, *}.

Prof Jeenal
Convert Infix expression to Postfix expression

●6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of
the stack has higher precedence. So pop until the stack becomes empty or the top
element has less precedence. ‘*’ is popped and added in postfix. So postfix =
“abc*” and stack = {+}.

Prof Jeenal
Convert Infix expression to Postfix expression
●Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix = “abc*+”.

Prof Jeenal
Convert Infix expression to Postfix expression
●Now stack is empty. So push ‘ + ’ in the stack. stack = {+}.

Prof Jeenal
Convert Infix expression to Postfix expression

●7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix
expression. postfix = “abc*+d”.

Prof Jeenal
Convert Infix expression to Postfix expression

●Final Step: Now no element is left. So empty the stack and add it in the postfix
expression. postfix = “abc*+d+”.

Prof Jeenal
Operator precedence rule

Prof Jeenal
Infix to Post fix
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Prof Jeenal
Infix to Post fix
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Prof Jeenal
Infix to Post fix
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Prof Jeenal
Infix to Post fix
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Prof Jeenal
Infix to Post fix
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Prof Jeenal
Evaluation of Postfix Expression

Postfix expression: The expression of the form “a b operator” (ab+) i.e.,

when a pair of operands is followed by an operator.
Input: str = “2 3 1 * + 9 -“
Output: -4
Explanation: If the expression is converted into an infix expression, it will
be
2 + (3 * 1) – 9 = 5 – 9 = -4.

Prof Jeenal
Evaluation of Postfix Expression

Evaluation of Postfix Expression using Stack:

Iterate the expression from left to right and keep on storing the operands into
a stack. Once an operator is received, pop the two topmost elements and
evaluate them and push the result in the stack again.

Prof Jeenal
Evaluation of Postfix Expression

Follow the steps mentioned below to evaluate postfix expression using stack:
● Create a stack to store operands (or values).
● Scan the given expression from left to right and do the following for
every scanned element.
● If the element is a number, push it into the stack.
● If the element is an operator, pop operands for the operator from the
stack. Evaluate the operator and push the result back to the stack.
● When the expression is ended, the number in the stack is the final answer.

Prof Jeenal
Evaluation of Postfix Expression

Consider the expression: exp = “2 3 1 * + 9 -“

● Scan 2, it’s a number, So push it into stack.
Stack contains ‘2’.

Prof Jeenal
Evaluation of Postfix Expression

● Scan 3, again a number, push it to stack, stack now contains ‘2 3’ (from

bottom to top)

Prof Jeenal
Evaluation of Postfix Expression

● Scan 1, again a number, push it to stack, stack now contains ‘2 3 1’

Prof Jeenal
Evaluation of Postfix Expression

● Scan *, it’s an operator. Pop two operands from stack, apply the * operator
on operands. We get 3*1 which results in 3. We push the result 3 to stack.
The stack now becomes ‘2 3’.

Prof Jeenal
Evaluation of Postfix Expression

● Scan +, it’s an operator. Pop two operands from stack, apply the + operator
on operands. We get 3 + 2 which results in 5. We push the result 5 to stack.
The stack now becomes ‘5’.

Prof Jeenal
Evaluation of Postfix Expression

● Scan 9, it’s a number. So we push it to the stack. The stack now becomes
‘5 9’.

Prof Jeenal
Evaluation of Postfix Expression

● Scan -, it’s an operator, pop two operands from stack, apply the – operator on
operands, we get 5 – 9 which results in -4. We push the result -4 to the stack.
The stack now becomes ‘-4’.

Prof Jeenal
Evaluation of Postfix Expression

● There are no more elements to scan, we return the top element from the stack
(which is the only element left in a stack).

So the result becomes -4.

Prof Jeenal
Recursion
● Recursion: The function calling itself is called recursion.

Recursive Stack Size:

● When a recursive function is invoked, its parameters are
stored in a data structure called activation records.
● Every time the recursive function is invoked, a new
activation record is generated and stored in the
memory.
● These activation records are stored in the special stack
called the recursive stack.
● These activation records are deleted when the function
execution is completed.
Prof Jeenal
Recursion
● So, when a recursive function is invoked, it
generates the activation records for different
values of the recursive function hence, extending
the recursion stack size.
● When the recursive function execution is
completed one by one its activation records get
deleted hence, contracting the recursive stack size.
The recursive stack size depends on the number of
activation records created and deleted.

Prof Jeenal
Recursion
#include <stdio.h>
using namespace std;

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

int main()
Prof Jeenal
{
Recursion
● For the above program. Firstly, the activation record for
main stack is generated and stored in the stack.

Prof Jeenal
Recursion
● In the above program, there is a recursive function fact
that has n as the local parameter. In the above example
program, n=2 is passed in the recursive function call.
● First Step: First, the function is invoked for n =2 and its
activation record are created in the recursive stack.

Prof Jeenal
Recursion
● 2nd Step: Then according to the recursive function, it is
invoked for n=1 and its activation record is created in the
recursive stack.

Prof Jeenal
Recursion
● 3rd Step: After the execution of the function for value n=1
as it is a base condition, its execution gets completed and
its activation record gets deleted.

Prof Jeenal
Recursion
● 4th step: Similarly, the function for value n=2(its previous
function) gets executed and its activation record gets
deleted. It comes out from the recursive function to the
main function.

Prof Jeenal
Recursion
● So, in the above example for recursive function fact and
value, n=2 recursive stack size excluding the main
function is 2. Hence, for value n recursive stack size is n.

Prof Jeenal
Queues
● Queue is an abstract data structure, somewhat similar to Stacks.
Unlike stacks, a queue is open at both its ends.
● One end is always used to insert data (enqueue) and the other is
used to remove data (dequeue).
● Queue follows First-In-First-Out methodology, i.e., the data
item stored first will be accessed first.

Prof Jeenal
Queues
● A Queue is a linear structure which follows a particular order in
which the operations are performed. The order is First In First
Out (FIFO).
● A good example of a queue is any queue of consumers for a
resource where the consumer that came first is served first.
● The difference between stacks and queues is in removing. In a
stack we remove the item the most recently added; in a queue,
we remove the item the least recently added.

Prof Jeenal
Queues

Prof Jeenal
OPERATIONS ON THE QUEUE

● Queue operations may involve initializing or defining the queue,

utilizing it, and then completely erasing it from the memory.
● Here we shall try to understand the basic operations associated with
queues −
enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.
● Few more functions are required to make the above-mentioned queue
operation [Link] are −
peek() − Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty
Prof Jeenal
Queues

In queue, we always dequeue (or access) data, pointed by front

pointer and while enqueing (or storing) data in the queue we take
help of rear pointer.

Prof Jeenal
Enqueue Operation
● Queues maintain two data pointers, front and rear. Therefore, its
operations are comparatively difficult to implement than that of stacks.
● The following steps should be taken to enqueue (insert) data into a queue
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next
empty space.
Step 4 − Add data element to the queue location, where the rear is
pointing.
Step 5 − return success.

Prof Jeenal
Dequeue Operation

Accessing data from the queue is a process of two tasks − access

the data where front is pointing and remove the data after access.
The
following steps are taken to perform dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is
pointing.
Step 4 − Increment front pointer to point to the next available data
element.
Step 5 − Return success. Prof Jeenal
● maxsize – Number of items allowed in the queue.
● empty() – Return True if the queue is empty, False otherwise.
● full() – Return True if there are maxsize items in the queue. If the queue was initialized with
maxsize=0 (the default), then full() never returns True.
● get() – Remove and return an item from the queue. If queue is empty, wait until an item is
available.
● get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
● put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available
before adding the item.
● put_nowait(item) – Put an item into the queue without blocking. If no free slot is
immediately available, raise QueueFull.
● qsize() – Return the number of items in the queue.

Prof Jeenal
Array implementation of Queue

● Like Stacks, Queues can also be represented in memory in two ways. Using
the contiguous memory like an array Using the non-contiguous memory
like a linked list Using the Contiguous Memory like an Array
● In this representation the Queue is implemented using the array. Variables
used in this case are
● QUEUE- the name of the array storing queue elements.
● FRONT- the index where the first element is stored in the array representing
the queue.
● REAR- the index where the last element is stored in array representing the
queue.
● MAX- defining that how many elements (maximum count) can be stored in
the array representing the queue.
Prof Jeenal
Array implementation of Queue

Prof Jeenal
Array implementation of Queue

● We can easily represent queue by using linear arrays. There are two
variables i.e. front and rear, that are implemented in the case of every
queue.
● Front and rear variables point to the position from where insertions and
deletions are performed in a queue.
● Initially, the value of front and rear is -1 which represents an empty
queue.
● Array representation of a queue containing 5 elements along with the
respective values of front and rear, is shown in the following figure.

Prof Jeenal
Array implementation of Queue
Array implementation of Queue
● The above figure shows the queue of characters forming the English
word "HELLO". Since, No deletion is performed in the queue till
now, therefore the value of front remains 0 .
● However, the value of rear increases by one every time an insertion is
performed in the queue.
● After inserting an element into the queue shown in the above figure,
the queue will look something like following. The value of rear will
become 5 while the value of front remains same.

Prof Jeenal
Queue

Prof Jeenal
Queue
After deleting an element, the value of front will increase from 0 to 1.
however, the queue will look something like following.

Prof Jeenal
Queue
#include <stdio.h>
#define SIZE 5 // Size of the queue
int queue[SIZE];
int front = -1, rear = -1;

// Function to insert an element (enqueue)

void enqueue(int value) {
if (rear == SIZE - 1) {
printf("Queue is full\n");
} else {
if (front == -1) // First element to insert
front = 0;
rear++;
queue[rear] = value;
printf("Inserted %d\n", value);
}
} Prof Jeenal
Queue
// Function to remove an element (dequeue)
void dequeue() {
if (front == -1 || front > rear) {
printf("Queue is empty\n");
} else {
printf("Deleted %d\n", queue[front]);
front++;
}
}
// Function to display the queue
void display() {
if (front == -1 || front > rear) {
printf("Queue is empty\n");
} else {
printf("Queue elements are: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
} Prof Jeenal
Queue
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
dequeue();
dequeue();
dequeue(); // To check underflow condition

return 0;
}
Prof Jeenal
Queue
o/p
Inserted 10
Inserted 20
Inserted 30
Queue elements are: 10 20 30
Deleted 10
Queue elements are: 20 30
Deleted 20
Deleted 30
Queue is empty
Types of queue

CIRCULAR QUEUE
A circular queue is the extended version of a regular queue where the last
element is connected to the first element. Thus forming a circle like structure.

Prof Jeenal
Circular queue
● The circular queue solves the major limitation of the normal queue. In
a normal queue, after a bit of insertion and deletion, there will be non
usable empty space.
● Here, indexes 0 and 1 can only be used after resetting the queue
(deletion of all elements). This reduces the actual size of the queue

Prof Jeenal
 Circular queue

How Circular Queue Works?

● Circular Queue works by the process of circular increment i.e. when we
try to increment the pointer and we reach the end of the queue, we start
from the beginning of the queue. Here, the circular increment is
performed by modulo division with the queue size.
That is,
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of
queue)

Prof Jeenal
Procedure on Circular Queue

● Front: It is utilized to get the front component from the Queue.

● Back: It is utilized to get the back component from the Queue.
● enQueue(value): This capacity is utilized to embed the new incentive
in the Queue. The new component is constantly embedded from the
backside.
● deQueue(): This capacity erases a component from the Queue. The
cancellation in a Queue consistently happens from the front end.

Prof Jeenal
Enqueue operation

● First, we will check whether the Queue is full or not.

● Initially the front and rear are set to -1. When we insert the first
element in a Queue, front and rear both are set to 0.
● When we insert a new element, the rear gets incremented, i.e.,
rear=rear+1.

Prof Jeenal
Enqueue operation
Scenarios for inserting an element:
There are two scenarios in which queue is not full:
● If rear != max - 1, then rear will be incremented to mod(maxsize) and the
new value will be inserted at the rear end of the queue.
● If front != 0 and rear = max - 1, it means that queue is not full, then set
the value of rear to 0 and insert the new element there.
There are two cases in which the element cannot be inserted:
● When front ==0 && rear = max-1, which means that front is at the first
position of the Queue and rear is at the last position of the Queue.
● front== rear + 1;
Prof Jeenal
Algorithm to insert an element in a circular queue

Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Prof Jeenal
Step 4: EXIT
Dequeue Operation
The means of dequeue activity are given underneath:
● To start with, we check if the Queue is vacant. In the event that the
queue is unfilled, we can't play out the dequeue activity.
● At the point when the component is erased, the estimation of front
gets decremented by 1.
● On the off chance that there is just a single component left which is to
be erased, at that point the front and back are reset to - 1.

Prof Jeenal
Algorithm to delete an element from the circular queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
SET FRONT = (FRONT + 1)% MAX
[END of IF]
Step 4: EXIT

Prof Jeenal
Code to insert an element in a circular queue
#include <stdio.h>
#define MAX 5 // maximum size of queue

int queue[MAX];
int front = -1, rear = -1;

// Function to insert an element (enqueue)

void enqueue(int value) {
if((front == 0 && rear == MAX - 1) || (rear + 1) % MAX == front) {
printf("Queue is full (Overflow).\n");
} else {
if(front == -1) { // first insertion
front = 0;
rear = 0;
} else {
rear = (rear + 1) % MAX;
}
queue[rear] = value;
printf("%d enqueued into circular queue.\n", value);
}
}
Code to delete an element in a circular queue

// Function to delete an element (dequeue)

void dequeue() {
if(front == -1) {
printf("Queue is empty (Underflow).\n");
} else {
printf("%d dequeued from circular queue.\n", queue[front]);
if(front == rear) {
// only one element was present
front = rear = -1;
} else {
front = (front + 1) % MAX;
}
}
}
Code to display an element in a circular queue

// Function to display the queue

void display() {
int i;
if(front == -1) {
printf("Queue is empty.\n");
} else {
printf("Circular Queue elements are:\n");
i = front;
while(1) {
printf("%d\n", queue[i]);
if(i == rear)
break;
i = (i + 1) % MAX;
}
}
}
Priority Queue

● A priority queue is a type of queue that arranges elements based on

their priority values.
● Elements with higher priority values are typically retrieved before
elements with lower priority values.
● In a priority queue, each element has a priority value associated with it.
When you add an element to the queue, it is inserted in a position based
on its priority value.
● For example, if you add an element with a high priority value to a
priority queue, it may be inserted near the front of the queue, while an
element with a low priority value may be inserted near the back.

Prof Jeenal
Priority Queue

● There are several ways to implement a priority queue, including

using an array, linked list, heap, or binary search tree.
● Each method has its own advantages and disadvantages, and the
best choice will depend on the specific needs of your application.
● Priority queues are often used in real-time systems, where the
order in which elements are processed can have significant
consequences.

Prof Jeenal
Properties of Priority Queue

● 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.

Prof Jeenal
How is Priority assigned to the elements in a Priority Queue?

● In a priority queue, generally, the value of an element is considered

for assigning the priority.
● For example, the element with the highest value is assigned the
highest priority and the element with the lowest value is assigned the
lowest priority.
● The reverse case can also be used i.e., the element with the lowest
value can be assigned the highest priority. Also, the priority can be
assigned according to our needs.

Prof Jeenal
Types of Priority Queue:

Prof Jeenal
Types of Priority Queue:

Ascending Order Priority Queue

● As the name suggests, in ascending order priority queue, the element
with a lower priority value is given a higher priority in the priority list.
● For example, if we have the following elements in a priority queue
arranged in ascending order like 4,6,8,9,10. Here, 4 is the smallest
number, therefore, it will get the highest priority in a priority queue and
so when we dequeue from this type of priority queue, 4 will remove from
the queue and dequeue returns 4.

Prof Jeenal
Types of Priority Queue:

Descending order Priority Queue

● The root node is the maximum element in a max heap, as you may
know. It will also remove the element with the highest priority first.
As a result, the root node is removed from the queue.
● This deletion leaves an empty space, which will be filled with fresh
insertions in the future.
● The heap invariant is then maintained by comparing the newly
inserted element to all other entries in the queue.

Prof Jeenal
Difference between Priority Queue and Normal Queue?

● There is no priority attached to elements in a queue, the rule of first-

in-first-out(FIFO) is implemented whereas, in a priority queue, the
elements have a priority. The elements with higher priority are served
first.
● Priority queue can be implemented using the following data
structures:
Arrays
Linked list
Heap data structure
Binary search tree
Prof Jeenal
Applications of Priority Queue:

● CPU Scheduling
● Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s
Minimum Spanning Tree, etc.
● Stack Implementation
● All queue applications where priority is involved.
● Data compression in Huffman code
● Event-driven simulation such as customers waiting in a queue.
● Finding Kth largest/smallest element.

Prof Jeenal
Advantages of Priority Queue:
● It helps to access the elements in a faster way. This is because elements in a priority
queue are ordered by priority, one can easily retrieve the highest priority element
without having to search through the entire queue.
● The ordering of elements in a Priority Queue is done dynamically. Elements in a
priority queue can have their priority values updated, which allows the queue to
dynamically reorder itself as priorities change.
● Efficient algorithms can be implemented. Priority queues are used in many
algorithms to improve their efficiency, such as Dijkstra’s algorithm for finding the
shortest path in a graph and the A* search algorithm for pathfinding.
● Included in real-time systems. This is because priority queues allow you to quickly
retrieve the highest priority element, they are often used in real-time systems where
time is of the essence.

Prof Jeenal
Disadvantages of Priority Queue:
● High complexity. Priority queues are more complex than simple data structures like
arrays and linked lists, and may be more difficult to implement and maintain.
● High consumption of memory. Storing the priority value for each element in a
priority queue can take up additional memory, which may be a concern in systems
with limited resources.
● It is not always the most efficient data structure. In some cases, other data structures
like heaps or binary search trees may be more efficient for certain operations, such as
finding the minimum or maximum element in the queue.
● At times it is less predictable:. This is because the order of elements in a priority
queue is determined by their priority values, the order in which elements are retrieved
may be less predictable than with other data structures like stacks or queues, which
follow a first-in, first-out (FIFO) or last-in, first-out (LIFO) order.

Prof Jeenal
Deque

● The deque represents Double Ended Queue.

● In the queue, the inclusion happens from one end while the erasure
happens from another end.
● The end at which the addition happens is known as the backside while
the end at which the erasure happens is known as front end.
● Deque is a direct information structure in which the inclusion and
cancellation tasks are performed from the two finishes. We can say that
deque is a summed up form of the line.
● Deque can be utilized both as stack and line as it permits the inclusion
and cancellation procedure on the two finishes.

Prof Jeenal
Deque

● In deque, the inclusion and cancellation activity can be performed

from one side. The stack adheres to the LIFO rule in which both the
addition and erasure can be performed distinctly from one end; in this
way, we reason that deque can be considered as a stack.

Prof Jeenal
Deque

● In deque, the addition can be performed toward one side, and the erasure
should be possible on another end. The queue adheres to the FIFO rule in
which the component is embedded toward one side and erased from
another end. Hence, we reason that the deque can likewise be
considered as the queue.

Prof Jeenal
Deque

● There are two types of Queues, Input-restricted queue, and output-

restricted queue.
● Information confined queue: The info limited queue implies that a few
limitations are applied to the inclusion. In info confined queue, the
addition is applied to one end while the erasure is applied from both the
closures.

Prof Jeenal
Deque

● Yield confined queue: The yield limited line implies that a few
limitations are applied to the erasure activity. In a yield limited queue,
the cancellation can be applied uniquely from one end, while the
inclusion is conceivable from the two finishes.

Prof Jeenal
Operations on Deque

The following are the operations applied on deque:

Insert at front
Delete from front
Insert at rear
Delete from rear

Prof Jeenal
We can perform two additional procedure on dequeue:

isFull(): This capacity restores a genuine worth if the stack is full; else,
it restores a bogus worth.
isEmpty(): This capacity restores a genuine worth if the stack is
vacant; else it restores a bogus worth.

Prof Jeenal
Insertion at the front end

● In this operation, the element is inserted from the front end of the queue.
Before implementing the operation, we first have to check whether the
queue is full or not.
● If the queue is not full, then the element can be inserted from the front
end by using the below conditions -
If the queue is empty, both rear and front are initialized with 0. Now, both
will point to the first element.
Otherwise, check the position of the front if the front is less than 1 (front < 1),
then reinitialize it by front = n - 1, i.e., the last index of the array.
Prof Jeenal
Insertion at the front end

Prof Jeenal
Insertion at the rear end

● In this operation, the element is inserted from the rear end of the queue. Before
implementing the operation, we first have to check again whether the queue is full or
not.
● If the queue is not full, then the element can be inserted from the rear end by using
the below conditions -
If the queue is empty, both rear and front are initialized with 0. Now, both will point to the
first element.

Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead of
increasing it by 1, we have to make it equal to 0.

Prof Jeenal
Insertion at the rear end

Prof Jeenal
Deletion at the front end

● First, check if deque is empty or not.

● If the deque is empty (front == -1), then we cannot perform deletion
operation. In this condition, we will simply print undeflow.
● If deque contains only 1 element (front = rear) , then only one deletion
operation can be performed. set front = -1 and rear = -1.
● Else if the front is at the last index ( front == n-1 ) , set front at starting
index of deque (front = 0).
● If none of the above case exists, just increment front by 1 (front = front
+ 1).

Prof Jeenal
Deletion at the front end

Prof Jeenal
Deletion at the rear end

● First, check if the deque is empty or not.

● If the deque is empty (front = -1), then deletion operation cannot be
performed and we will print underflow.
● If the deque has only 1 element( front==rear), we will set front = -1
and rear =-1.
● If the rear is at the starting index of deque (rear == 0) , then set rear
to last index (rear = n-1).
● If none of the above case exists, just decrement rear by 1 (rear =
rear-1).

Prof Jeenal
Deletion at the rear end

Prof Jeenal
Application of deque
● Deque can be used as both stack and queue, as it supports both
operations.
● Deque can be used as a palindrome checker means that if we read the
string from both ends, the string would be the same.
● Task scheduler: Deques can be used to implement a task scheduler that
keeps track of tasks to be executed. Tasks can be added to the back of the
deque, and the scheduler can remove tasks from the front of the deque
and execute them.
● Multi-level undo/redo functionality: Deques can be used to implement
undo and redo functionality in applications. Each time a user performs an
action, the current state of the application is pushed onto the deque.
When the user undoes an action, the front of the deque is popped, and the
previous state is restored. Prof Jeenal
Application of circular Queue
● Memory management: The circular queue provides memory management. As we
have already seen that in linear queue, the memory is not managed very efficiently.
But in case of a circular queue, the memory is managed efficiently by placing the
elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the
processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic light is one of the best
examples of the circular queue. Each light of traffic light gets ON one by one after
every j interval of time. Like red light gets ON for one minute then yellow light for
one minute and then green light. After green light, the red light gets ON.

Prof Jeenal
Applications of priority Queue
● Dijkstra’s Shortest Path Algorithm using priority queue: When the graph is stored
in the form of adjacency list or matrix, priority queue can be used to extract minimum
efficiently when implementing Dijkstra’s algorithm.
● Data compression : It is used in Huffman codes which is used to compresses data.
● Artificial Intelligence : A* Search Algorithm : The A* search algorithm finds the
shortest path between two vertices of a weighted graph, trying out the most promising
routes first.
● Operating systems: It is also used in Operating System for load balancing (load
balancing on server), interrupt handling.
● Robotics: Priority Queue is used in robotics to plan and execute tasks in a priority-
based manner.
● Medical systems: Priority queues are used in medical systems, such as triage
systems in emergency departments, to prioritize patients based on the urgency of their
condition.
Prof Jeenal