Data Structure and Algorithm
Queue
In ordinary English, a queue is defined as a waiting line, like a line of people waiting
to purchase tickets, where the first person in line is the first person served. In
computer applications a queue has the following definition.
1. Definition
A queue is an ordered collection of items from which items may be
deleted at one end (called the front or head of the queue) and into which items
may be inserted at the other end (called the rear or tail of the queue)
Like stack, queue is also a dynamic structure which can expand and shrink while
items are inserted and deleted respectively.
The first element inserted into a queue is the first to be removed from the queue.
For this reason a queue is sometimes called a FIFO (First-In, First-Out) list.
2. Examples of a queue
There are a number of real-world examples for queue
a line of cars in a petrol station
a line of people at a bank for payment
a line at bus stop
waiting to get hair cut at barber shop
within a computer system there may be queues of tasks waiting for
printer, for access to disk storage, and in time-sharing systems for use of
the CPU.
Queues are frequently used in simulations. In queuing process there are a number of
customers coming to servers to receive service. The number of servers may be
limited. Therefore, customers have to wait in queues before they are served, and they
spend some amount of time while they are being served. Customers can be people or
any other objects.
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 1 of 7
Data Structure and Algorithm
3. Representation of queue
A queue can be represented by using a one dimensional array to hold the
elements of the queue and by using two variables, front and rear to hold the
positions within the first and the last elements of the queue. A queue of integers
can be represented using structure as follows
#define MAX 100
struct queue
{
int items[MAX];
int front;
int rear;
};
enum boolean {false, true};
4. Operations on queue
The major operations that are performed on a queue are the following
Operation Explanation
Create (q) Initializes an empty queue
Empty (q) Checks whether the queue is empty or not
Full (q) Checks whether the queue reaches maximum array size
Front(q) Returns the front item
Enqueue (q, x) Inserts the item x on the rear of the queue
Dequeue(q) Removes the front element of the queue
5. Array implementation
Like stacks queues can be easily implemented using one dimensional array.
a) Create(q)
Initially both the front and the rear pointers are set to -1.
void create(queue *pq)
{
pq->front=pq->rear=-1;
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 2 of 7
Data Structure and Algorithm
b) Empty(q)
The empty condition is satisfied when the front and the rear pointers are
equal. By the create operation both the front and rear pointer were set to -1. So
initially the queue is empty.
boolean empty(queue *pq)
{
return (pq->front==pq->rear?true:false);
}
c) Full(q)
The queue can not be said full just because the rear pointer reaches the
maximum size. Due to some sequence of enqueue and dequeue operations, some
locations near the front end of the queue may be unused. Therefore, using the
full(q) function we must first check whether the rear has reached the maximum
size. If so, check for any vacant location near the front end. If no such location is
found we say the queue is full, or else we move the elements towards the
beginning of the queue to accommodate the incoming element. The front and
rear values get changed accordingly. This method will, however, create
inefficiency. We will see how the inefficiency can be avoided using circular
queues.
boolean full(queue *pq)
{
if(pq->rear>=MAX-1)
{
if(pq->front==-1)
return true;
else
{
for(int i=pq->front+1;i<=pq->rear;i++)
pq->items[i-pq->front-1]=pq->items[i];
pq->rear=pq->rear-pq->front-1;
pq->front=-1;
return false;
}
}
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 3 of 7
Data Structure and Algorithm
return false;
}
d) Front(q)
The front function returns the element available at the front of the queue.
This operation is successful only when the queue is not empty.
int front(queue *pq)
{
if(empty(pq))
{
cout<<"\nQueue underflow";
exit(1);
}
return pq->items[pq->front+1];
}
e) Enqueue(q,x)
Normally the enqueue operation can always be applied since there is no limit on
the number of items a queue may contain. But, as in the case of stacks, depending on
the implementation the size of the queue may be restricted. When a queue is
implemented by one dimensional array, new items may be inserted into the queue
only when there is a cell within the array to hold the item. After all the array cells
are occupied, trying to add additional element will result in overflow. Therefore,
always before adding a new item into the queue overflow condition must be
checked.
The enqueue(q,x) function inserts the element x at the rear of the queue q,
and succeeds only if the queue is not full.
void enqueue(queue *pq,int x)
{
if(full(pq))
{
cout<<"\nQueue overflow";
exit(1);
}
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 4 of 7
Data Structure and Algorithm
else
pq->items[++pq->rear]=x;
}
f) Dequeue(q)
In order to remove item from the front of a queue, first we have to check
whether the queue is empty or not. Trying to delete some thing from an empty
queue will result in underflow.
The dequeue(q) function deletes the front element and returns it. It
performs successfully if the queue is not empty.
int dequeue(queue *pq)
{
if(empty(pq))
{
cout<<"\nQueue underflow";
exit(1);
}
return pq->items[++pq->front];
}
Circular Queue
In the above array implementation of queue, the problem of inefficiency
arises only when the value of the rear pointer exceeds the maximum size of the
array during the enqueue operation. This is due to the shifting of elements
towards the beginning of the array to accommodate the incoming element. This
problem can be corrected if we logically consider the queue to be circular. In this
case, the necessity for shifting elements does not arise, and at the same time the
allocated memory will be used efficiently. The concept of circular queue is
therefore useful for array based implementation.
Once the rear pointer reaches the maximum size, the next location at
which the element can be added is the first one (index 0), provided the first
location is vacant. The interesting thing to note here is that the queue wraps
around the end of the array. The specific location of the queue can be easily
determined by using the mod operator (%).
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 5 of 7
Data Structure and Algorithm
The implementation of a circular queue is carried out by initially setting both
the front and rear pointers to 0. Here, the location pointed to by the front pointer
must be vacant. This helps us to determine the empty or full condition of the queue.
The location pointed to by the front pointer will be empty even when the queue is
full. The location prior to the front pointer is the rear pointer if the queue is full. The
condition for checking the queue full status therefore is front==(rear+1)%MAX.
a) Create(q)
void create(queue *pq)
{
pq->rear=pq->front=0;
}
a) Empty(q)
int empty(queue *pq)
{
return (pq->front==pq->rear);
}
b) Full(q)
int full(queue *pq)
{
return (pq->front==(pq->rear+1)%MAX);
}
c) Front(q)
int front(queue *pq)
{
if(empty(pq))
{
cout<<"\nQueue underflow";
exit(1);
}
return pq->items[pq->front+1];
}
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 6 of 7
Data Structure and Algorithm
d) Enqueue(q,x)
void enqueue(queue *pq,int x)
{
if(full(pq))
{
cout<<"\nQueue overflow";
exit(1);
}
else
{
pq->rear=(pq->rear+1)%MAX;
pq->items[pq->rear]=x;
}
}
e) Dequeue(q)
int remove(queue *pq)
{
if(empty(pq))
{
cout<<"\nQueue underflow";
exit(1);
}
pq->front=(pq->front+1)%MAX;
return pq->items[pq->front];
}
Queue, Lecture Note
Compiled by worku wondimu, Unity University Page 7 of 7