1

PCET’S Pimpri Chinchwad University

Department of Computer Science and Engineering

Course Name : Data Structures and Algorithms
Course Code/Course Type : UBTCE201/PCC
SY. [Link]

Prepared By: Mr. Rahul Sonkamble

PIMPRI CHINCHWAD UNIVERSITY

 2

Course Objectives (CO):

• The objectives of Data Structures and Algorithms are:
1. To gain the knowledge about the concept of stack, queue and linked list.
2. To categorize the use of searching and sorting techniques.
3. Learn programming methodology for capability building.
4. Apply programming concepts to solve real life problem.
5. Implement Non-Linear Data Structures like Trees and graphs using programming
language

PIMPRI CHINCHWAD UNIVERSITY

 3

Course Learning Outcomes (CLO):

Students would be able to:
1. Apply and analyze use of stacks, queues and linked lists with their
applications.
2. Apply and analyze use of searching and sorting techniques with their
applications
3. Perform operations like searching, insertion, deletion, traversing mechanism
etc. on various data structures.
4. Apply advanced data structure strategies to solve real world problems.
5. Apply concepts learned in various domains like DBMS, compiler

PIMPRI CHINCHWAD UNIVERSITY

 UNIT- III
Stack and Queues
 5

Concept of stack
• Stack Data Structure is a linear data structure that follows LIFO
(Last In First Out) Principle , so the last element inserted is the
first to be popped out.

PIMPRI CHINCHWAD UNIVERSITY

 6

Basic Operations on Stack Data

Structure:
push() to insert an element into the stack

pop() to remove an element from the stack

top() Returns the top element of the stack.

isEmpty() returns true if stack is empty else false.

isFull() returns true if the stack is full else false.

PIMPRI CHINCHWAD UNIVERSITY

 7

Push Operation in Stack Data Structure:

Algorithm for Push Operation:

Before pushing the element to the stack, we check

if the stack is full .

If the stack is full (top == capacity-1) ,

then Stack Overflows and we cannot insert the
element to the stack.
Otherwise, we increment the value of top by
1 (top = top + 1) and the new value is inserted
at top position .
The elements can be pushed into the stack till we
reach the capacity of the stack.

PIMPRI CHINCHWAD UNIVERSITY

 8

Pop Operation in Stack Data Structure:

Algorithm for Pop Operation:

Before popping the element from the stack, we

check if the stack is empty .

If the stack is empty (top == -1), then Stack

Underflows and we cannot remove any element
from the stack.
Otherwise, we store the value at top, decrement
the value of top by 1 (top = top – 1) and return
the stored top value.

PIMPRI CHINCHWAD UNIVERSITY

 9

Top or Peek Operation in Stack Data

Structure
Algorithm for Top Operation:

Before returning the top element

from the stack, we check if the
stack is empty.
If the stack is empty (top == -1),
we simply print “Stack is empty”.

Otherwise, we return the element

stored at index = top .

PIMPRI CHINCHWAD UNIVERSITY

 10

isEmpty Operation in Stack Data Structure

Algorithm for isEmpty

Operation:
Check for the value
of top in stack.
If (top == -1) , then the
stack is empty so
return true .
Otherwise, the stack is not
empty so return false .
PIMPRI CHINCHWAD UNIVERSITY
 11

isFull Operation in Stack Data Structure

Algorithm for isFull

Operation:
Check for the value of top in
stack.
If (top == capacity-
1), then the stack is full so
return true.
Otherwise, the stack is not
full so return false.
PIMPRI CHINCHWAD UNIVERSITY
 12

Applications of Stack
Recursion

Infix to Postfix

Infix to prefix

Postfix Evaluation

Prefix Evaluation

PIMPRI CHINCHWAD UNIVERSITY

 13

Recursio
n

PIMPRI CHINCHWAD UNIVERSITY

 1. Scan all the symbols one by one from left to right
in the given Infix Expression.
2. If the reading symbol is an operand, then
immediately append it to the Postfix Expression.
3. If the reading symbol is left parenthesis ‘( ‘, then
Push it onto the Stack.
Algorithm 4. If the reading symbol is right parenthesis ‘)’, then
for infix to Pop all the contents of the stack until the
respective left parenthesis is popped and append
each popped symbol to Postfix Expression.
postfix 5. If the reading symbol is an operator (+, –, *, /),
then Push it onto the Stack. However, first, pop
the operators which are already on the stack that
have higher or equal precedence than the
current operator and append them to the postfix.
If an open parenthesis is there on top of the
stack then push the operator into the stack.
6. If the input is over, pop all the remaining symbols
from the stack and append them to the postfix.
Examples
a+b
• a+b+c
• a+b-c
• d/e*(a+b+c)
Algorithm for infix to prefix
• To convert an infix expression to a prefix expression, we can use
the stack data structure. The idea is as follows:

• Step 1: Reverse the infix expression. Note while reversing each ‘(‘
will become ‘)’ and each ‘)’ becomes ‘(‘.
• Step 2: Convert the reversed infix expression to “nearly” postfix
expression.
• While converting to postfix expression, instead of using pop
operation to pop operators with greater than or equal precedence,
here we will only pop the operators from stack that have greater
precedence.
• Step 3: Reverse the postfix expression.
• a+b

•1. Reversed string: b+a

•2. Postfix of b+a: ba+
•3. Reversed string of ba+: +ab
• a+b+c

•1. Reversed string: c+b+a

•2. Postfix of c+b+a: cb+a+
•3. Reversed string of cb+a+: +a+bc
• a+b-c

•1. Reversed string: c-b+a

•2. Postfix of c-b+a: cb-a+
•3. Reversed string of cb-a+: +a-bc
• d/e*(a+b+c)

•1. Reversed string: (c+b+a)*e/d

•2. Postfix of (c+b+a)*e/d: cb+a+e*d/
•3. Reversed string of cb+a+e*d/: /d*e+a+bc
Postfix Evaluation Algorithm
• 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.
Example
•231*+9-
Prefix Evaluation Algorithm
• Put a pointer P at the end of the string
• If character at P is an operand push it to Stack
• If the character at P is an operator pop two
elements from the Stack. Operate on these elements
according to the operator, and push the result
back to the Stack
• Decrement P by 1 and go to Step 2 as long as there
are characters left to be scanned in the expression.
• The Result is stored at the top of the Stack,
return it
• End
Example
Queue
• A Queue Data Structure is a
fundamental concept in computer
science used for storing and
managing data in a specific order.
• It follows the principle of “First
in, First out” (FIFO), where the
first element added to the queue
is the first one to be removed.
• Queues are commonly used in
various algorithms and
applications for their simplicity
and efficiency in managing data
flow.
Basic Operations of Queue Data
Structure
• Enqueue (Insert): Adds an element to the rear of the queue.
• Dequeue (Delete): Removes and returns the element from the
front of the queue.
• Peek: Returns the element at the front of the queue without
removing it.
• Empty: Checks if the queue is empty.
• Full: Checks if the queue is full.
enqueue()
• Inserts an element at the end of
the queue i.e. at the rear end.
• The following steps should be
taken to enqueue (insert) data
into a queue:
• Check if the queue is full.
• If the queue is full, return overflow
error and exit.
• If the queue is not full, increment
the rear pointer to point to the
next empty space.
• Add the data element to the
queue location, where the rear is
pointing.
• return success.
dequeue()
• This operation removes and
returns an element that is at the
front end of the queue.
• The following steps are taken to
perform the dequeue operation:
• Check if the queue is empty.
• If the queue is empty, return the
underflow error and exit.
• If the queue is not empty, access
the data where the front is
pointing.
• Increment the front pointer to
point to the next available data
element.
• The Return success.
front()
• This operation returns the element at the front end
without removing it.
The following steps are taken to perform the front
operation:
• If the queue is empty return the most minimum value.
• otherwise, return the front value.
rear()
This operation returns the element at the rear end
without removing it.
The following steps are taken to perform the rear
operation:
• If the queue is empty return the most minimum value.
• otherwise, return the rear value.
isEmpty()
This operation returns a boolean value that indicates
whether the queue is empty or not.
The following steps are taken to perform the Empty
operation:
• check if front value is equal to -1 or not, if yes then
return true means queue is empty.
• Otherwise return false, means queue is not empty
isFull()
This operation returns a boolean value that indicates
whether the queue is full or not.
The following steps are taken to perform the isFull()
operation:
• Check if front value is equal to zero and rear is equal to
the capacity of queue if yes then return true.
• otherwise return false
size()
This operation returns the size of the queue i.e. the total
number of elements it contains.

[Link]()
Parameters :
No parameters are passed
Returns :
Number of elements in the container
Array implementation of queue
To implement a queue using a simple array,
• create an array arr of size n and
• take two variables front and rear which are initialized as
0 and -1 respectively
• rear is the index up to which the elements are stored in
the array including the rear index itself. We mainly add
an item by incrementing it.
• front is the index of the first element of the array. We
mainly remove the element at this index in Dequeue
operation.
Class Structure
#include <iostream>
using namespace std;
class Queue {
private: int front, rear, size;
int arr[MAX];
public:
Queue()
{
front = -1;
rear = -1;
size = 0;
}
};
enqueue
void Insert()
{
int val;
if (rear == n - 1)
cout<<"Queue Overflow"<<endl;
else {
if (front == - 1)
front = 0;
cout<<"Insert the element in queue : "<<endl;

cin>>val;
rear++;
queue[rear] = val;
}
}
dequeue
void Delete()
{
if (front == - 1 || front > rear)
{
cout<<"Queue Underflow ";
return ;
}
else
{
cout<<"Element deleted from queue is : "<<
queue[front]<<endl;
front++;;
}
}
void Display()
{
if (front == - 1)
cout<<"Queue is empty"<<endl;
else {
cout<<"Queue elements are :";
for(inti=front;i<=rear;i++)
cout<<queue[i]<<“";
cout<<endl;
}
}
Circular Queue
• A Circular Queue is an extended
version of a normal queue where
the last element of the queue is
connected to the first element of
the queue forming a circle.
• The operations are performed based
on FIFO (First In First Out) principle.
It is also called ‘Ring Buffer’.
• 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.
Operations on Circular Queue
• Front: Get the front item from the queue.
• Rear: Get the last item from the queue.
• enQueue(value) This function is used to insert an element into the
circular queue. In a circular queue, the new element is always
inserted at the rear position.
• Check whether the queue is full – [i.e., the rear end is in just before the
front end in a circular manner].
• If it is full then display Queue is full.
• If the queue is not full then, insert an element at the end of the queue.
• deQueue() This function is used to delete an element from the
circular queue. In a circular queue, the element is always deleted
from the front position.
• Check whether the queue is Empty.
• If it is empty then display Queue is empty.
• If the queue is not empty, then get the last element and remove it from the queue.
 Implement Circular Queue using
Array
[Link] an array queue of size n, where n is the maximum number of
elements that the queue can hold.
[Link] two variables front and rear to -1.
[Link]: To enqueue an element x into the queue, do the following:
1. Increment rear by 1.
1. If rear is equal to n, set rear to 0.
2. If front is -1, set front to 0.
3. Set queue[rear] to x.
[Link]: To dequeue an element from the queue, do the following:
1. Check if the queue is empty by checking if front is -1.
1. If it is, return an error message indicating that the queue is empty.
2. Set x to queue[front].
3. If front is equal to rear, set front and rear to -1.
4. Otherwise, increment front by 1 and if front is equal to n, set front to 0.
5. Return x.
void insertCQ(int val)
{
if ((front == 0 && rear == n-1) || (front == rear+1))
{
cout<<"Queue Overflow \n";
return;
}
if (front == -1)
{
front = 0;
rear = 0;
} else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val ;
}
void deleteCQ() {
if (front == -1)
{
cout<<"Queue Underflow\n";
return ;
}
cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;
if (front == rear)
{
front = -1; rear = -1;
}
else
{
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
else {
if (front == -1){
while (f <= n - 1) {
cout<<"Queueisempty"<<endl;
cout<<cqueue[f]<<"";
f++;
return;
}
}
f = 0;
cout<<"Queue elements are :\n";
while (f <= r) {
if (f <= r) {
cout<<cqueue[f]<<"";
while (f <= r){
f++;
cout<<cqueue[f]<<"";
}
f++;
}
}
cout<<endl;
}
}
 Double Ended Queue (Deque)
• Deque or Double Ended Queue is a generalized
version of Queue data structure that allows insert
and delete at both ends.
Operations
on Deque
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.
function insertFront(deque[], front, rear, MAX_SIZE, x):
if (front == 0 and rear == MAX_SIZE - 1) or (front == rear
+ 1):
print "Deque is Full"
return

if front == -1: // Deque is empty

front = 0
rear = 0
else if front == 0:
front = MAX_SIZE - 1
else:
front = front - 1

deque[front] = x
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.
function insertRear(deque[], front, rear, MAX_SIZE, x):
if (front == 0 and rear == MAX_SIZE - 1) or (front ==
rear + 1):
print "Deque is Full"
return

if front == -1: // Deque is empty

front = 0
rear = 0
else if rear == MAX_SIZE - 1:
rear = 0
else:
rear = rear + 1

deque[rear] = x
Deletion at the front end
In this operation, the element is deleted from the front end of the
queue. Before implementing the operation, we first have to check
whether the queue is empty or not.
• If the queue is empty, i.e., front = -1, it is the underflow
condition, and we cannot perform the deletion. If the queue is
not full, then the element can be inserted from the front end by
using the below conditions
• If the deque has only one element, set rear = -1 and front = -1.
• Else if front is at end (that means front = size - 1), set front = 0.
• Else increment the front by 1, (i.e., front = front + 1).
function deleteFront(deque[], front, rear):
if front == -1:
print "Deque is Empty"
return NULL

item = deque[front]

if front == rear: // Only one element in deque

front = -1
rear = -1
else if front == MAX_SIZE - 1:
front = 0
else:
front = front + 1

return item
Deletion at the rear end
In this operation, the element is deleted from the rear
end of the queue. Before implementing the operation, we
first have to check whether the queue is empty or not.
• If the queue is empty, i.e., front = -1, it is the underflow
condition, and we cannot perform the deletion.
• If the deque has only one element, set rear = -1 and
front = -1.
• If rear = 0 (rear is at front), then set rear = n - 1.
• Else, decrement the rear by 1 (or, rear = rear -1).
function deleteRear(deque[], front, rear):
if front == -1:
print "Deque is Empty"
return NULL

item = deque[rear]

if front == rear: // Only one element in deque

front = -1
rear = -1
else if rear == 0:
rear = MAX_SIZE - 1
else:
rear = rear - 1

return item
 Check empty & Full
• Empty operation is performed to check whether the
deque is empty or not. If front = -1, it means that the
deque is empty.
• Full operation is performed to check whether the deque
is full or not. If front = rear + 1, or front = 0 and rear =
n - 1 it means that the deque is full.
function isEmpty(front): function isFull(front, rear, MAX_SIZE):
return front == -1 return (front == 0 and rear == MAX_SIZE - 1) or
(front == rear + 1)
Applications of queue
• Task scheduling in operating systems
• Data transfer in network communication
• Simulation of real-world systems (e.g., waiting lines)
• Priority queues for event processing queues for event
processing
Priority Queue
• A priority queue is an abstract data type that behaves
similarly to the normal queue except that each element
has some priority, i.e., the element with the highest
priority would come first in a priority queue. The priority
of the elements in a priority queue will determine the
order in which elements are removed from the priority
queue.
• The priority queue supports only comparable elements,
which means that the elements are either arranged in
an ascending or descending order.
Characteristics of a Priority queue
• Every element in a priority queue has some priority
associated with it.
• An element with the higher priority will be deleted
before the deletion of the lesser priority.
• If two elements in a priority queue have the same
priority, they will be arranged using the FIFO principle.
Example
• 1, 3, 4, 8, 14, 22
All the values are arranged in ascending order. Now, we will observe how the
priority queue will look after performing the following operations:
• poll(): This function will remove the highest priority element from the priority
queue. In the above priority queue, the '1' element has the highest priority, so
it will be removed from the priority queue.
• add(2): This function will insert '2' element in a priority queue. As 2 is the
smallest element among all the numbers so it will obtain the highest priority.
• poll(): It will remove '2' element from the priority queue as it has the highest
priority queue.
• add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8,
so it will obtain the third highest priority in a priority queue.
Types of Priority Queue
• Ascending order priority
queue: In ascending order
priority queue, a lower
priority number is given as a
higher priority in a priority.
For example, we take the
numbers from 1 to 5
arranged in an ascending
order like 1,2,3,4,5;
therefore, the smallest
number, i.e., 1 is given as
the highest priority in a
priority queue.
• Descending order
priority queue: In
descending order priority
queue, a higher priority
number is given as a higher
priority in a priority. For
example, we take the
numbers from 1 to 5
arranged in descending
order like 5, 4, 3, 2, 1;
therefore, the largest
number, i.e., 5 is given as
the highest priority in a
priority queue.