UNIT-4:

Queues: Introduction to queues: properties and operations,

implementing queues using arrays and linked lists, Circular Queues,
Applications of Queue – FCFS Scheduling, etc.
Deques: Introduction to deques (double-ended queues), Operations
on deques and their applications

QUEUE:
● Queue is a linear data structure in which
elements can be inserted from one end
called rear and deleted from other end
called front.

● The deletion or insertion of elements can

take place only at the front or rear end calleddequeue and enqueue respectively.
The first element that gets added into the queue is the first one to get removed
from the queue. Hence the queue is referred to as First-In-First-Out list (FIFO).

Basic Queue Operations in Queue Data Structure

 Below are the basic queue operations in data structure:

Operation Description
enqueue() Process of adding or storing an element to the end of the queue
dequeue() Process of removing or accessing an element from the front of the queue
peek() Used to get the element at the front of the queue without removing it
initialize() Creates an empty queue
isfull() Checks if the queue is full
isempty() Check if the queue is empty

let us understand in detail the two primary operations associated with Queue data structure –
enqueue and dequeue.

Enqueue Operation

Below are the steps to enqueue (insert) data into a queue

1. Check whether the queue is full or not.

2. If the queue is full – print the overflow error and exit the program.
 3. If the queue is not full – increment the rear pointer to point to the next empty space.
4. Else add the element in the position pointed by Rear.
5. Return success.

Algorithm for Enqueue Operation

procedure enqueue (data)

if queue is full

return overflow

endif

rear ← rear + 1

queue[rear] ← data

return true

end procedure

Dequeue Operation

Below are the steps to perform the dequeue operation

 Check whether the queue is full or not.

 If the queue is empty – print the underflow error and exit the program.
 If the queue is not empty – access the data where the front is pointing.
 Else increment the front pointer to point to the next available data element.
 Return success.

Algorithm for Dequeue Operation

procedure dequeue

if queue is empty

return underflow

end if

data = queue[front]

front ← front + 1

return true

end procedure
Queue applications in Data Structure

A queue data structure is generally used in scenarios where the FIFO approach (First In First
Out) has to be implemented. The following are some of the most common queue applications
in data structure:

 Managing requests on a single shared resource such as CPU scheduling and disk
scheduling
 Handling hardware or real-time systems interrupts
 Handling website traffic
 Routers and switches in networking
 Maintaining the playlist in media players

REPRESENTATION OF QUEUEs:
ARRAYs: Queues can be easily represented using linear arrays. Every queue has
front and rear variables that point to the position from where deletionsand insertions
can be done, respectively. The array representation of a queue isshown
Drawback: The array must be declared to have some fixed size. If we allocate space
for 50 elements in the queue and it hardly uses 20–25 locations, then half of the
space will be wasted.

LINKED LISTs:

In a linked queue, every element has two parts, one that stores the
data and another that stores the address of the next element.
The START pointer of the linked list is used as FRONT. Here, we
will also use another pointer called REAR, which will store the
address of the last element in the queue. All insertions will be done
 at the rear end and all the deletions will be done at the front end.
If FRONT = REAR = NULL, then it indicates that the queue is empty.

Implementation of Queue

A queue can be implemented in two ways:

 Sequential allocation: It can be implemented using an array. A queue implemented

using an array can organize only a limited number of elements.
 Linked list allocation: It can be implemented using a linked list. A queue
implemented using a linked list can organize unlimited elements.

Using Arrays:

ARRAYs: Queues can be easily represented using linear arrays. Every queue has front and
rear variables that point to the position from where deletions and insertions can be done,
respectively.
Let us consider a queue, which can hold maximum of five elements. Initially the queue is
empty. An element can beadded to the queue only at the rear end of the queue.

EnQueue:
Before adding an element in the queue, it is checked whether queue is full. If the queue is
full, then addition cannot take place. Otherwise, the element is added to the end of the list
at the rear end.If we are inserting first element into the queue thenchange front to 0 (Zero).

Steps for ENQUEUE operation

1. Check whether queue is FULL. (rear >= SIZE-1)
2. If it is FULL, then display an error message "Queue is FULL!!!
Insertion is not possible!!!" and terminate the function.
3. If it is NOT FULL, then increment rear value by one
(rear++) and set queue[rear] = value.

Algorithm

 Step 1: IF REAR = MAX - 1

Write OVERFLOW
Go to step
[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

DeQueue:

Now, delete an element 1. The element deleted is the element at the front of the
queue. So the status of the queue is:
When the last element delete 5. Theelement deleted at the front of the queue. So thestatus
of the queue is empty. So change the values of front and rear to -1 (front=rear= -1)
The dequeue operation deletes the element from the front of the queue. Before deleting
and element, it is checked if the queue is empty. If not the element pointed by front is
deleted from the queue and front is now made to point to the next element in the queue.

Steps for DEQUEUE operation

1. Check whether queue is EMPTY. (front == -1)
2. If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
3. If it is NOT EMPTY, then display queue[front] as deleted
element, increment the front value by one (front ++). If we are
deleting last element both front and rear are equal (front == rear), then
set both front and rear to '-1' (front = rear = -1).

Algorithm

 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

C program to implement queues using arrays

#include<stdio.h>

#include<stdlib.h>

#define maxsize 5

void insert();

void delete();

void display();

int front = -1, rear = -1;

int queue[maxsize];
void main ()

int choice;

while(choice != 4)

printf("\n*************************Main Menu***********************
******\n");

printf("\n===================================================
==============\n");

printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\

n");

printf("\nEnter your choice ?");

scanf("%d",&choice);

switch(choice)

case 1:

insert();

break;

case 2:

delete();

break;

case 3:

display();

break;

case 4:

exit(0);

break;
 default:

printf("\nEnter valid choice??\n");

void insert()

int item;

printf("\nEnter the element\n");

scanf("\n%d",&item);

if(rear == maxsize-1)

printf("\nOVERFLOW\n");

return;

if(front == -1 && rear == -1)

front = 0;

rear = 0;

else

rear = rear+1;

queue[rear] = item;
 printf("\nValue inserted ");

void delete()

int item;

if (front == -1 || front > rear)

printf("\nUNDERFLOW\n");

return;

else

item = queue[front];

if(front == rear)

front = -1;

rear = -1 ;

else

front = front + 1;

printf("\nvalue deleted ");

 }

void display()

int i;

if(rear == -1)

printf("\nEmpty queue\n");

else

{ printf("\nprinting values .....\n");

for(i=front;i<=rear;i++)

printf("\n%d\n",queue[i]);

Using Linked List:

 In a linked queue, each node of the queue consists of two parts i.e. data part
and the next part. Each element of the queue points to its immediate next
element in the memory.

struct node
{
int data;
 struct node *next;
};
 In the linked queue, there are two pointers maintained inthe 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. Initially

struct node *front = NULL, *rear = NULL;

Operation on Linked Queue: There are two basic operations which can be
implemented on the linked queues. The operations are Enqueue and Dequeue.

Enqueue function: Enqueue function will add the element at the end of the
linked list.

1. Declare a new node and allocate memory for it.

2. If front == NULL, make both front and rear points to the new node.

3. Otherwise, add the new node in rear->next (end of the list) and
make the new nodeas the rear node. i.e. rear = new node

Dequeue function: Dequeue function will remove the first element from the
queue.

1. Check whether the queue is empty or not

2. If it is the empty queue (front == NULL), We can't

dequeue the element.

3. Otherwise, Make the front node points to the next node. i.e
 front = front->next;

if front pointer becomes NULL, set the rear pointer also NULL. Free the front node's memory.

Example: Enqueue()

Dequeue()

Implementation of Queues using Linked Lists

#include <stdio.h>
#include <stdlib.h>
// Structure to create a node with data and the next pointer
struct node {
 int data;
struct node * next;
};
struct node * front = NULL;
struct node * rear = NULL;
// Enqueue() operation on a queue
void enqueue(int value) {
struct node * ptr;
ptr = (struct node * ) malloc(sizeof(struct node));
ptr -> data = value;
ptr -> next = NULL;
if ((front == NULL) && (rear == NULL)) {
front = rear = ptr;
} else {
rear -> next = ptr;
rear = ptr;
}
printf("Node is Inserted\n\n");
}
// Dequeue() operation on a queue
int dequeue() {
if (front == NULL) {
printf("\nUnderflow\n");
return -1;
} else {
struct node * temp = front;
int temp_data = front -> data;
front = front -> next;
free(temp);
return temp_data;
 }
}
// Display all elements of the queue
void display() {
struct node * temp;
if ((front == NULL) && (rear == NULL)) {
printf("\nQueue is Empty\n");
} else {
printf("The queue is \n");
temp = front;
while (temp) {
printf("%d--->", temp -> data);
temp = temp -> next;
}
printf("NULL\n\n");
}
}
int main() {
int choice, value;
printf("\nImplementation of Queue using Linked List\n");
while (choice != 4) {
printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("\nEnter the value to insert: ");
scanf("%d", &value);
enqueue(value);
break;
 case 2:
printf("Popped element is :%d\n", dequeue());
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong Choice\n");
}
}
return 0;
}

TYPES OF QUEUES:
A queue data structure can be classified into the following types:
1. Circular Queue 2. Deque 3. Priority Queue 4. Multiple Queue
CIRCULAR QUEUEs:
In a Linear queue, once the queue is completely full, it's not possible
to insert any more elements. When we dequeue any element to
remove it from the queue, we are actually moving the front of the
queue forward, but rear is still pointing to the last element of the
queue, we cannot insert new elements.
Circular Queue is also a linear data structure, which follows the
principle of FIFO(First In First Out), but instead of ending the queue
at the last position, it again starts from the first position after the last,
hence making the queue behave like a circular data structure.

Operations on Circular Queue: The following are the operations that can be
performed
o enQueue(value): This function is used to insert the new value in
 the Queue. The newelement is always inserted from the rear end.
o deQueue(): This function deletes an element from the Queue. The
deletion in a Queuealways takes place from the front end.

Enqueue operation: The steps of enqueue operation are given below:

o First, we will check whether the Queue is full or not.
o 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.
o From 2nd element onwards, When we insert a new element, the
rear gets incremented, i.e., rear=rear+1.

Queue is not full:

o If rear != max - 1, then rear will be incremented and the new value
will be inserted at therear end of the queue.
o If front != 0 and rear = max - 1, it means that queue is not full, then
set the value of rearto 0 and insert the new element there.

Queue is full:
o When front ==0 && rear = max-1, which means that front is at the
first position of theQueue and rear is at the last position of the
Queue.
o front== rear + 1;

Dequeue Operation: The steps of dequeue operation are given below:

o First, we check whether the Queue is empty or not. If the queue
is empty, we cannot perform the dequeue operation.
o When the element is deleted, the value of front gets decremented by 1.
o If there is only one element left which is to be deleted, then the front and
rear are reset -1.
Let's understand the enqueue and dequeue operation through the
diagrammatic representation.

Implementation of Circular Queues:

#include<stdio.h>
#define capacity 6
int queue[capacity];
int front = -1, rear = -1;
// Here we check if the Circular queue is full or not
int checkFull ()
{
if ((front == rear + 1) || (front == 0 && rear == capacity - 1))
{
return 1;
}
return 0;
}
// Here we check if the Circular queue is empty or not
int checkEmpty ()
{
if (front == -1)
{
return 1;
}
return 0;
}
// Addtion in the Circular Queue
void enqueue (int value)
{
if (checkFull ())
printf ("Overflow condition\n");
else
{
if (front == -1)
front = 0;
rear = (rear + 1) % capacity;
queue[rear] = value;
printf ("%d was enqueued to circular queue\n", value);
}
}
// Removal from the Circular Queue
int dequeue ()
{
int variable;
if (checkEmpty ())
{
printf ("Underflow condition\n");
return -1;
}
else
{
variable = queue[front];
if (front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % capacity;
}
printf ("%d was dequeued from circular queue\n", variable);
return 1;
}
}
// Display the queue
void print ()
{
int i;
if (checkEmpty ())
printf ("Nothing to dequeue\n");
else
{
printf ("\nThe queue looks like: \n");
for (i = front; i != rear; i = (i + 1) % capacity)
{
printf ("%d ", queue[i]);
}
printf ("%d \n\n", queue[i]);
}
}
int main ()
{
// Not possible as the Circular queue is empty
dequeue ();
enqueue (15);
enqueue (20);
enqueue (25);
enqueue (30);
enqueue (35);
print ();
dequeue ();
dequeue ();
print ();
enqueue (40);
enqueue (45);
enqueue (50);
enqueue (55); //Overflow condition
print ();
return 0;
}

Deque (or double-ended queue)

What is a queue?

A queue is a data structure in which whatever comes first will go out first, and it follows the
FIFO (First-In-First-Out) policy. Insertion in the queue is done from one end known as the
rear end or the tail, whereas the deletion is done from another end known as the front end
or the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where the person
who enters first in the queue gets the ticket first, and the person enters last in the queue gets
the ticket at last.
What is a Deque (or double-ended queue)

The deque stands for Double Ended Queue. Deque is a linear data structure where the
insertion and deletion operations are performed from both ends. We can say that deque is a
generalized version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does not
follow the FIFO rule. The representation of a deque is given as follows -

Types of deque

There are two types of deque –

 Input restricted queue

 Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion
can be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.
Operations performed on deque

There are the following operations that can be applied on a deque -

 Insertion at front
 Insertion at rear
 Deletion at front
 Deletion at rear

We can also perform peek operations in the deque along with the operations listed above.
Through peek operation, we can get the deque's front and rear elements of the deque. So, in
addition to the above operations, following operations are also supported in deque -

 Get the front item from the deque

 Get the rear item from the deque
 Check whether the deque is full or not
 Checks whether the deque is empty or not

Now, let's understand the operation performed on deque using an example.

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

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

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

Check empty

This operation is performed to check whether the deque is empty or not. If front = -1, it
means that the deque is empty.

Check full

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

The time complexity of all of the above operations of the deque is O(1), i.e., constant.

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

Implementation of deque

implementation of deque in C programming language.

Program:

#include <stdio.h>

#define size 5

int deque[size];

int f = -1, r = -1;

// insert_front function will insert the value from the front

void insert_front(int x)

if((f==0 && r==size-1) || (f==r+1))

printf("Overflow");

else if((f==-1) && (r==-1))

f=r=0;

deque[f]=x;

else if(f==0)

f=size-1;

deque[f]=x;

else

f=f-1;
 deque[f]=x;

// insert_rear function will insert the value from the rear

void insert_rear(int x)

if((f==0 && r==size-1) || (f==r+1))

printf("Overflow");

else if((f==-1) && (r==-1))

r=0;

deque[r]=x;

else if(r==size-1)

r=0;

deque[r]=x;

else

r++;

deque[r]=x;

}
 }

// display function prints all the value of deque.

void display()

int i=f;

printf("\nElements in a deque are: ");

while(i!=r)

printf("%d ",deque[i]);

i=(i+1)%size;

printf("%d",deque[r]);

// getfront function retrieves the first value of the deque.

void getfront()

if((f==-1) && (r==-1))

printf("Deque is empty");

else

printf("\nThe value of the element at front is: %d", deque[f]);

}
}

// getrear function retrieves the last value of the deque.

void getrear()

if((f==-1) && (r==-1))

printf("Deque is empty");

else

printf("\nThe value of the element at rear is %d", deque[r]);

// delete_front() function deletes the element from the front

void delete_front()

if((f==-1) && (r==-1))

printf("Deque is empty");

else if(f==r)

printf("\nThe deleted element is %d", deque[f]);

f=-1;

r=-1;
 }

else if(f==(size-1))

printf("\nThe deleted element is %d", deque[f]);

f=0;

} else

printf("\nThe deleted element is %d", deque[f]);

f=f+1;

// delete_rear() function deletes the element from the rear

void delete_rear()

if((f==-1) && (r==-1))

printf("Deque is empty");

else if(f==r)

printf("\nThe deleted element is %d", deque[r]);

f=-1;

r=-1;
 }

else if(r==0)

printf("\nThe deleted element is %d", deque[r]);

r=size-1;

else

printf("\nThe deleted element is %d", deque[r]);

r=r-1;

int main()

insert_front(20);

insert_front(10);

insert_rear(30);

insert_rear(50);

insert_rear(80);

display(); // Calling the display function to retrieve the values of deque

getfront(); // Retrieve the value at front-end

getrear(); // Retrieve the value at rear-end

delete_front();

delete_rear();

display(); // calling display function to retrieve values after deletion

 return 0;

Applications of Queue – FCFS Scheduling, etc (BFS- Breadth-first search)

1. First Come First Serve

we are going to learn an important concept in CPU Process Scheduling Algorithms. The
important concept name is First Come First Serve. This is the basic algorithm which every
student must learn to understand all the basics of CPU Process Scheduling Algorithms.

First Come First Serve paves the way for understanding of other algorithms. This algorithm
may have many disadvantages. But these disadvantages created very new and efficient
algorithms. So, it is our responsibility to learn about First Come First Serve CPU Process
Scheduling Algorithms.

Important Abbreviations

1. CPU - - - > Central Processing Unit

2. FCFS - - - > First Come First Serve
3. AT - - - > Arrival Time
4. BT - - - > Burst Time
5. WT - - - > Waiting Time
6. TAT - - - > Turn Around Time
7. CT - - - > Completion Time
8. FIFO - - - > First In First Out

First Come First Serve

First Come First Serve CPU Scheduling Algorithm shortly known as FCFS is the first
algorithm of CPU Process Scheduling Algorithm. In First Come First Serve Algorithm what
we do is to allow the process to execute in linear manner.

This means that whichever process enters process enters the ready queue first is executed
first. This shows that First Come First Serve Algorithm follows First In First Out (FIFO)
principle.

The First Come First Serve Algorithm can be executed in Pre Emptive and Non Pre Emptive
manner. Before, going into examples, let us understand what is Pre Emptive and Non Pre
Emptive Approach in CPU Process Scheduling.

Pre Emptive Approach

In this instance of Pre Emptive Process Scheduling, the OS allots the resources to a Process
for a predetermined period of time. The process transitions from running state to ready state
or from waiting state to ready state during resource allocation. This switching happens
because the CPU may assign other processes precedence and substitute the currently active
process for the higher priority process.

Non Pre Emptive Approach

In this case of Non Pre Emptive Process Scheduling, the resource cannot be withdrawn from
a process before the process has finished running. When a running process finishes and
transitions to the waiting state, resources are switched.

Example

S. No Process ID Process Name Arrival Time Burst Time

___ ______ _______ _______ _______

1 P1 A 0 9

2 P2 B 1 3

3 P3 C 1 2

4 P4 D 1 4

5 P5 E 2 3

6 P6 F 3 2

Non Pre Emptive Approach

Now, let us solve this problem with the help of the Scheduling Algorithm named First Come
First Serve in a Non Preemptive Approach.

Gantt chart for the above Example 1 is:

Turn Around Time = Completion Time - Arrival Time

Waiting Time = Turn Around Time - Burst Time

Solution to the Above Question Example 1

The Average Completion Time is:

Average CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6

Average CT = 97 / 6

Average CT = 16.16667

The Average Waiting Time is:

Average WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6

Average WT = 66 / 6

Average WT = 11

The Average Turn Around Time is:

Average TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6

Average TAT = 89 / 6

Average TAT = 14.83334

Pre Emptive Approach

Now, let us solve this problem with the help of the Scheduling Algorithm named First Come
First Serve in a Pre Emptive Approach.

In Pre Emptive Approach we search for the best process which is available

Gantt chart for the above Example 1 is:

2. Breadth-first search

Breadth-first search is a graph traversal algorithm that starts traversing the graph from the
root node and explores all the neighboring nodes. Then, it selects the nearest node and
explores all the unexplored nodes. While using BFS for traversal, any node in the graph can
be considered as the root node.

There are many ways to traverse the graph, but among them, BFS is the most commonly used
approach. It is a recursive algorithm to search all the vertices of a tree or graph data structure.
BFS puts every vertex of the graph into two categories - visited and non-visited. It selects a
single node in a graph and, after that, visits all the nodes adjacent to the selected node.

Algorithm

The steps involved in the BFS algorithm to explore a graph are given as follows -

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and
set their STATUS = 2
(waiting state)

[END OF LOOP]

Step 6: EXIT

Example of BFS algorithm

Now, let's understand the working of BFS algorithm by using an example. In the example
given below, there is a directed graph having 7 vertices.

In the above graph, minimum path 'P' can be found by using the BFS that will start from
Node A and end at Node E. The algorithm uses two queues, namely QUEUE1 and QUEUE2.
QUEUE1 holds all the nodes that are to be processed, while QUEUE2 holds all the nodes that
are processed and deleted from QUEUE1.

Now, let's start examining the graph starting from Node A.

Step 1 - First, add A to queue1 and NULL to queue2.

QUEUE1 = {A}

QUEUE2 = {NULL}

Step 2 - Now, delete node A from queue1 and add it into queue2. Insert all neighbors of node
A to queue1.

QUEUE1 = {B, D}

QUEUE2 = {A}

Step 3 - Now, delete node B from queue1 and add it into queue2. Insert all neighbors of node
B to queue1.

QUEUE1 = {D, C, F}

QUEUE2 = {A, B}
Step 4 - Now, delete node D from queue1 and add it into queue2. Insert all neighbors of node
D to queue1. The only neighbor of Node D is F since it is already inserted, so it will not be
inserted again.

QUEUE1 = {C, F}

QUEUE2 = {A, B, D}

Step 5 - Delete node C from queue1 and add it into queue2. Insert all neighbors of node C to
queue1.

 QUEUE1 = {F, E, G}
 QUEUE2 = {A, B, D, C}

Step 6 - Delete node F from queue1 and add it into queue2. Insert all neighbors of node F to
queue1. Since all the neighbors of node F are already present, we will not insert them again.

 QUEUE1 = {E, G}
 QUEUE2 = {A, B, D, C, F}

Step 6 - Delete node E from queue1. Since all of its neighbors have already been added, so
we will not insert them again. Now, all the nodes are visited, and the target node E is
encountered into queue2.

 QUEUE1 = {G}
 QUEUE2 = {A, B, D, C, F, E}