Chapter 6: Stacks

I What are we studying in this chapter? I

• Definition and examples
• Representing and implementing stacks in C
• Definition, conversion and evaluation of expressions -7 hours

6.1 Introduction
The digital computers are electronic devices that can transmit, store and manipulate
information. Information is obtained from data and it is the result of processing,
manipulatingand organizing the data.The various types of data that are processed by
the computer are numeric or character (address, names etc.,) in nature. In the coming
chapters, we discuss extensively on various types of data structures. First, we shall see
"What is data structure? What are the various types of data structures?"

Definition:A data structureis a method of storing data in a computer so that it can be

usedefficiently. The Data Structures mainly deal with:
•• The study of how the data is organized in the memory
• How efficiently the data can be stored in the memory
• How efficiently the data can be retrieved and manipulated, and
• The possible ways in which different data items are logically related.
Thedata structures can be classified as shown below:
Integer
Floating point
Primitive -~I--~ Character
/'

Double
Pointers
Data Arrays
structures
Stacks
Linear
Queues
Non Linked lists
primitive

Non-linear ---c: Trees

Graphs
6.2 Q Stacks

Now, let us see "What are primitive data structures?"

Definition: The Primitive Data structures are data structures that can be manipulated
directly by machine instructions.
For example, the integers, floating point numbers (real), characters, pointers
etc., are some of the primitive data structures. In C language, the different primitive
data structures are defined using the data types such as int, float, char and double.

Now, let us see "What are non-primitive data structures?"

Definition: The Non-primitive data structures are data structures that cannot be
manipulated directly by machine instructions.
For example, arrays, structures, stacks, queues, linked lists, files etc., are some
of the non- primitive data structures. The non-primitive data structures are classified
into linear data structures and non-linear data structures. The data structures that show
the relationship of logical adjacency between the elements are called linear data
structures. Otherwise, they are called non-linear data structures .
•
6.2 Stacks

We have seen that, normally all the plates in a hotel/canteen are placed one above the
other. The plates are inserted from the top only. If a plate is required, the top most
plate is selected. This process of inserting the plates at the top and removing the plates
from the top is called stacking of plates. Let us see how stacks are used in the field of
computer science. Before proceeding further, let us see "What is a stack? What are
the various operations that can be performed on stacks?"
!

Definition: A stack 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 same
end. \'fhis position from where elements are inserted and from where elements are
deleted is called top of the stack. losing this approach, the last element inserted is the
first element to be deleted out, and hence, stack is also called Last In First Out
(LIFO) data structure. The various operations that can be performed on stacks are
shown below:

Stack operations -E Push (Inserting an element on the top of stack)

Pop (Deleting an element from the top of stack)
display (Display contents of stack)
 ~ Systematic Approach to Data Structures using C - 6.3

6.2.1 Push operation

Let us see "What is push operation?"

Definition: Inserting an element into the stack is called Only one item
is inserted at a time and item has to be inserted only from top of the stack.

Example 6.2.1.1: Stack contents after inserting 4 items 30, 20, 25 and 10 one after
the other with a STACK SIZE 4.

STACK SIZE = 4

~3

~El ~El~~~
oEl ~0m3 000
to
~t 2 25
3~
1
o
20
30
2
1
o
top
~ -I S S S s s
Empty stack insert 30 insert 20 insert 25 insert 10

Figure 6.1 Sequence of insertion operations

When items are being inserted, we may get stack overflow. Now, let us see "What is
stack overflow?"

Definition: When elements are being inserted, there is a possibility of stack being
full. Once the stack is full, it is not possible to insert any element. Trying to insert an
element, even when the stack is full results in.overflow of stack.
For example, consider the stack shown in figure 6.1 with STACK_SIZE 4. We
can insert at the most four elements. After inserting 30, 20, 25 and 10 there is no
space to insert any item. Then we say .that stack is full. This condition is called
overflow of stack.

Now, let us see "How to implement push operation using arrays (static allocation
technique)?"

Design: Before inserting any element, we should ask the question "Where and how
the item has to be inserted?" If we know the answer for this question we have the
6.4 Q Stacks

push function ready. So, let us consider the situation where two elements 30 end 20
are already inserted into the stack as shown in figure 6.2.a. with top = 1.

STACK_SIZE = 4 STACK_SIZE = 4 STACK_SIZE =4 STACK_SIZE =4

3 ~3
~2 ~2
t 3~ 25 2
to 2
~ 3~
1 20 1 1 20 1
o 30 0 o 30 0
-1 S -1 S -1 S -1 S

(a) (b) (c) (d)

Fig. 6.2 Showing the design of push operation

\ .
Suppose, we have to insert an element say item. Now, let us ask "Where this item has
to be inserted?" We know that it has to be inserted at top = 2. For this to happen, we
have to increment top.by 1 (Fig. 6.2.b). This is achieved using the statement:

top = top + 1; 1* Increment top by 1 *1

Then we ask "How item has to be inserted at top position?" This is achieved by
copying item to s[top] (Fig 6.2.c) using the following statement:

s[top] = item; 1* Insert into stack *1

But, as we insert an item, we must ask "When we can not insert item into the stack?"
We can not insert any item when top has already reached STACK_SIZE - 1(Fig.
6.2.d) . In such situation, we have to display appropriate message as shown below:

1* Check for overflow of stack *1

if (top = STACK_SIZE -1)·
{
printf("Stack overflow\n");
return;
l }

Here, STACK - SIZE should be #defined . (preprocessor directive) and is called

symbolic constant. If the above condition fails, the item has to be inserted. Now, the
complete C function for this can be written as shown below:
 Q Systematic Approach to Data Structures using C - 6.5

Example 6.2.1.2: C function to insert an integer itemIl.Ising global variables)

void puslu)
{
/* Check for overflow of stack */
if (top = STACK_SIZE -1)
{
printf("Stack overflow\n");
return;
}

top = top + 1;
/* Increment top by 1 */ }
I
s[++top] = item;
s[top] = item; /* Insert into stack */

Note: The array s, the variable top and the variable item are global variables and
should be declared before all the functions. As far as possible let us avoid the usage of
global variables in this book.

Let us re-write the above code by passing parameters. It is clear from the above code
that as the item is inserted, the contents of the stack identified by s and the index top
pointing to topmost element are changed and so they should be passed as parameters
(pass by reference) as shown below:

Example 6.2.1.3:, C function to insert an integer item (by passing parameters)

void push(int item, int *top, int sm
{
/* Check for overflow of stack */
if (*top = STACK_SIZE - 1)
{
printf("Stack overflow\n");
return;
}

*top = *top + 1; /* Increment top by 1 */ } s[++(*top)] = item;

s[*top] = item; /* Insert into stack */
6.6 Q Stacks

The following function inserts a character item into the stack.

Example 6.2.1.4: C function to insert a character item (by passing parameters)

void push(char item, int *top, char s[])

{
1* Check for overflow of stack *1
if (*top = STACK_SIZE -1)
{
printf("Stack overflow\n");
return;
}

*top = *top + 1; 1* Increment top by 1 *it

s[*top] = item; 1* Insert into stack *1 f s[++(*top)] = item;
}

Note: By comparing functions shown in 6.2.1.3 and 6.2.1.4 note that body of the
function has not been changed. But, the type of formal parameters changes.

6.2.2 Pop operation

Let us see "What is pop operation?"
Definition: Deleting an element from the stack is called pop operation. Only one item
can be deleted at a time and item has to be deleted only from top of the stack.

Example 6.2.2.1: Performing pop operation when stack already contains 30, 20, 25,
and 10.

to
3 3 3 3
2 2 2
1 ~ ~ 20 1
top 1
o o 30 ~O 30 top 0
1 -I -I -I -+-1
Stack full After After After
deleting 25 deleting 20 deleting 30
(stack empty)
Figure 6.3 Sequence of Deletion operations
 Q Systematic Approach to Data Structures using C - 6.7
The items can be deleted one by one as shown in figure 6.3.The contents of stack and
the top which contains the position of topmost elements are also shown. When items
are being deleted, we may get stack underflow. Now, let us see "What is stack
underflow?"

Definition: When elements are being deleted, there is a possibility of stack being
empty. When stack is empty, it is not possible to delete any item. Trying to delete an
element from an empty stack results in stack underflow.
For example, in the figure 6.3, after deleting 10, 25, 20 and 30 there are no
elements in the stack and stack is empty. Deleting an element from the stack results in
stack underflow.

Now, let us see "How to implement pop operation using arrays (static allocation
technique)?"

Design: Let us delete an item from the top of the stack. This can be achieved by
accessing the top element s[top] as shown below:

item_deleted = s[top]; /* A~cess the topmost item */

and then decrementing top by one as shown below:

top = top - 1; /* Update the position of topmost item */

The above two statements can also be written using single statement as shown below:

item = s[top--]; Note: item = s[--top]; is wrong.

Each time, the item is deleted, top is decremented and finally, when the stack is
empty the value of top will be -1 and so, it is not possible to delete any item from the
stack. Hence, the above statement has to be executed only if stack is not empty and
the code to delete an item from stack can be written as shown below:

Example 6.2.2.1: C function to delete an integer item (using global variables)

int popt)
{
int item_deleted;

if (top == -1) return 0; /* Stack underflow? */

6.8 Q Stacks

item_deleted = s[top--]; 1* Access the item and delete *1

return item_deleted; 1* Send the item deleted to the calling function */

}

Now, let us write the above function without using global variables and by passing
appropriate parameters. We know that to access the top item, we need the index top
and the stack s. So, we have to pass top and s as the parameters. As the value of top
changes every time the item is deleted, top can be used as a pointer variable. The
complete C function (by passing parameters) is shown below:

Example 6.2.2.2: C function to delete an integer item (by passing parameters)

int poptint *top, int s[])
{
int item_deleted; 1* To hold the top most item of stack *1
1* Stack underflow? *1
if (*top = -1) return 0;
1* Obtain the top most element and change the position of top item *1
item_deleted = s[(*top )--];
1* Send the item deleted to the calling function */
return item_deleted;
}

The following function shows how to delete a character item from the stack.
! ~.'

Example 6.2.2.3: C function to delete a character item (by passing parameters)

char pop(int *top, char s[])
{
char iternjleleted; 1* Holds the top most item of sack *1
1* Stack underflow? *1
if (*top = -1) return 0;
1* Obtain the top most element and change the position of top item *1
item_deleted = s[(*top)--]; .
1* Send the item deleted to the calling function */
return item_deleted;
}
 Q Systematic Approach to Data Structures using C - 6.9

6.2.3 Display stack items

In the display procedure, if the stack already has some items, all those items are
displayed one after the other. If no items are present, the appropriate error message is
displayed. Let us design the display function.

Design: Assume that the stack contains three elements as shown below:

~~
1
o
-1 S
Usually, the contents of the stack are displayed from the bottom to top. So, first item
to be displayed is 30, next item to be displayed is 20 and final item to be displayed is
25. This can be achieved using the following statements:

Design I, Output
printf("%d\n", illlQ[1);); I 30
printf("%d\n", 20
printf("%d\n", 2); I 25

In generai, we can use printf("%d\n",

!
s [i] );
I
I Note: i = 0 to 2 ( i.e., top).

ote: Please note how the value of i change from 0 to top. Now, the code takes the
following form:

for (i = 0; i <= top; i++)

{
printf("%d\n", s[i]);
}

But, the above statement should not be executed when stack is empty i.e., when top
takes the value .,...1. So, the above code can be modified to include this error condition
andcan be written as shown below:
6.10 Q Stacks

Example 6.2.3.1: C function to display the contents of stack (using global variables)
void displayt)
{
int i;
1* If stack is empty *1
if (top = -1)
{
printf("Stack is empty\n");
return;
}
1* Display contents of stack *1
printf("Contents of the stack\n");
for (i = 0; i <= top; i++)
{
printf("%d\n", s[i]);
}
}

By passing parameters, the function above function can be written as shown below:
Example 6.2.3.2: C function to display contents of the stack (by passing parameters)
void display(int top, int sm
{
int i;
1* Is stack empty *1
if(top = -1)
{
prtntf(t'Stack is empty\n");
return;
}
1* Display contents of stack*l·
printf("Contents of the stack\n");
1 for (i = 0; i <= top; i++)
{
printf("%d\n", s[i]);
}
}
 ~ Systematic Approach to Data Structures using C - 6.11

6.2.4 Stack implementation using arrays (static implementation of stacks)

In the previous sections we have seen how the stacks can be implemented using
global variables and by passing parameters. The complete program to perform
operations such as push, pop and display using global variables is shown below:

Example 6.2.9: C Program to implement stack using arrays (Using global variables)

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

#define STACK SIZE 5

1* Global variables */

int top; /* index to hold the position of the top most item */
int s[10]; /* Holds the stack items */
int item; /* Item to be inserted into the stack */

1* Include function push shown in example 6.2.1.2 */

1* Include function pop shown in example 6.2.2.1 */

1* Include function display shown in example 6.2.3.1 */

void mainO
{
int item; /* Item to be inserted */
int item_deleted; /* Item to be deleted from the stack */
int choice; /* user choice for push, pop and display */

top = -1; /* Indicates stack is empty */

for (;;)
{
prtntf(" 1:Push 2:Pop\nlt);
printf(1t3 :Display 4:Exit\nIt);
printf'(vlinter the choice'n");
scallf(lt%dlt ,&choice);
6.12 Q Stacks

Continued .....

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

case 2:
item __deleted = popt);

if (item_deleted = 0)
printf("Stack is empty\n");
else
printf("ltem deleted = %d\n",item_deleted);

break;

case 3:
displayt);
break;

default:
exit(O);
}
}
}

The program to perform operations such as push, pop and display by passing
parameters is shown below:

Example 6.2.10: C Program to implement stack using arrays (by Passing parameters)
.1

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

#define STACK SIZE 5

.
 Q Systematic Approach to Data Structures using C - 6.13
Continued ....

1* Include function push shown in example 6.2.1.3 */

1* Include function pop shown in example 6.2.2.2 */
1* Include function display shown in example 6.2.3.2 */
void maint)
{
int top; /* Points to top of the stack */
int s[10]; /* Holds the stack items */
int item; /* Item to be inserted or deleted item */
int item_deleted; /* Item to be deleted from the stack */
int choice; /* user choice for push, pop and display */
top = -1; /* Indicates stack is empty to start with */
for (;;)
{
prfntf("! :Push 2:Pop\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); .
push(item,&top,s );
break;

case 2:
item_deleted = pop(&top,s);

if (itemdeleted = 0)
printf("Stack is empty\n");
else
printf("Item deleted = %d\n",item_deleted);

break;
6.14 Q Stacks

Continued .....

case 3:
display(top,s);
break;
default:
exit(O);
}
}
}

6.3 Applications of stack

Once we define a stack and how stack is implemented in C, let us concentrate on

"What are the applications of stack?" The various applications in which stacks are
used are:
• Conversion of expressions: When we write mathematical expressions in a
program, we use infix expressions. These expressions will be converted into
equivalent machine instructions by the compiler using stacks. Using stacks we can
efficiently convert the expressions from infix to postfix, infix to prefix, postfix to
infix, postfix to prefix, postfix to infix and postfix to prefix.

• Evaluation of expressions: An arithmetic expression represented in the form of

either postfix or prefix can be easily evaluated.

• Recursion: A function which calls itself is called recursive function. Some of the
problems such as tower of Hanoi, problems involving tree manipulations etc., can
be implemented very efficiently using recursion. It is. a very important facility
available in variety of programming languages such as C, c++ etc.,

• Other applications: There are so many other applications where stacks can be
used: For example, to find whether the string is a palindrome, to check whether a
given expression is valid or not and so on.
1
Now, we shall discuss these applications in detail in the subsequent sections.

6.4 Conversion of Expressions

First, let us see "What is an expression? What are the various types of expressions?"
 Chapter 8: Queues
I What are we studying in this chapter? I
• Queue and its sequential representation
• Definition and various types of queues .
• Implementation of ordinary queue using arrays
• Implementation of Circular queue using arrays
• Implementation of Double ended queue using arrays
• Implementation of Priority queue using arrays
• Implementation of ordinary queue using structures
• Implementation of Circular queue using structures
• Implementation of Double ended queue using structures
• Implementation of Priority queue using structures
- 4 hours

8.1Introduction
This chapter deals with an 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.
For example, if a number of print jobs are given from various computers to
take printout from a network printer, all the print jobs are diverted to a queue and are
stored in the order of their arrivaL So, a new print job will be at the end of queue and
so, the print job, 'which is at the front of the queue, gets the services of the network
printer. There are so many such instances, where the queue concept is used in the
field of computer science. First, let us see "What is a queue? What are the various
operations that can be performed on queues?

Definition(A queue is defined as a special type of data structure where elements are
inserted from one end and elements are deleted from the other end. The end from
where the elements are inserted is called rear end and the end from where elements
are deleted is called front end. Since the first item inserted is the first item to be
8.2 Q Queues

deleted from queue, queue is also called Eirst !n first Out (FIFO) data structure. In
a queue, elements are always inserted from the rear end and elements are deleted from
the front end. The pictorial representation of the queue is shown in tigure 8.1.

f r
o 1 2 3 4
delete +--1 10 20 I 30 J~ I +-- Insert
Front end Rear end

Fig 8.1 Pictorial representation of queue

Here, the front end is denoted by f and rear end is denoted by r. So, the first item
inserted into the queue is 10, the second item inserted is 20 and the last item inserted
is 30. Any new element to be inserted into this queue has to be inserted towards right
of 30 and that item will be the last element in the queue. The first item to be deleted
from the queue is the item, which is at the front of the queue i.e., 10. So, it is very
clear from the operations performed on queues that First item Inserted is the First
item to be deleted Out from the queue. So, queue is also called First In First Out
(FIFO) data structure.
This data structure is useful in time-sharing systems where many user jobs will
be waiting in the system queue for processing. These jobs may request the services of
CPU, main memory or external devices such as printer etc. All these jobs will be
given a fixed time for processing and are allowed to use one after the other. This is
the case of an ordinary queue where priority is same for all the jobs and whichever
job is submitted first, that job will be processed. Now, let us see "What are the
various operations that can be performed on queues?" The various primitive
operations that can be performed on queues are

Operations on queues -f Insert an item into queue

Delete an item from queue
Display the contents of queue

8.2 Different types of queues

Note: Sometimes, based on the preference, jobs may have to be processed. Such a
queue where a job is processed based on the priority is called a priority queue. Now,
let us see "What are the different types of queues?"
 Q Systematic Approach to Data Structures using C - 8.3

The different types of queues are shown below:

Queue (Ordinary queue)

Circular queue
Types of queues
Double ended queue
Priority queue

8.2.1 Queue (Ordinary queue)

Let us see "What is a queue?"

Definition: A queue is defined as a special type of data structure where elements are
inserted from one end and elements are deleted from the other end. The end from
where the elements are inserted is called rear end and the end from where elements
are deleted is called front end. Since the first item inserted is the first item to be
deleted from queue, queue is also called .first !n ,Eirst Out (FIFO) data structure.

Here, first element inserted is the first element to go out of the queue. A queue
can be represented using an array as shown in fig.8.2. The operations that can be
performed on these queues are

Operations on queues -E Insert an item into queue

Delete an item from queue
Display the contents of queue

Letus discuss how these operations can be designed and implemented.

8.2.1.1 Insert at the rear end

Now, let us see "How to implement insert operation using arrays (static allocation
technique)?"

Design: Before inserting any element, we should ask the question "Where and how
the item has to be inserted?" If we know the answer for this question we have the
8.4 Q Queues

insert function ready. So, let us consider the situation where four elements 10, 20, 30
and 40 are already inserted into queue as shown in figure 8.2.a. with f = a and r = 3.

Before insert After insert

(a) (b)

Fi2.8.2 To insert an item 50

Suppose, we have to insert an element say item. Now, let us ask "Where this item has
to be inserted?" We know that it has to be inserted at r = 4. For this to happen, we
have to-increment r by 1 (Fig. 8.2.b). This is achieved using the statement:

r = r + 1; 1* Increment r by 1 *1

Then we ask "How item has to be inserted at rear end?" This is achieved by copying
item to q[r] (Fig 8.2.b) using the following statement:

q[r] = item; 1* Insert into stack *1

But, as we insert an item, we must ask "When we can not insert item into the queue?"
We can not insert any item when r has already reached QUEUE_SIZE - l(Fig. 6.2.b).
In such situation, we have to display appropriate message as shown below:

1* Check for overflow of queue *1

if (r = QUEU-,-SIZE -1)
{
printf("Queue overflow\n");
return;
}
1

Here, QUEUE_SIZE should be #defined (preprocessor directive) and is called

symbolic constant. If the above condition fails, the item has to be inserted. Now, the
complete C function for this can be written as shown below:
 ,!;!. Systematic Approach to Data Structures using C - 8.5

Example 8.~.1.1.1: C function to insert an integer item (Using global variables)

void insertrean)
{
1* Check for overflow of stack *1
if (r =QUEUE_SIZE - 1)
{
printf("Queue overflow\n");
return;
}

r=r+ 1; 1* Increment top by 1 *1 }

q[r] = item; 1* Insert into queue *1 q[++r] = item;

Note: The array q, the variable r and the variable item are global variables and should
be declared before all the functions. As far as possible let us avoid the usage of global
variables in this book.

Let us re-write the above code by passing parameters. It is clear from the above code
that as the item is inserted, the contents of the queue identified by q and r changes.
So, the variables q and r should be passed as parameters (pass by reference) as shown
below:

Example 8.2.1.1.2: C function to insert an integer item (by passing parameters)

void insertrear (int item, int *r, int q[])

{
1* Check for overflow of stack *1
if (*r = QUEUE_SIZE - 1)
{
printf("Queue overflow\n");
return;
(.
*r = *r + 1; 1* Increment top by 1 *1 } q[++(*r)] = item;
q[*r] = item; 1* Insert into queue *1
8.6 Q Queues

Note: Inserting an element at the rear end of queue IS called enqueue. So, to
implement enqueue is same as the above function.
8.2.1.2 Delete from the front end
Now, let us see "How to implement delete front operation using arrays (static
allocation technique)?" Consider the following situation where 3 items are already
inserted into queue and one item is deleted at a time. The sequence of operations are
shown below:

o 3 4

r
After inserting 3 items After deleting 1st item
(a) (b)

f, r r
nd
After deleting 2 item After deleting 3rd item
(c) (d)

Fig.8.2 Queue showing delete operation

Design: Item has to be deleted from the front end inaqueue. This can be achieved by
accessing the front element q[f] as shown below:
printf("Item deleted = %d\n", q[f]); /* Access and print first item */

and then incrementing f by one as shown below:

f= f+ 1 /* Update position of front item */

The above two statements can also be written using single statement as shown below:
.
1 printf("Jtem deleted = %d\n", q[f++]); /* Access and update queue */

Observe that as each item is deleted, the index variable f is incremented so that it
always contains the position of first item (see figure 8.2). Finally, when the queue is
empty the value of f will be greater than r. Once f is greater than r (see Fig. 8.2.d) , it
is not possible to delete any item. This condition is called underflow of queue. Hence,
 Q Systematic Approach to Data Structures using C - 8.7

the above statement has to be executed only if queue is not empty and the code to
delete an item from queue can be written as shown below:

Example 8.2.1.2.1: C function to delete an integer item (using global variables)

void delete_frontO
{
if( f> r)
{
printf("Queue underflow\n");
return;
}
printfC"The element deleted is %d\n",q[(f)++]);

if(f>r)f=O,r=-l; 1* Initialize to queue empty conditions *(

Note: After deleting an item, it may so happen that queue may be empty. So,
immediately after deleting an element, if queue is empty, it is better to initialize f = 0
and r = -1 as shown in the above function. This is the initial status of queue when no
items are inserted and it indicates that queue is initially empty.
Now, let us write the above function without using global variables and by passing
appropriate parameters. Note that f and r contents changes as we delete the items. So,
they should be declared as pointers. The complete C function (by passing parameters)
is shown below:
Example 8.2.1.2.2: C function to delete an integer item (by passing parameters)

void delete_front(int q[], int *f, int *r)

{
if ( *f> *r)
{
printf("Queue underflow\n");
return;
}

printf("The element deleted is %d\n",q[(*f)++]);

if (*f> *r) *f= 0, "r = -1;
I
8.8 ~ Queues

8.2.1.3 Display queue contents

In the display procedure, if the queue already has some items, all those items are
displayed one after the other. If no items are present, the appropriate error message is
displayed. Let us design the display function.

Design: Consider the following situation where 4 items were inserted and first item
has already been deleted.

Usually, the contents of the queue are displayed from the front end and moving
towards right till we get the rear end. So, first item to be displayed is 20, next item to
be displayed is 30 and final item to be displayed is 40. This can be achieved using the
following statements:

Design Output
printf("%d\n"'!IDl ); 20
printf("%d\n", [2); 30
printf("%d\n", 3); 40

In general, we can use printf("%d\n",

!
q (iJ ); I Note: i = 1 to 3
, i = fto r
. I

Note: Please note how the value of i change from f to r (i = 0 to r is wrong). Now, the
code takes the following form:

for (i = f; i <= r; i++)

{
printf("%d\n", q[i]);
}

But, the above statement should not be executed when queue is empty i.e., when f is
greater than r. So, the above code can be modified to include this error condition and
can be written as shown below:
 Q Systematic Approach to Data Structures using C - 8.9

Example 8.2.1.3.1: C function to display the contents of queue (using global

variables)
void displayt)
{
int i;

1* If queue is empty */
if(f>r)
{
printf("Queue is empty\n");
return;
}

/* Display contents of queue */

printf("Contents of the queue\n");
for (i = f; i <= r; i++)
{
printf("%d\n", q[i]);
}

By passing parameters, the function above function can be written as shown below:

Example 8.2.1.3.2: Function to display the contents of queue (using parameters)

void display(int q[], int f, int r)

{
int i;

if ( f> r)
{
printf("Queue is empty\n");
return;
}

printf("Contents of queue is\n");

for ( i = f; i <= r; i++)
printf(" %d\n",q[i]);
8.10 Q Queues

The complete C program to implement different operations on an ordinary queue is

shown below:

Example 8.2.1.3.3: C program to implement queue operations (static/array

implementation) using global variables

#include.<stdi~.h>
#include <process.h>

#define QUEUE_SIZE 5

int choice,item,f,r,q[1 0]; /* Global variables */

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

/* Include: Example 8.2.1.2.1: Function to delete an item (using global variables) */
/* Include: Example 8.2.1.3.1: To display contents of queue (global variables) */
void maim)
{
/* Initially queue is empty */
f= 0; /* Front end of queue */
r = -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, q, &r);
. break;

case 2:
delete_front(q, &f, &r);
 Q Systematic Approach to Data Structures using C - 8.11

break;

case 3:
display( q, f, r);
break;

default:
exit(O);
}
}

Example 8.2.1.3.4: C program to implement queue operations

by passing parameters

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

#defineQUEUE_SIZE 5

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

1* Include: Example 8.2.1.2.2: Function to delete an item (by passing parameters) */
1* Include: Example 8.2.1.3.2: Function to display the contents of queue */
void maim)
{
int choice,item,f,r,q[ 10];

/* Initially queue is empty */

f=O; /* Front end of queue */
r = -1; /* Rear end of queue* /

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

switch ( choice)
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d", &item);
insert_rear(item, &r, q);
break;
case 2:
delete_front(q, &f, &r);
break;
case 3:
display( q, f, r);
break;
default:
exit(O);
}
}
}

8.2.2 Double ended queue (Dequeue)

In this section, let us concentrate on another queue called double ended queue. In
short, it is also called dequeue. Now, let us see "What is a double ended queue (or
dequeue)? and "What are the various operations that can be performed on dequeues?"
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
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

1
Display the contents of queue
Note: The three operations insert rear, delete_front and display operations have
already been discussed in section 8.2.1. 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.
 .Q Systematic Approach to Data Structures using C - 8.13

8.2.2.1 Insert at the front end

Now, let us see "How to implement insert front function using arrays (static allocation
technique)?"

Design: Before inserting any element, we should ask the question "Where and how
the item has to be inserted?" 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: Note that queue is empty. Here, an item can be inserted at the
front end first by incrementing r by 1 and then insert an item.

-1 o 1 2 3 4 -1

r f

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 */

if(f=O&&r=-l)
{
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:

f, r
After deleting 2 items After inserting 20
(a) (b)
 8.14 Q Queues

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

/* Insert at the front end if possible: Case 2 */
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.

o 1 2 3 4
I 10 I 20 I 30 I I I
f r
Q after inserting 10, 20, 30

Now, Observe that, it is not possible to insert an any item at the front end and we
should display the appropriate message:
printf("Front insertion not possible\n");
I
The complete C function to insert an item at the front end is shown below:

Example 8.2.2.1.1: Function to insert an item at the front end (using global variables)

void insertfrontt)
{
if (f= 0 && r = -1) '/* Case 1: Insert when Q empty */
{
q[++(r)] =item;
return;
}

if (f!= 0) /* Case 2: Insert when items are present */

{
q[ --(f)] = item;
1 return;
}
printf("Front insertion not possible\n");
} /* Case 3: Insertion not possible at front end */
 Q Systematic Approach to Data Structures using C - 8.15

By passing parameters, the above function can be written as shown below:

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

8.2.2.2 Delete from the rear end

Now, let us see "How to implement delete rear operation using arrays (static
allocation technique)?" Consider the following situation where 3 items are already
inserted into queue and one item is deleted.

o 1 2 3 4 o 1 2 3 4
I 10 I 20 I 30 I I I I 10 I ·20 I I I I
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:
printf("ltem deleted = %d\n", q[r]); 1* Access and print rear item *1
and then decrementing r by one as shown below:
 8.16 Q Queues

r=r-1; 1* Update position of rear item *i

The above two statements can also be written using single statement as shown below:
printf("Item deleted = %d\n", q[r--]); 1* Access and update queue *1
. Observe that as each item is deleted, the index variable r is decrementd 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 8.2.2.2.1: Function to delete an item from the rear end of queue (Using
global variables)
void delete JearO
{
if(f >r)
{
printf("Queue underflow\n");
return;
}
printf("The element deleted is %d\n",q[(r)--]);
if (f> r) 1* Reset to initial state of empty queue *1
{
f=O,r=-l;
}
}

The above function can be written by passing the parameters as shown below:

Example 8.2.2.2.2: Function to delete an item from the rear end of queue (By passing
parameters)
void drlete Jear(int q[],int *f, int *r)
{
if (*f > *r)
{
printf("Queue underflow\n");
return;
}
 Q Systematic Approach to Data Structures using C - 8.17
printf("The element deleted is %d\n",q[(*r)-- J);

if (*f> *r) 1* Reset to initial state of empty queue */

{
*f= 0, *r = -1;
}

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

shown below

Example 8.2.2.2.3: C program to implement double-ended queue usmg global

variables

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

#define QUE~ _ SIZE 5

int choice,item,f,r,q[lO]; /* Global variables */
"
1* Include: Example 8.2.1.1.1: Function to insert an itemat the rear end */
1* Include: Example 8.2.1.2.1: Function to delete an item at the front end */
1* Include: Example 8.2.2.1.1: Function to insert an item at the front end */
* Include: Example 8.2.2.2.1: Function to delete an item at the rear end */
1* Include: Example 8.2.1.3.1: To display contents of queue */
void maim)
{
/* Initially queue is empty */
f= 0; /* Front end of queue */
r = -1; 1* Rear end of queue*/
for (;;)
{
printf("l :Insert_front 2:Insert_rear\n");
printf("3:Delete _front 4:Delete Jear\n");
print.f("5:Display 6:Exit\n");
printf("Enter the choice\n");
scanf("%d" ,&choice);
 8.18 Q Queues

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

insert _fronn);
break;

case 2:
printf("Enter the item to be inserted\n");
scanf("%d" ,&item);
insert JearO;
break;

case 3:
delete _ fronu);
break;

case 4:
deleterean);
break;

case 5:
displayt);
break;

default:
exit(O);
}
}
}

I Example 8.2.2.2.4:
parameters.
C program to implement double-ended queue by passing

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

#define QUEUE_SIZE 5
 Q Systematic Approach to Data Structures using C - 8.19

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

/* Include: Example 8.2.1.2.2: Function to delete an item at the front end */
1* Include: Example 8.2.2.1.2: Function to insert an item at the front end */
1* Include: Example 8.2.2.2.2: Function to delete an item at the rear end */
'* Include: Example 8.2.1.3.2: To display contents of queue *1
void maint)
{
int choice,item,f,r,q[ 10];

f=O;
r = -1;

for (;;)
{
printf(" 1:Insert _front 2:Insert Jear\n");
printf("3 :Delete _front 4:Delete Jear\n");
printf("5:Display 6:Exit\n");
printf("Enter the choice\n");
.s~anf("%d" ,&choice);

switch ( choice)
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%djl,&item);
insert_front(item, q, &f, &r);
break;

case 2:
printf("Enter the item to be inserted\n");
scanf("%d" ,&item);
insertrearutem, &r, q);
break;

case 3:
deletefronuq, &f, &r);
break;
 8.20 Q Queues

case 4:
delete_rear(q, &f, &r);
break;

, case 5:
• display( q, f, r);
break;

default:
exit(O);
}
". }
}

8.2.2.3 Disadvantage of queue

We know that queue is a data structure where elements are inserted from one end and
elements are deleted at the other end. Now, let us see "What is the disadvantage of
representing a queue using array?" Consider the queue shown below:

o 1 2

f r
This situation will arise 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
"Queue overflow"

This is because, in our function insertrear (see example 8.2.1.1.1) before inserting r
is compared with QUEUE_SIZE - 1. Since r is same as QUEUE_SIZE -1, insertion
not possible. Note that "Rear insertion is denied in a queue even if room is available
at the front end". Thus, even if free memory is available, we can not access these
memory locations. This is a disadvantage. This disadvantage can be overcome by
moving the item at the front end of the queue to the very first location of queue and
then shifting the remaining element from second location onwards. But; shifting the
data is costly in terms of computer time if the data being stored is very large. S , this
method is not recommended. Let us see, how these disadvantages and difficulties can
be overcome using "Circular queue represented as an array".
 Q Systematic Approach to Data Structures using C - 8.21

8.2.3 Circular queue

Now, we shall see "What is a circular queue?"

Definition: In circular queue, the elements of a given queue can be stored efficiently
in an array so as to "wrap around" so that 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 shown in next page. 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 a circular queue
usmg arrays. .
Assume that circular queue contains only one item as shown in fig. 8.6.a. Note
that the value of f = r = O. We know that item is inserted only at the rear end. So,
before inserting the value of r should be -1.

Note: So, initially when stack is empty, f = 0 and r = -1

The configuration shown in fig.8.6.b is obtained after inserting 20 and 30. To insert
an item, the rear index r has to be incremented first. For this, any of the two
statements shown below can be used.

r=r+1 or r = (r + 1) % QUEUE_SIZE

Both statements will increment r by 1. But, we prefer the second statement. Let us
see, why we consider the second approach. The queue shown in fig.8.6.c is obtained
after inserting 40 and 50. Note that at this point, the queue is full. Suppose we delete
two items 10 and 20 one after the other. The resulting queue is shown in fig.8.6.d.
Now, try to insert an item 60. If the statement

r=r+1

is used to increment rear pointer, the value of r will be 5. Since it is it circular queue r
shouldbe O.This can be achieved using the statement

r = (r + 1) % QUEUE_SIZE

After execution of the above statement, r will be O. If this approach is used, to check
foroverflow or underflow, we use a variable count that contains the number of items
in the queue at any instant. So, as an item is inserted, increment count by 1 and as an
item is deleted, decrement count by 1. By this it is ensured that at any point of time,
count always contains the total number of elements in the queue. So, if queue is
empty, count will be 0 and if queue is full, count will be QUEUE_SIZE.
8.22 Q Queues

,2

4
@ 1
o
1 ~
o

f, r
1 2 3 4

(a)
f,r

2r

@
o 1 2 3 4

4' 20 1 ~
f r
10
o (b) After inserting 20 & 30
f

2
4 0
o 1 2 3 4

r 4 5 2 1 ~
f r
~ 10
o (c) After inserting 40 & 50
f

@ 4 0 f o 1 2 3 4

4 5 1 ~
r f r

o After Deleting 10 & 20

(d)

@ 4 0 f o 1 2 3 4

4 5 1 ~
1
6 r f

o
r (e) After inserting 60

Fig.8.6 Pictorial representation of a circular queue

 Q Systematic Approach to Data Structures using C - 8.23

Note: As usual, the various operations that can be performed on circular queues are:
+ Insert rear
• Delete front
• Display

Let us see, "How to implement circular queue- operations?"

8.2.3.1 To insert from the rear end

Now, let us see ''What are the various steps to be followed while inserting?" The
following steps are followed:

Step 1: Check for overflow: Now, let us see "How to check for overflow?" This is
achieved using the following statements:

if (count = QUEUE_SIZE)
{
printf("Queue is ful1\n");
return;
}

Step 2: Insert item: This is achieved by incrementing r by 1 and then inserting as

shownbelow: -
r = (r + 1) % QUEUE_SIZE;
q[r] = item;

Step 3: Update count: As we insert an element update count by 1. This is achieved

using the following statement:
count++;

So,the complete function to insert an item at the end of circular queue is shown
below:

Example 8.2.3.1.1: Function to insert an item at the rear end

voidinsertrearfint item, int q[], int *r, int *count)

{
if ( *count = QUEUE_SIZE) /* Check for overflow */
{
printf("Overflow of queue\n");
return;
}
8.24 Q Queues

*r = (*r + 1) % QUEUE_SIZE; 1* increment rear pointer *1

q[*r] = item; 1* Insert the item *1

*count += 1; 1* update the counter *1

}

8~2.3.2To delete from the front end

Now, let us see "What are the various steps to be followed while deleting an
element?" The following steps are followed:
Step 1: Check for undeflow: Now, let us see "How to check for underflow?" This is
achieved using the following statements:
if (count = 0)
{
printf("Queue is empty\n");
return;
}
Step 2: Delete item: This is achieved by accessing the element using index f and then
incrementing f by 1 (As we did in other queues). The equivalent statements can be
written as shown below: incremeriting r by 1 and then inserting as shown below: '

printf("The deleted element is %d\n",-q[f]);

f= (f+ 1) % QUEUE_SIZE;

Step 3: Update count; As we insert an element update count by '1: This is achieved
using the following statement:
count++;

So, the complete function to delete an item from the front end of circular queue is
shown below:

Example 8.2.3.2.1: Function to delete an item from the front end of circular queue
; .
void delete _front(int q[], int *f, int *count)
{ ~
if( *count = 0)
{
printf("Underflow of queue\n");
return;
}
 Q Systematic Approach to Data Structures using C - 8.25

printf("The deleted element is %d\n",q[*f]); 1* Access the item *1

*f = (*f + 1) % QUEUE_SIZE; 1* Point to next first item *1
*count -= 1; 1* update counter *1

8.2.3.3 To display queue contents

Now, let us see "What are the various steps to be followed while displaying the
elementsof circular queue?" The following steps are followed:
Step 1: Check for undeflow: Now, let us see "How to check for underflow?" This is
achievedusing the following statements:
if (count = 0)
{
printf("Queue is empty\n");
return;
}
Step 2: Display: Display starts from the front index f. After displaying q[f] we have
to update f by 1 (as we did for r). The procedure is repeated for count number 'of
times. This is because, count contains the number of elements in queue. The
equivalentcode for this can be written as:
for (i = 1; i < = count; i++)
{
printf("%d\n", q[f]);
f= (f+l) % QUEUE_SIZE;
}
So,the complete function to delete an item from the front end of circular queue is
shownbelow:

Example 8.2.3.3.1: Function to display the contents of circular queue

void display(int q[], int f, int count)
(
int i;
if ( count = 0 ) 1* Check for queue empty *1
{
printf("Q is empty\n"); ,
return;
}
8.26 Q Queues

printf("Contents of queue is\n"); /* Print count number of times */

for ( i = 1; i <= count; i++)

{
printf("%d\n",q[f]); /* access the item */
f= (f + 1) % QUEUE_SIZE; /* Point to next item */
}
}

The complete C program to implement circular queue using arrays is shown below:

Example 8.2.3.3.2: C program to implement circular queue

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

#define QUEUE_SIZE 5

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

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

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

void maint)
{
int choice,item,f,r,count,q[20];

f=O;
r = -1;
count = 0; /* queue is empty */
for (;;)
l {

printf(" 1:Insert . 2:Delete\n");

printf("3 :Display 4:Exit\n");
printf("Enter the choice\n");
scanf("%d" ,&choice);
 Q Systematic Approach to Data Structures using C - 8.27

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

case 2:
delete_front(q, &f, &count);
break;

case 3:
display( q, f, count);
break;

default:
exit(O);
}
}

8.2.4 Priority queue

In this section, let us see another variation of queue called priority queue. Let us see
"Whatis priority queue? What are the various types of priority queues?"
Definition.r;.he priority queue is a special type of data structure in which items can
beinserted or deleted based on the priority. Always an element with highest priority
isprocessed before processing any of the lower priority elements. If the elements in
thequeue are of same priority, then the element, which is inserted first into the queue,
isprocessed. Priority queues are used in job scheduling algorithms in the design of
operatingsystem where the jobs with highest priorities have to be processed first.

Thepriority queues are classified into two groups:

• 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.
8.28 Q Queues

Now, let us see "How to implementation of priority queues?" There are vanous
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 JearO - which inserts the item at the end of the queue.
• remove _ smallt) - 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.
• displayr) - 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.

Example 8.2.4.1: Function to insert an item at the correct place in priority queue
l

void insert_item(int item, iat q[], int *r)

{
int J;
 Q Systematic Approach to Data Structures using C - 8.29

if ( *r = QUEUE _ SIZE-l ) 1* Check for overflow *1

{
printf("Q is full\n");
return;
}

j = *r; I*Compare from this initial rear point *1

1* Find the appropriate position to make room for inserting

* an item based on the priority *1
1* Item to be inserted is less than q[j] *1
while (j >= 0 && item < q[j])
{
q[j-H] = q[j]; 1* Move the item at q[j] to its next position *1
j--;
}

q[j+ 1] = item; 1* Insert an item at the appropriate position *1

*r = *r + 1; 1* Update the rear pointer *1

Note: To implement priority queue, insert an item such that items are arranged in
ascending order. But, always delete an item from the front end. The functions
delete_front{) and display{) remains unaltered. The complete program to implement
priority queue is shown below:

Example 8.2.4.2: C Program to implement priority queues

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

#define QUEUE_SIZE 5
/

/* Include: Example 8.2.1.2.2: C function to delete an integer item *1

/* Include: Example 8.2.1.3.2: Function to display the contents of queue *1

/* Include: Example. 8.2.4.1: Function to insert item at the correct place in queue *1
8.30 Q Queues

void maint)
{
int choice,item,f,r,q[10];

f= 0;
r = -1;

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_item(item, q, &r);
break;

case 2:
delete_front(q, &f, &r);
break;

case 3:
display( q,f,r);
break;

default:
exit(O);
}
}
}

Note: We can input in any order. But, the items are inserted at the appropriate
position and are arranged in ascending order. The item at Oth position is having
highest priority; the item at 15t position is having next highest priority and so on.
Finally, the item at the end of the queue is having the least priority. So, if we remove
from front, an item with highest priority is removed.