Data Structure and

Algorithm Chapter
Eight
Queues
Introduction

• Queue data structure is a collection of similar data items in which

insertion and deletion operations are performed based on FIFO
(First In First Out) principle.

• Queue is a linear data structure in which the insertion and

deletion operations are performed at two different ends.

• 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‘.
 Operations on a Queue
• The following operations are performed on a queue data
structure...
1. enQueue(value) - To insert an element into the queue
2. deQueue() - To delete an element from the queue
3. display() - To display the elements of the queue
Contd.

• Example

Operation Content of queue

Enqueue(B) B
Enqueue(C) B, C
Dequeue() C
Enqueue(G) C, G
Enqueue (F) C, G, F
Dequeue() G, F
Enqueue(A) G, F, A
Dequeue() F, A
Implementation of a Queue

• Queue data structure can be implemented in two ways. They are as

follows...

1. Using Array

2. Using Linked List

• When a queue is implemented using array, that queue

can
organize only limited number of elements.

• When a queue is implemented using linked list, that queue can

organize unlimited number of elements.
 Simple Array implementation of enqueue
and dequeue operations
• Queue implemented using array can store only fixed number of data
values.

• The implementation of queue data structure using array is very simple,

just define a one dimensional array of specific size and insert or delete
the values into that array by using FIFO principle with the help of
variables 'front' and 'rear'. Initially both 'front' and 'rear' are set to -1.

• Whenever, we want to insert a new value into the queue, increment

'rear' value by one and then insert at that position.

• Whenever we want to delete a value from the queue, then increment

'front' value by one and then display the value at 'front' position as
deleted element.
Contd.

enQueue(value) – Steps to insert a value into the queue

• The enQueue() function takes one value as parameter and inserts that value
into the queue. An integer variable (QUEUESIZE) that tells the total number
of data in the queue is used.

• Step 1: Check whether queue is FULL. (rear == SIZE-1)

• Step 2: If it is FULL, then display "Queue Overflow" and terminate the

function.

• Step 3: If it is NOT FULL, then increment rear value by one (rear++) and
set queue[rear] = value.

• Step 4: Increment QUEUESIZE value by one (QUEUESIZE ++)

• Step 5: If front == -1 , then increment front value by one (front ++)

Contd. enQueue(value) – Implementation

const int SIZE=100;

int FRONT =-1, REAR =-1;
int QUEUESIZE = 0;
int Num[SIZE];
void enQueue(int x)
{
if(REAR==SIZE-1)
cout<<“queue overflow”;
else if(REAR==-1 &&FRONT==-1)
{
REAR++;
FRONT++;
Num[REAR]=x;
QUEUESIZE++; }
else
{
FRONT++;
Num[FRONT]=x;
QUEUESIZE++;
}
}
Contd.

deQueue( ) – Steps to delete a value from the queue

• The deQueue() function does not take any value as

parameter
since the element is always deleted from front position.
• Step 1: Check whether queue is EMPTY. (rear == front
or
QUEUESIZE== 0)

• Step 2: If it is EMPITY, then display "Queue Underflow"

and terminate the function.

• Step 3: If it is NOT EMPITY, then increment

front value by one (front++) and display queue[front] as deleted
Contd. deQueue() – Implementation

int deQueue( )
{
int x;
if(FRONT=-1 && R EAR==-1)
cout<<"Queue Underflow";
else if(FRONT== REAR)
{
x=Num[FRONT];
FRONT=REAR=-1;
QUEUESIZE--;
}
else
{
x=Num[FRONT];
FRONT++;
QUEUESIZE--;

}
return x;
}
Contd.

display( ) – Steps to display elements of a queue

• Step 1: Check whether queue is EMPTY. == front or

(rear
QUEUESIZE== 0)
• Step 2: If it is EMPTY, then display "Queue Empty" and terminate
the function.

• Step 3: If it is NOT EMTY, then define an integer variable 'i' and set
'i = front'.

• Step 4: Display 'queue[i]' value and increment 'i' value by one (i++).
Repeat the same until 'i' value is equal to rear (i <= rear)
Contd.

display() – Implementation

void display()
{
if(FRONT==-1 && REAR==-1)
cout<<“\nQueue is Empty";

else
{
cout<<“\n Queue elements are ";
for(i = front; i<= rear ; i++)
cout<<“\t”<< Num[i];
}
}
 Circular Queue
Linear Array Implementation
• Queue 5 7 9 11 13 15

Front Rear

• After Four dequeue() 13 15

Rear
Front
• You can’t enqueue() anymore because your queue is full (rear== max
index). Index 0-3 are still empty though !

• solution CIRCULAR QUEUE

17 19 21 23 13 15

Rear Front
 Circular Queue
Linear Array Implementation

• Write the Implementation of Circular Queue using Linear Array.

• void enqueue(int x);

• int dequeue();

• void display();
 Linked List implementation of enqueue and
dequeue operations
• Queue using array is not suitable when we don't know the size of
data which we are going to use.

• A queue which is implemented using linked list can work for unlimited
number of values. That means, queue using linked list can work for
variable size of data (No need to fix the size at beginning of the
implementation).

• In linked list implementation of a queue, the last inserted node is always

pointed by 'rear' and the first node is always pointed by 'front'.

• Example
Contd.

enQueue(value) – Steps to insert an element into the queue

• We can use the following steps to insert a new node into the queue...

• Step 1: Create a newNode with given value and set 'newNode → next' to
NULL.

• Step 2: Check whether queue is Empty (rear == NULL)

• Step 3: If it is Empty then, set front = newNode and rear = newNode.

• Step 4: If it is Not Empty then,

set rear → next = newNode and rear =

newNode.
Contd.

enQueue(value) – Implementation

void enQueue(int value)

{
Node *temp;
temp = new Node;
temp >data = value;
temp -> next = NULL;
if(front == NULL && rear == NULL)
front = rear = temp;
else{
rear -> next = temp;
rear = temp;
}
cout<<"\nInsertion is Success!!!\n";
}
Contd.

deQueue( ) – Steps to delete a value from the queue

• We can use the following steps to delete a node from the queue...

• Step 1: Check whether queue is Empty (front == NULL).

• Step 2: If it is Empty, then display "Queue is Empty!!! Deletion is

not possible!!!" and terminate from the function

• Step 3: If it is Not Empty then, define a Node pointer 'temp' and set it
to 'front'.

• Step 4: Then set 'front = front → next' and delete 'temp' .

Contd.
deQueue( ) – Implementation

void deQueue()
{
if(front == NULL && rear==NULL)
cout<<"\nQueue is Empty!!!\n";
else{
Node *temp = front;
front = front -> next;
cout<<"\nDeleted element: \n",<<
temp->data;
delete temp;
}
}
Contd.

display( ) – Steps to display elements of a queue

• We can use the following steps to display the elements (nodes) of a
queue...
• Step 1: Check whether queue is Empty (front == NULL).

• Step 2: If it is Empty then, display 'Queue is Empty!!!' and terminate

the function.
• Step 3: If it is Not Empty then, define a Node pointer 'temp' and
initialize with front.
• Step 4: Display 'temp → data --->' and move it to the next node.
Repeat the same until 'temp' reaches to 'rear' (temp → next !=NULL
or temp !=NULL).
Contd.

display() – Implementation

void display()
{
if(front == NULL) cout<<"\
nQueue is Empty!!!\n"; else{
Node *temp = front;
while(temp != NULL)
{ cout<<temp->data<<"---
>"; temp = temp -> next;
}
cout<<"NULL";
}}
 Circular Queue
Linked List Implementation
• Write the Implementation of Circular Queue using Linked List.

• void enqueue(int x);

• int dequeue();

• void display();
Deque (pronounced as Deck)
• Deque is a Double Ended Queue

• Insertion and deletion can occur at either end

• Deque has the following basic operations
EnqueueFront – inserts data at the front of the list
DequeueFront – deletes data at the front of the list
EnqueueRear – inserts data at the end of the list
DequeueRear – deletes data at the end of the list

• Implementation is similar to that of queue.

• Deque is best implemented using doubly linked list

Priority Queue

• Priority Queue is a queue where each data has an associated key that
is provided at the time of insertion.

• Dequeue operation deletes data having highest priority in the list

• One of the previously used dequeue or enqueue operations has to

be modified

Example: Consider the following queue of persons where females

have
higher priority than males (gender is the key to give priority).
Demerging Queues
• It is the process of creating two or more queues from a single queue.
• used to give priority for some groups of data.
• Example: The following two queues can be created from the above
priority queue

Aster Meron Abebe Alemu Belay Kedir Yonas

Female Female Male Male Male Male Male

Algorithm:
create empty females and males queue
while (PriorityQueue is not empty)
{
Data=DequeuePriorityQueue(); // delete data at the front
if(gender of Data is Female)
EnqueueFemale(Data);
else
EnqueueMale(Data);
}
Merging Queues

• is the process of crating a priority queue from two or more queues.

• the ordinary dequeue implementation can be used to delete data in the
newly created priority queue.
• Example: The following two queues (female queue has higher priority
than the male queue ) can be merged to create a priority queue.

Aster Meron Abebe Alemu Belay Kedir Yonas

Female Female Male Male Male Male Male

Aster Meron Abebe Alemu Belay Kedir Yonas

Female Female Male Male Male Male Male
 Contd.
Algorithm:
create an empty queue
while(FemaleQueue is not empty)
EnqueuePriorityQueue(DequeueFemalesQueue());
while(MaleQueue is not empty)
EnqueuePriorityQueue(DequeueMalesQueue());
It is also possible to merge two or more priority queues.
Example: consider the following priority queues and suppose large
numbers represent high priorities.
ABC CDE DEF FGH HIJ BCD EFG GHI IJK JKL
52 41 35 16 12 47 32 13 10 7

Thus, the two queues can be merged to give the following queue

ABC BCD CDE DEF EFG FGH GHI HIJ IJK JKL
52 47 41 35 32 16 13 12 10 7
EX.

Write a C++ implementation of the above algorithms (Merging

and Demerging Queues)
Application of
Queues