Queue

A Queue is a linear structure which follows a particular order in which the

operations are performed. The order is First In First Out (FIFO). A good
example of a queue is any queue of consumers for a resource where the
consumer that came first is served first. The difference between stacks and
queues is in removing. In a stack we remove the item the most recently added;
in a queue, we remove the item the least recently added.

Applications of Queue Data Structure

Last Updated: 30-06-2018
Queue is used when things don’t have to be processed immediately, but have to
be processed in First In First Out order like Breadth First Search. This property
of Queue makes it also useful in following kind of scenarios.
1) When a resource is shared among multiple consumers. Examples include
CPU scheduling, Disk Scheduling.
2) When data is transferred asynchronously (data not necessarily received at
same rate as sent) between two processes. Examples include IO Buffers, pipes,
file IO, etc.
Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it,
and then completely erasing it from the memory. Here we shall try to
understand the basic operations associated with queues −
• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.
Implementation of Queue
• using array
• using linked list
 Implementation of Queue using array

Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are
comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
• Step 1 − Check if the queue is full.
• Step 2 − If the queue is full, produce overflow error and exit.
• Step 3 − If the queue is not full, increment rear pointer to point the next
empty space.
• Step 4 − Add data element to the queue location, where the rear is pointing.
• Step 5 − return success.

Sometimes, we also check to see if a queue is initialized or not, to handle any

unforeseen situations.
Algorithm for enqueue operation
procedure enqueue(data)

if queue is full
return overflow
endif

rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementation of enqueue() in C programming language −
Example
int enqueue(int data)
if(isfull())
return 0;

rear = rear + 1;
queue[rear] = data;

return 1;
end procedure

Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data
where front is pointing and remove the data after access. The following steps are
taken to perform dequeue operation −
• Step 1 − Check if the queue is empty.
• Step 2 − If the queue is empty, produce underflow error and exit.
• Step 3 − If the queue is not empty, access the data where front is pointing.
• Step 4 − Increment front pointer to point to the next available data element.
• Step 5 − Return success.

Algorithm for dequeue operation

procedure dequeue
 if queue is empty
return underflow
end if

data = queue[front]
front ← front + 1
return true

end procedure
Implementation of dequeue() in C programming language −
Example
int dequeue() {
if(isempty())
return 0;

int data = queue[front];

front = front + 1;

return data;
}

Drawback of array implementation

Although, the technique of creating a queue is easy, but there are some drawbacks of
using this technique to implement a queue.

o Memory wastage : The space of the array, which is used to store queue
elements, can never be reused to store the elements of that queue because the
elements can only be inserted at front end and the value of front might be so
high so that, all the space before that, can never be filled.

The above figure shows how the memory space is wasted in the array representation of
queue. In the above figure, a queue of size 10 having 3 elements, is shown. The value of
the front variable is 5, therefore, we can not reinsert the values in the place of already
deleted element before the position of front. That much space of the array is wasted and
can not be used in the future (for this queue).

o Deciding the array size

On of the most common problem with array implementation is the size of the array
which requires to be declared in advance. Due to the fact that, the queue can be
extended at runtime depending upon the problem, the extension in the array size is a
time taking process and almost impossible to be performed at runtime since a lot of
reallocations take place. Due to this reason, we can declare the array large enough so
that we can store queue elements as enough as possible but the main problem with this
declaration is that, most of the array slots (nearly half) can never be reused. It will again
lead to memory wastage.

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial, the array
implementation can not be used for the large scale applications where the queues are
implemented. One of the alternative of array implementation is linked list
implementation of queue.

The storage requirement of linked representation of a queue with n elements is o(n)

while the time requirement for operations is o(1).

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

In the linked queue, there are two pointers maintained in the memory i.e. front pointer
and rear pointer. The front pointer contains the address of the starting element of the
queue while the rear pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and
rear both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

 Operation on Linked Queue
There are two basic operations which can be implemented on the linked queues. The
operations are Insertion and Deletion.

Insert operation
Algorithm
o Step 1: Allocate the space for the new node PTR
o Step 2: SET PTR -> DATA = VAL
o Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
o Step 4: END

Deletion
Deletion operation removes the element that is first inserted among all the queue
elements. Firstly, we need to check either the list is empty or not. The condition front
== NULL becomes true if the list is empty, in this case , we simply write underflow on
the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front. For this
purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift the
front pointer, point to its next node and free the node pointed by the node ptr. This is
done by using the following statements.

1. ptr = front;
2. front = front -> next;
3. free(ptr);

The algorithm and C function is given as follows.

Algorithm
o Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
o Step 2: SET PTR = FRONT
o Step 3: SET FRORT = FRONT -> NEXT
o Step 4: FREE PTR
o Step 5: END