Chapter 7: QUEUES

What are we studying in this chapter?

Definition, array representation
Queue operations
Queue variants: Circular queue, priority queue, double ended queue
Circular queues using dynamic arrays, multiple queues
Programming examples - 7 hours

7.1 Definition and representation

This chapter deals with another important data structure namely queue. The term
queue is very familiar to us in day to day life, as we see people standing in a queue to
board the bus, or we see people standing in a queue near cinema hall to purchase the
tickets etc., In any situation a person who just arrives will stand at the end of the
queue and the person who is at the front of the queue is the first person to board the
bus or to get the ticket etc., The same concept of queue is used in the field of
computer science also. Now, let us see

Definition: A queue is a special type of data structure (an ordered collection of items)
where elements are inserted from one end and elements are deleted from the other
end. The end at which new elements are added is called the rear and the end from
which elements are deleted is called the front. Using this approach, the First element
Inserted is the First element to be deleted Out, and hence, queue is also called First In
First Out (FIFO) data structure.

Now, let us see types of queues? Since a queue elements are

stored in linear order, it can be implemented using arrays and linked lists. Based on
the method of insertion and deletion the queues are classified as shown below:

Linear queue (Ordinary queue)

Circular queue
Types of queues
Double ended queue (dequeue or qeque)
Priority queue
7.2 Queues
Once we know what is a queue and what are the different types of queues, the next
question is The queues can be represented using
following two data structures:
Arrays
Linked lists

In this chapter we concentrate on how each type of queue can be represented using
arrays. In the next chapter we see how a queue can be represented using linked lists.

7.2 Linear queue (Ordinary queue)

The linear queue or ordinary queue or simply a queue are one and the same. Now, let
us see

Definition: A queue (linear queue or ordinary queue) is a special type of data

structure (an ordered collection of items) where elements are inserted from one end
and elements are deleted from the other end. The end at which new elements are
added is called the rear and the end from which elements are deleted is called the
front. Using this approach, the First element Inserted is the First element to be deleted
Out, and hence, queue is also called First In First Out (FIFO) data structure.

For example, consider the queue shown below having the elements 10, 50 and 20:
q
10 50 20
0 1 2 3 4
front rear
The items are inserted into queue in the order 10, 50 and 20. The variable q is
used as an array to hold these elements
Item 10 is the first element inserted. So, the variable first is used as index to the
first element
Item 20 is the last element inserted. So, the variable rear is used as index to the
last element
Two more items can be inserted into above queue.
Now, let us see
The various operations that can be performed on stacks are shown below:
Insert (An element is inserted from the rear end)
Queue operations Delete (An element is deleted from the front end)
Display (Display the status of queue and queue contents)
 Data Structures using C - 7.3

7.2.1 Insert into queue

In a queue, an item is always inserted at the rear end. Now, let us see nsert

Design: The various steps to be followed while inserting the elements into queue are
shown below:

Step 1: Consider the queue shown below. Can we insert any element into the queue?
No, it is not possible because queue is full.
Observe that whenever rear value is QUEUE_SIZE = 5
q
not possible. The code for this can be
written as shown below: 10 20 30 40 50
0 1 2 3 4
if (rear == QUEUE_SIZE - 1) front rear
{
printf e is full\ Rear insertion not possible
return;
}

Step 2: If the above condition is not Item = 40

satisfied, it means the queue is not full
and an element can be inserted at the rear q
end. Observe that item has to be inserted 10 20 30
after 30 at position 3. That is, before 0 1 2 3 4
inserting an item, we have to increment front rear
rear by one. This can be achieved using
Insertion is possible
the statement:
rear = rear + 1;

Step 3: Now the item can be inserted at rear Item = 40

position. This can be achieved by copying item q
into q[rear] as shown below:
10 20 30 40
q[rear] = item; 0 1 2 3 4
front rear
7.4 Queues
Now, the complete function to insert an item into que can be written as shown below:

Example 7.1: Function to insert an item at the rear end of queue

Using global variables By passing parameters or int *q
void Insert_Rear() void Insert_Rear(int item, int *rear, int q[])
{ {
/* Check for overflow of queue */ /* Check for overflow of stack */
if (rear == QUE_SIZE 1) if (*rear == QUE_SIZE 1)
{ {
printf Queue overflow\ printf queue overflow\
return; return;
} }
/* Insert the item */ /* Insert the item */
rear = rear + 1; *rear = *rear + 1;
q[++rear] = item; q[*rear] = item; q[++(*rear)] = item;
q[rear] = item;
} }

7.2.2 Delete from queue

In a queue, an item is always removed from the front end. Now, let us see
delete an item from
Design: The various steps to be followed while deleting an element from queue are
shown below:

Step 1: Now, let us see

q q
10 20 30 10 20 30
0 1 2 3 4 0 1 2 3 4
front rear front
rear
3 items are present in queue only one item is present

front < rear front == rear

 Data Structures using C - 7.5
So, it is observed from above two figures that if front is less than or equal to rear
some elements are present. Otherwise, that is, if front is greater than rear then queue
is empty. We can check for empty queue using the following statement:
if (front > rear) return -1; // Que is empty

Step 2: When above condition fails, we can delete an item from front end of queue.
For this to happen, we have to access and return the first element and increment value
of front by 1 as shown below:
return q[front++];

Now, the complete function to delete an element from the front end of the queue can
be written as shown below:

Example 7.2: Function to delete an element from the front end of queue
or int *q
int Delete_Front() int Delete_Front(int *front,int *rear,int q[])
{ {
if (front > rear) return -1; if ( *front > *rear) return -1;

return q[front++]; return q[(*front)++];

} }

Note: The variables front, rear and Note: The variables front, rear and q have
q are global. So, they can be to be passed as parameters. Since the
accessed in all the functions. contents of front, rear and q are changed
they should be treated as pointers.
7.2.3 Display queue items
Now, let us see
Design: The various steps to be followed while displaying the elements of from
queue are shown below:

Step 1: Check for empty queue. This can be done using the following code:
if (front > rear)
{
printf \
return;
}
7.6 Queues
Step 2: If elements are present in queue control comes out of the above if statement.
Assume that the queue contains three elements as shown in figure.

20 25 10
-1 0 1 2 3 4

front rear
The contents of queue can be displayed as shown below:
Output
\ 0] ); 20
\ 1] ); 25
\ 2] ); 10

In general, we can use d\ [i] ); Note: i = front to rear

Now, the code takes the following form:

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

{
printf \
}

Now, the complete function can be written as shown below:

Example 7.3: Display queue elements

void Display() void Display(int front, int rear, int q[])

{ {
int i; int i;
/* If queue is empty */ /* If queue is empty */
if (front > rear) if (front > rear)
{ {
printf Queue is empty\ printf Queue is empty\
return; return;
} }
 Data Structures using C - 7.7

/* Display contents of queue */ /* Display contents of queue */

printf queue\ printf queue\
for (i = front; i <= rear; i++) for (i = front; i <= rear; i++)
{ {
printf \ q[i]); printf \ q[i]);
} }
} }

7.2.4 Queue implementation using arrays (static implementation of queues)

The complete C program to implement different operations on a queue is shown

below:

Example 7.4: C program to implement queue operations using global variables

#include <stdio.h>
#include <process.h>

#define QUE_SIZE 5

int choice, item, front, rear, q[10]; /* Global variables */

/* Include: Example 7.1: Function to insert an item (Using global variables) */

/* Include: Example 7.2: Function to delete an item (using global variables) */
/* Include: Example 7.3: To display contents of queue (global variables) */
void main()
{
/* Initially queue is empty */
front = 0; /* Front end of queue */
rear = -1; /* Rear end of queue*/

for (;;)
{
printf("1:Insert 2:Delete\n");
printf("3:Display 4:Exit\n");
printf("Enter the choice\n");
scanf("%d", &choice);
7.8 Queues
switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d", &item);
Insert_Rear();
break;
case 2:
item = Delete_Front();
if (item == -1)
\
else
\
break;
case 3:
Display();
break;
default:
exit(0);
}
}
}

Example 7.5: C program to implement queue operations by passing parameters

#include <stdio.h>
#include <process.h>

#define QUE_SIZE 5

/* Include: Example 7.1: Function to insert an integer (passing parameters) */

/* Include: Example 7.2: Function to delete an item (by passing parameters) */
/* Include: Example 7.3: Function to display the contents of queue */
 Data Structures using C - 7.9
void main()
{
int choice, item, front, rear, q[10];

/* Initially queue is empty */

front = 0; /* Front end of queue */
rear = -1; /* Rear end of queue*/

for (;;)
{
printf("1:Insert 2:Delete\n");
printf("3:Display 4:Exit\n");
printf("Enter the choice\n");
scanf("%d", &choice);
switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d", &item);
Insert_Rear(item, &rear, q);
break;
case 2:
item = Delete_Front(&front, &rear, q);
if (item == -1)
\
else
\

break;
case 3:
Display(front, rear, q);
break;
default:
exit(0);
}
}
}
7.10 Queues

7.3 Disadvantage of queue

Now, let us see of queue which is represented using an
Consider the queue shown below:
front rear
0 1 2 3 4
10 20 30 40 50

The above situation arises when 5 elements say 10, 20, 30, 40 and 50 are inserted and
then deleting first two items 10 and 20. Now, if we try to insert an item we get the
message

Note: In the above situation, rear insertion is denied even if space is available at the
front end. This is because in our function InsertQ() (see example 7.1) before inserting
an element, we test whether rear is equal to QUEUE_SIZE 1.
. This is a disadvantage. This disadvantage can be overcome
using two methods:
Method 1: Shift left: After deleting the element from the front, shift all remaining
elements to the left. This can be pictorially represented as shown below:

front rear front rear

0 1 2 3 4 0 1 2 3 4
10 20 30 40 50 20 30 40 50
After inserting 10, 20, 30, 40, 50 After deleting 10, shift remaining
elements to the left

front rear front rear

0 1 2 3 4 0 1 2 3 4
30 40 50 40 50

After deleting 20 shift After deleting 30 shift remaining items

remaining items towards left towards left

When an item is deleted, all the items towards right are moved to left by one position
and rear is decremented by 1. It is costly method and hence not recommended.
 Data Structures using C - 7.11
Method 2: Using circular representation: In a queue, we increment rear by 1 and
then insert the item as shown below:
rear = rear + 1;
q[rear] = item;
In circular representation, we increment rear by 1 as usual and then perform the
modulus operation using
rear = (rear + 1) % QUE_SIZE;
where QUE_SIZE is symbolic constant which represent maximum number of
elements in the queue and it can be defined as shown below:
#define QUE_SIZE 5
The significance of % operator is clear from the following example.
Insert: Assume QUE_SIZE is 5 and 5 elements are inserted into queue. The circular
representation along with linear array are shown below:

3 2
40 30 q 10 20 30 40 50
rear 4 50 20 1 0 1 2 3 4
10
0
front rear

front
Delete: In the above queue, item 10 is the first element. So, during deletion, the item
10 has to be deleted. This is achieved by incrementing front by 1 so that front
contains the index of the second element. This is pictorially represented as shown
below:
3 2
40 30 q 20 30 40 50
20 1 front 0 1 2 3 4
rear 4 50
front rear
0
Insert: Now if we want to insert an item 60, we have to increment rear by 1. In the
above figure, the value of rear is 4. If we increment rear by 1, its value will be 5. But,
we have assumed that queue is circular. So, after incrementing by 1, it should be 0
instead of 5. This is achieved by taking modulus as shown below:
rear = (rear + 1) % QUE_SIZE
7.12 Queues
After executing the above statement, the value of rear will be 0 so that item 60 can be
inserted at 0th position as shown below:

3 2
40 30 q 60 20 30 40 50
4 50 20 1 front 0 1 2 3 4
60
rear front
0
rear
Now, if we display the contents of queue, the output will be 20, 30, 40, 50, 60. This is
because 20 is the first element in the queue and 60 is the last element in the queue.

Note: As we increment rear by 1 using the statement:

rear = (rear + 1) % QUE_SIZE

we increment front by 1 each time an item is deleted using the statement:

front = (front + 1) % QUE_SIZE

7.4 Circular queue

Now, we shall see

Definition: In circular queue, the elements of a given queue can be stored efficiently
rear end of the queue is followed by the
front of queue. The pictorial representation of a circular queue and its equivalent
representation using an array are given side by side in figure below:

rear
q 10 20 30
3 2
30 0 1 2 3 4
4 20 1 front rear
10
0

front
 Data Structures using C - 7.13
This circular representation allows the entire array to store the elements without
shifting any data within the queue. This is an efficient way of implementing queues.

Empty queue: The circular representation and its equivalent array representation
when queue is empty is shown below:

3 2
q
-1 0 1 2 3 4
4 1
rear
front rear
front 0
When queue is empty, front = 0 and rear = -1. But, in circular queue, just before
index 0 we have index 4. So, instead of rear = -1, we can write rear = 4 also. Thus,
empty queue is represented by following initialization statements:

front = 0
rear = -1;

The above statements indicating empty queue can also be represented as shown
below:
front = 0
rear = 4; // rear = 4. In general, rear = QUE_SIZE 1

Example 7.6: Show the contents of circular queue after performing each of the
following
a) Empty queue
b) Insert 10
c) Insert 20 and 30
d) Insert 40 and 50
e) Insert 60
f) Delete two items
g) Insert 60 and 70
h) Insert 80

Solution: The queue and its representation after performing each of the above
operations can be written as shown below:

Step 1: Empty queue: Whenever front is 0 and rear is either -1 or QUE_SIZE 1,

queue is empty. An empty queue can be represented as shown below:
7.14 Queues

3 2
q
-1 0 1 2 3 4
4 1
rear
front rear
front 0

Step2: Inserting 10: After incrementing rear by 1, 10 is inserted as shown below:

3 2
q 10
0 1 2 3 4
4 1
10 front
rear
front 0 rear

Step 3: Inserting 20 and 30: Increment rear by 1 and insert 20. Again increment
rear by 1 and insert 30 as shown below:

rear
3 2
30 q 10 20 30
0 1 2 3 4
4 20 1
10 front rear
front 0

Step 4: Inserting 40 and 50: Increment rear by 1 and insert 40. Again increment
rear by 1 and insert 50 as shown below:

3 2
40 30 q 10 20 30 40 50
0 1 2 3 4
rear 4 50 20 1
10 front rear
0
front

Step 5: Inserting 60: Queue is full. It is not possible to insert any element into queue.
So, contents of queue have not been changed.
 Data Structures using C - 7.15

3 2 q
40 30 10 20 30 40 50
0 1 2 3 4
rear 4 50 20 1
10 front rear
front 0 Queue is full
Step 6: Delete: An item has to be deleted always from the front end. So, 10 is deleted
and contents of queue after deleting 10 is shown below:

3 2
40 30 q 20 30 40 50
0 1 2 3 4
rear 4 50 20 1 front
front rear
0
Step 7: Delete: An item has to be deleted always from the front end. So, 20 is deleted
and contents of queue after deleting 20 is shown below:

3 2
40 30 front q 30 40 50
0 1 2 3 4
1
rear 4 50
front rear
0
Step 8: Inserting 60: Incrementing rear by 1, its value is 0 (because of its circular
representation) and insert 60 at 0th location as shown below:

3 2
40 30 front q 60 30 40 50
0 1 2 3 4
4 50 1
60 rear front
0
rear
Step 9: Inserting 70: Increment rear by 1 and insert 70 as shown below:

3 2
40 30 front q 60 70 30 40 50
0 1 2 3 4
4 50 70 1
rear
60 rear front
0
7.16 Queues
Step 10: Inserting 80: Queue is full. It is not possible to insert any element into
queue. So, contents of queue has not been changed.

3 2
40 30 front q 60 70 30 40 50
0 1 2 3 4
4 50 70 1 rear
60 rear front
0
Queue is full

7.4.1 InsertQ()

Now, let us see insert function using arrays (static allocation

Design: The various steps to be followed while inserting the elements into queue are
shown below:

Step 1: Check for overflow: Before inserting, we check whether sufficient space is
available in the queue. This can be achieved using the following code:
if (count == QUEUE_SIZE)
{
printf \
return;
}

Step 2: Insert item: Increment rear by 1 and then take the mod operation and then
insert the item as shown below:
rear = (rear + 1) % QUEUE_SIZE;
q[rear] = item;

Step 3: Update count: As we insert an element into queue, we update count by 1.

This is achieved using the following statement:
count++;
Note: Observe that as we insert an item, the count is incremented by 1. This indicates
at any point of time, the variable count contains the total number of items present in
the queue.
 Data Structures using C - 7.17
Now, the complete function using global variables and by passing as parameters can
be written as shown below:

Example 7.7: InsertQ() using global variables and by passing parameters

void InsertQ(int item, int *rear, int *q,

void InsertQ() int *count)
{ {
/* Check for overflow of queue */ /* Check for overflow of stack */
if (count == QUE_SIZE) if (*count == QUE_SIZE)
{ {
printf Queue overflow\ printf queue overflow\
return; return;
} }

rear = (rear + 1) % QUE_SIZE; *rear = (*rear + 1) % QUE_SIZE;

q[rear] = item; q[*rear] = item;
count++; (*count)++;
} }

7.4.2 DeleteQ()
Now, let us see
The following steps are followed:
Step 1: Check for underflow: Before deleting an element from queue, we check
whether sufficient queue is empty or not. This can be achieved using the statement:

if (count == 0) return -1;

When above condition fails, it means queue is not empty and return the element
present at the front end of queue as shown in step2.
Step 2: Access the first item: This is achieved by accessing the element using index
front and then updating front by adding 1 to it and then take mod value. The
equivalent statements can be written as shown below:

item = q[front]; // access the item

front = (front + 1) % QUE_SIZE; // update front so that it contains
// index of next element.
7.18 Queues
Step 3: Update count: As we delete an element from queue, decrement count by 1.
This is achieved using the following statement:
count--;
Step 4: Return the element which was at the front end using the statement:
return item;
The function to delete an element using global variables/parameters is shown below:

Example 7.8: Function to delete an item from the front end of circular queue

int DeleteQ() int DeleteQ(int *front, int q[], int *count)

{ {
int item; int item;
if (count == 0 ) return -1; if ( *count == 0 ) return -1;

item = q[front]; item = q[*front];

front = (front + 1) % QUE_SIZE; *front = (*front + 1) % QUE_SIZE;
count -= 1; *count -= 1;

return item; return item;

} }

7.4.3 DisplayQ()
Now, let us see
The following steps are followed:

Step 1: Check for underflow: This is achieved using the following statement:
if (count == 0)
{
printf \
return;
}

Step 2: Display: Display starts from the front index. After displaying q[front] we
have to update front by 1 (That is by incrementing front by 1 and then taking the
modulus). The procedure is repeated for count number of times. This is because,
count contains the number of items in queue. The code for this can be written as:
 Data Structures using C - 7.19
for (i = 1, f = front; i < = count; i++)
{
printf \
f = (f + 1) % QUE_SIZE;
}

So, the complete function to display the contents of queue is shown below:
Example 7.9: Function to display the contents of circular queue
void display() void display(int front, int q[], int count)
{ {
int i, f; int i, f;
if ( count == 0 ) if ( count == 0 )
{ {
printf("Q is empty\n"); printf("Q is empty\n");
return; return;
} }
printf("Contents of queue is\n"); printf("Contents of queue is\n");
for ( i = 1, f = front; i <= count; i++) for ( i = 1, f = front; i <= count; i++)
{ {
printf("%d\n",q[f]); printf("%d\n",q[f]);
f = (f + 1) % QUE_SIZE; f = (f + 1) % QUE_SIZE;
} }
} }

The complete C program to implement circular queue by passing parameters is shown

below:

Example 7.10: C program to implement circular queue using global variables

#include <stdio.h>
#include <process.h>
#define QUE_SIZE 5
int item, front, rear, count, q[QUE_SIZE];

/* Include: Example 7.7: Function to insert an item at the rear end */

/* Include: Example 7.8: Function to delete an item from the front end */
/* Include: Example 7.9: Function to display the contents of circular queue */
7.20 Queues
void main()
{
int choice;

front = 0;
rear = -1;
count = 0; /* queue is empty */

for (;;)
{
printf("1:Insert 2:Delete\n");
printf("3:Display 4:Exit\n");
printf("Enter the choice\n");
scanf("%d",&choice);

switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d",&item);
InsertQ();
break;
case 2:
item = DeleteQ();
if (item == -1)
{
s empty\
break;
}
\
break;
case 3:
display();
break;
default:
exit(0);
}
}
}
 Data Structures using C - 7.21
The C program to implement circular queue by passing parameters is shown below:

Example 7.11: C program to implement circular queue by passing parameters

#include <stdio.h>
#include <process.h>

#define QUE_SIZE 5

/* Include: Example 7.7: Function to insert an item at the rear end */

/* Include: Example 7.8: Function to delete an item from the front end */

/* Include: Example 7.9: Function to display the contents of circular queue */

void main()
{
int choice, item, front, rear, count, q[QUE_SIZE];

front = 0;
rear = -1;
count = 0; /* queue is empty */

for (;;)
{
printf("1:Insert 2:Delete\n");
printf("3:Display 4:Exit\n");
printf("Enter the choice\n");
scanf("%d", &choice);

switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d",&item);

InsertQ(item, &rear, q, &count);

break;
case 2:
item = DeleteQ(&front, q, &count);
7.22 Queues
if (item == -1)
{
\
break;
}

\
break;
case 3:
display(front, q, count);
break;
default:
exit(0);
}
}
}

7.5 Double ended queue (Dequeue)

In this section, let us concentrate on another variant of queue called double ended
queue. In short, it is also called dequeuer or qeque. The deque is pronounced as deck.

Now, let us see and

various operations that can be performed on
Definition: A Dequeue is a special type of data structure in which insertions are done
from both ends and deletions are done at both ends. The operations that can be
performed on deques are shown below:
Insert an item from front end
Insert an item from rear end
Operations performed on dqueues Delete an item from front end
Delete an item from rear end
Display the contents of queue
Note: The three operations Insert_Rear, Delete_Front and display operations have
already been discussed in section 7.2. In this section, other two operations i.e., insert
an item at the front end and delete an item from the rear end are discussed.
 Data Structures using C - 7.23
7.5.1 Insert at the front end

Now, let us see insert front function using arrays (static allocation

Design: Before inserting any element, we should ask the question Where and how an
item has to be If we know the answer for this question we have the
insert front function ready. So, let us consider various situations shown in figure
below:

Case 1: Queue empty: When queue is empty, an item can be inserted at the front end
first by incrementing r by 1 and then insert an item.

-1 0 1 2 3 4 -1 0 1 2 3 4
10 20 30 40 10 10
r f f, r
Before insert After insert
(a) (b)

The equivalent code for this can be written as shown below:

/* Insert at front end if queue is empty: Case 1 (Fig a) */

if ( f == 0 && r == -1 )
{
q[++r] = item;
return;
}

Case 2: Some items are deleted: Consider the following situation where 10, 20 and
30 were inserted earlier and 10 and 20 have been deleted from the front end. Now,
there is only one item in queue. Here, an item can be inserted by decrementing the
front index f by 1 and then inserting an item at that position as shown below:

0 1 2 3 4 0 1 2 3 4
10 20 30 40 10 20 30 40
f, r f r
After deleting 2 items After inserting 20
(a) (b)
7.24 Queues
The equivalent code for this can be written as shown below:
/* Insert at the front end if possible: Case 2 (Fig a)*/
if ( f != 0 )
{
q[--f] = item;
return;
}
Case 3: Some items are inserted (not deleted): Consider the following situation
where 10, 20 and 30 were inserted into queue.

0 1 2 3 4
10 20 30 40
f r
queue after inserting 10, 20, 30
Now, Observe that, in the above situation it is not possible to insert an any item at the
front end and we should display the appropriate message. This is achieved using the
following statement:
printf \
The complete C function to insert an item at the front end is shown below:

Example 7.12: Function front insert(replacing f by front, r by rear ( global variables)

void Insert_Front()
{
if ( front == 0 && rear == -1 ) /* Case 1: Insert when Q empty */
{
q[++rear] = item;
return;
}
if ( front != 0 ) /* Case 2: Insert when items are present */
{
q[--front] = item;
return;
}
printf("Front insertion not possible\n");
} /* Case 3: Insertion not possible at front end */
 Data Structures using C - 7.25
By passing parameters, the above function can be written as shown below:

Example 7.13: Function to insert an item at the front end (by passing parameters)
void Insert_Front(int item, int q[], int *front, int *rear)
{
if ( *front == 0 && *rear == -1 ) /* Case 1: Insert when Q empty */
{
q[++(*rear)] = item;
return;
}
if ( *front != 0 ) /* Case 2: Insert when items are present */
{
q[--(*front)] = item;
return;
}
printf("Front insertion not possible\n");
} /* Case 3: Insertion not possible at front end */

7.5.2 Delete from the rear end

Now, let us see delete rear operation using arrays (static

Consider the following situation where 3 items are already
inserted into queue and one item is deleted.

0 1 2 3 4 0 1 2 3 4
10 20 30 40 10 20 40
f r f r
After inserting 3 items After deleting from rear
(a) (b)

Design: Item has to be deleted from rear end. This can be achieved by accessing the
rear element q[r] as shown below:
\ /* Access and print rear item */
and then decrementing r by one as shown below:
r = r 1; /* Update position of rear item */
7.26 Queues
The above two statements can also be written using single statement as shown below:

\ --]); /* Access and update queue */

Observe that as each item is deleted, the index variable r is decremented so that it
always contains the position of last item (see figure). Finally, when the queue is
empty the value of f will be greater than r. Once f is greater than r, it is not possible
to delete any item because queue is empty. This condition is called underflow of
queue. Hence, the above statement has to be executed only if queue is not empty and
the code to delete an item from rear end of queue can be written as shown below:

Example 7.14: Function to delete an item from the rear end (Using global variables)

int Delete_Rear()
{
int item;

if (front > rear) return 1; /* Queue is empty */

item = q[rear--];

if (front > rear) front = 0, rear = -1; /* Reset to initial state of empty queue */

return item;
}
The above function can be written by passing the parameters as shown below:

Example 7.15: Function delete rear (replace f by front, r by rear (passing parameters)

int Delete_Rear(int q[],int *front, int *rear)

{
int item;

if (*front > *rear) return 1; /* Queue is empty */

item = q[(*rear)--]; /* Delete item from rear end */

if (*front > *rear) *front = 0, *rear = -1; /* Reset to empty queue */

return item;
}
 Data Structures using C - 7.27

The complete C code to implement double-ended queue using global variables is

shown below

Example 7.16: C program to implement double-ended queue using global variables

#include <stdio.h>
#include <process.h>
#define QUE_SIZE 5
int choice, item, front, rear, q[10]; /* Global variables */

/* Include: Example 7.1: Function to insert an item at the rear end */

/* Include: Example 7.2: Function to delete an item at the front end */
/* Include: Example 7.12: Function to insert an item at the front end */
/* Include: Example 7.14: Function to delete an item at the rear end */
/* Include: Example 7.3: To display contents of queue */
void main()
{
/* Initially queue is empty */
front = 0; /* Front end of queue */
rear = -1; /* Rear end of queue*/
for (;;)
{
printf("1:Insert_front 2:Insert_rear\n");
printf("3:Delete_front 4:Delete_rear\n");
printf("5:Display 6:Exit\n");
printf("Enter the choice\n");
scanf("%d", &choice);

switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d",&item);
Insert_Front();
break;
7.28 Queues
case 2:
printf("Enter the item to be inserted\n");
scanf("%d",&item);
Insert_Rear();
break;
case 3:
item = Delete_Front();
if (item == -1)
\
else
m deleted from front = %d\

break;
case 4:
item = Delete_Rear();
if (item == -1)
\
else
\

break;

case 5:
Display();
break;

default:
exit(0);
}
}
}

Example 7.17: C program to implement dequeue by passing parameters.

#include <stdio.h>
#include <process.h>

#define QUE_SIZE 5
/* Include: Example 7.1: Function to insert an item at the rear end */
 Data Structures using C - 7.29
/* Include: Example 7.2: Function to delete an item at the front end */
/* Include: Example 7.13: Function to insert an item at the front end */
/* Include: Example 7.15: Function to delete an item at the rear end */
/* Include: Example 7.3: To display contents of queue */
void main()
{
int choice, item, front, rear, q[10];
front = 0;
rear = -1;

for (;;)
{
printf("1:Insert_front 2:Insert_rear\n");
printf("3:Delete_front 4:Delete_rear\n");
printf("5:Display 6:Exit\n");
printf("Enter the choice\n");
scanf("%d",&choice);
switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d",&item);
Insert_Front(item, q, &front, &rear);
break;
case 2:
printf("Enter the item to be inserted\n");
scanf("%d",&item);
Insert_Rear(item, &rear, q);
break;
case 3:
item = Delete_Front(&front, &rear, q);
7.30 Queues
if (item == -1)
printf \
else
printf \

break;

case 4:
item = Delete_Rear(q, &front, &rear);

if (item == -1)
printf \
else
printf \

break;

case 5:
Display(front, rear, q);
break;

default:
exit(0);
}
}
}

7.6 Priority queue

In this section, let us see another variation of queue called priority queue. Let us see

Definition: A queue in which we are able to insert items or remove items from any
position based on some priority is often referred to as a priority queue. Always an
element with highest priority is processed before processing any of the lower priority
elements. If the elements in the queue are of same priority, then the element, which is
inserted first into the queue, is processed. Priority queues are used in job scheduling
algorithms in the design of operating system where the jobs with highest priorities
have to be processed first.
The priority queues are classified into two groups:
 Data Structures using C - 7.31
Ascending priority queue: In an ascending priority queue elements can be inserted
in any order. But, while deleting an element from the queue, only the smallest
element is removed first.

Descending priority queue: In descending priority also elements can be inserted in

any order. But, while deleting an element from the queue, only the largest element
is deleted first.

Now, let us see There are various methods of

implementing priority queues using arrays.

Design 1: One of the methods is to implement an ascending priority queue where

elements can be inserted in any fashion and only the smallest element is removed.
Here, an element is inserted from the rear end of the queue but an element with least
value should be deleted. After deleting the smallest number, store a very large value
in that location, indicating the absence of an item. The variable count can be used to
keep track of number of elements in the array. The three functions useful for this
purpose are:
insert_rear() - which inserts the item at the end of the queue.
remove_small() which returns the smallest item from the queue and at the
same time store maximum number in that location indicating an item has been
deleted.
display() which displays the contents of queue.

It is left as an exercise to the reader to implement this. Now, let us implement priority
queues using another technique.

Design 2: The second technique is to insert the items based on the priority. In this
technique, we assume the item to be inserted itself denotes the priority. So, the items
with least value can be considered as the items with highest priority and items with
highest value can be considered as the items with least priority. So, to implement
priority queue, we insert the elements into queue in such a way that they are always
ordered in increasing order. With this technique the highest priority elements are at
the front end of the queue and lowest priority elements are at the rear end of queue.
Hence, while deleting an item, always delete from the front end so that highest
priority element is deleted first. The function to insert an item at the appropriate place
is shown below:

Note: To insert an element into appropriate place so that elements are arranged in
ascending order, we use the insertion sort technique.