Queues ADT

What is a Queue?
Queue is a linear data structure in which the insertion and
deletion operations are performed at two different ends. In
a queue data structure, adding and removing elements are
performed at two different positions.
The insertion is performed at one end and deletion is
performed at another end. In a queue data structure, the
insertion operation is performed at a position which is
known as ‘REAR' and the deletion operation is performed
at a position which is known as ‘FRONT'. In queue data
structure, the insertion and deletion operations are
performed based on FIFO (First In First Out) principle.
In a queue data structure, the insertion operation is performed
using a function called "enQueue()" and deletion operation
is performed using a function called "deQueue()".

Queue data structure can be defined as follows:

Queue data structure is a linear data structure in which
the operations are performed based on FIFO principle.
A queue data structure can also be defined as
"Queue data structure is a collection of similar data items
in which insertion and deletion operations are performed
based on FIFO principle".
 Example
Queue after inserting 25, 30, 51, 60 and 85.
 Operations on a Queue
The following operations are performed on a queue data
structure...
enQueue(value) - (To insert an element into the queue)
deQueue() - (To delete an element from the queue)
display() - (To display the elements of the queue)

Queue data structure can be implemented in two ways. They

are as follows...
Using Array
Using Linked List
 Implementation of Queue Using Array
A queue data structure can be implemented using one
dimensional array. The queue implemented using array stores
only fixed number of data values. The implementation of
queue data structure using array is very simple. Just define a
one dimensional array of specific size and insert or delete the
values into that array by using FIFO (First In First Out)
principle with the help of variables 'front' and 'rear'.
Initially both 'front' and 'rear' are set to -1. Whenever, we
want to insert a new value into the queue, increment 'rear'
value by one and then insert at that position. Whenever we
want to delete a value from the queue, then delete the element
which is at 'front' position and increment 'front' value by one.
 enQueue(value) - Inserting value into the queue
enQueue(value) - Inserting value into the queue
In a queue data structure, enQueue() is a function used to
insert a new element into the queue. In a queue, the new
element is always inserted at rear position. The
enQueue() function takes one integer value as a parameter
and inserts that value into the queue. We can use the
following steps to insert an element into the queue...
Step 1 - Check whether queue is FULL. (rear == SIZE-1)
Step 2 - If it is FULL, then display "Queue is FULL!!!
Insertion is not possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then increment rear value by
one (rear++) and set queue[rear] = value.
 deQueue() - Deleting a value from the Queue
In a queue data structure, deQueue() is a function used to
delete an element from the queue. In a queue, the element is
always deleted from front position. The deQueue() function
does not take any value as parameter. We can use the
following steps to delete an element from the queue...
Step 1 - Check whether queue is EMPTY. (front == rear)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!
Deletion is not possible!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then increment
the front value by one (front ++). Then
display queue[front] as deleted element. Then check
whether both front and rear are equal (front == rear), if
it TRUE, then set both front and rear to '-1'
(front = rear = -1).
 display() - Displays the elements of a Queue
We can use the following steps to display the elements of a
queue...
Step 1 - Check whether queue is EMPTY. (front == rear)
Step 2 - If it is EMPTY, then display "Queue is
EMPTY!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then define an integer
variable 'i' and set 'i = front+1'.
Step 4 - Display 'queue[i]' value and increment 'i' value by
one (i++). Repeat the same until 'i' value reaches
to rear (i <= rear)
 GATE IT 2007
void fun (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
fun(Q);
insert(Q, i);
}
}
 Leaves the queue Q unchanged
 Reverses the order of the elements in the queue Q
 Deletes the element at the front of the queue Q and inserts it at the
rear keeping the other elements in the same order
 Empties the queue Q
 ISRO 20012
Which one of the following is an application of Queue Data
Structure?
When a resource is shared among multiple consumers.
When data is transferred asynchronously (data not
necessarily received at same rate as sent) between two
processes
Load Balancing
All of the above
 GATE CS 2013
MultiDequeue(Q){
m=k
while (Q is not empty and m > 0)
{
Dequeue(Q) m = m - 1
}
}
What is the worst case time complexity of a sequence of n Multi
Dequeue() operations on an initially empty queue?
 Θ(n)
 Θ(n+k)
 Θ(n2)
 Θ(nk)
 GATE-CS-2016 (Set 1)
A queue is implemented using an array such that ENQUEUE
and DEQUEUE operations are performed efficiently.
Which one of the following statements is CORRECT (n
refers to the number of items in the queue)?
Both operations can be performed in O(1) time
At most one operation can be performed in O(1) time but
the worst case time for the other operation will be Ω(n)
The worst case time complexity for both operations will be
Ω(n)
Worst case time complexity for both operations will be Ω(log
n)
 Implementation of Queue Using Linked List
The major problem with the queue implemented using an
array is, It will work for an only fixed number of data
values. Queue using an array is not suitable when we don't
know the size of data which we are going to use.
A queue data structure can be implemented using a linked
list data structure. The Queue implemented using linked
list can organize as many data values as we want.
In linked list implementation of a queue, the last inserted
node is always pointed by 'rear' and the first node is
always pointed by 'front'.
 enQueue(value) - Inserting an element into the Queue
We can use the following steps to insert a new node into the
queue...
Step-1 - Create a newNode with given value and set
'newNode → next' to NULL.
Step-2 - Check whether queue is Empty (rear == NULL)
Step-3- If it is Empty then,
set front = newNode and rear = newNode.
Step 4 - If it is Not Empty then,
set rear → next = newNode and rear = newNode.
 deQueue() - Deleting an Element from Queue
We can use the following steps to delete a node from the
queue...
Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty, then display "Queue is Empty!!!
Deletion is not possible!!!" and terminate from the
function
Step 3 - If it is Not Empty then, define a Node pointer
'temp' and set it to 'front'.
Step 4 - Then set 'front = front → next' and delete 'temp'
(free(temp)).
 display() - Displaying the elements of Queue
We can use the following steps to display the elements
(nodes) of a queue...
Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty then, display 'Queue is Empty!!!' and
terminate the function.
Step 3 - If it is Not Empty then, define a Node
pointer 'temp' and initialize with front.
Step 4 - Display 'temp → data --->' and move it to the next
node. Repeat the same until 'temp' reaches to 'rear' (temp
→ next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.
 GATE-CS-2016 (Set 1)
Which of the following is true about linked list
implementation of queue?
In push operation, if new nodes are inserted at the
beginning of linked list, then in pop operation, nodes
must be removed from end.
In push operation, if new nodes are inserted at the end,
then in pop operation, nodes must be removed from the
beginning.
Both of the above
None of the above
 GATE CS 2018
 A queue is implemented using a non-circular singly linked list. The
queue has a head pointer and a tail pointer, as shown in the figure.

 Let n denote the number of nodes in the queue. Let 'enqueue' be

implemented by inserting a new node at the head, and 'dequeue' be
implemented by deletion of a node from the tail. Which one of the
following is the time complexity of the most time-efficient
implementation of 'enqueue' and 'dequeue, respectively, for this
data structure?
 Θ(1), Θ(n)
 Θ(1), Θ(1)
 Θ(n), Θ(1)
 Θ(n), Θ(n)
 Circular Queue
In a normal Queue Data Structure, we can insert elements
until queue becomes full. But once the queue becomes full,
we can not insert the next element until all the elements are
deleted from the queue. For example, consider the queue
below.
The queue after inserting all the elements into it is as
follows...

Now consider the following situation after deleting three elements from the queue...
This situation also says that Queue is Full and we cannot
insert the new element because 'rear' is still at last
position.
In the above situation, even though we have empty
positions in the queue we can not make use of them to
insert the new element.
This is the major problem in a normal queue data
structure.
 To overcome this problem we use a circular queue data
structure.
 What is Circular Queue?
A Circular Queue can be defined as follows...
A circular queue is a linear data structure in which the
operations are performed based on FIFO (First In First Out)
principle and the last position is connected back to the first
position to make a circle.Graphical representation of a
circular queue is as follows...
 enQueue(value) - Inserting value into the Circular Queue
The enQueue() function takes one integer value as
parameter and inserts that value into the circular queue.
We can use the following steps to insert an element into
the circular queue...
Step 1 - Check whether queue is FULL. ((rear == SIZE-1
&& front == 0) || (front == rear+1))
Step 2 - If it is FULL, then display "Queue is FULL!!!
Insertion is not possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then check rear == SIZE - 1
&& front != 0 if it is TRUE, then set rear = -1.
Step 4 - Increment rear value by one (rear++),
set queue[rear] = value and check 'front == -1' if it
is TRUE, then set front = 0.
ALGORITHM: Insertion in Queue
// Initially FRONT=0 and REAR = 0
// value is the element to be inserted in the queue
enqueue (value)
{
if ( (REAR + 1) % N == FRONT)
{
print(“Queue is FULL”)
return
}
Queue[REAR]=item
REAR = (REAR + 1) % N
}
 deQueue() - Deleting a value from the Circular Queue
In a circular queue, deQueue() is a function used to delete an
element from the circular queue. We can use the following
steps to delete an element from the circular queue...
Step 1 - Check whether queue is EMPTY. (front == -1 &&
rear == -1)
Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!
Deletion is not possible!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then display queue[front] as
deleted element and increment the front value by one (front
++). Then check whether front == SIZE, if it is TRUE, then
set front = 0. Then check whether both front -
1 and rear are equal (front -1 == rear), if it TRUE, then set
both front and rear to '-1' (front = rear = -1).
ALGORITHM: Deletion in Queue
// item is the element deleted from the queue

int dequeue ()
{
if ( REAR == FRONT)
{
print(“Queue is EMPTY”)
return -1
}
item = Queue[FRONT]
FRONT = (FRONT + 1) % N
Return item
}
 ISRO CS 2014
Consider a standard Circular Queue 'q' implementation
(which has the same condition for Queue Full and Queue
Empty) whose size is 11 and the elements of the queue are
q[0], q[1], q[2].....,q[10]. The front and rear pointers are
initialized to point at q[2] . In which position will the ninth
element be added?
q[0]
q[1]
q[10]
q[9]
 GATE CS 2018
Suppose a circular queue of capacity (n – 1) elements is
implemented with an array of n elements. Assume that the
insertion and deletion operation are carried out using REAR
and FRONT as array index variables, respectively. Initially,
REAR = FRONT = 0. The conditions to detect queue full and
queue empty are:
 Full: (REAR+1) mod n == FRONT, empty: REAR ==
FRONT
 Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod
n == REAR
 Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
 Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
 Double Ended Queue [Deque]
Double Ended Queue is also a Queue data structure in
which the insertion and deletion operations are performed
at both the ends (front and rear). That means, we can
insert at both front and rear positions and can delete from
both front and rear positions.
Double Ended Queue can be represented in TWO ways,
those are as follows...
Input Restricted Double Ended Queue
Output Restricted Double Ended Queue
Input Restricted Double Ended Queue
In input restricted double-ended queue, the insertion
operation is performed at only one end and deletion
operation is performed at both the ends.
Output Restricted Double Ended Queue
In output restricted double ended queue, the deletion
operation is performed at only one end and insertion
operation is performed at both the ends.
 Applications of Deque
A web browser's history. Recently visited URLs are added
to the front of the deque, and the URLs at the back of the
deque is removed after some specified number of insertions
at the front.
Another common application of the deque is storing a
software application's list of undo operations.
Some moneyControl Apps, it will show the stocks you last
visited, it will remove the stocks after some time and will
add the latest ones.
 Priority Queues
Priority queue data structure is an abstract data type that
provides a way to maintain a set of elements, each with an
associated value called key.
There are two kinds of priority queues: a max-priority
queue and a min-priority queue. In both kinds, the
priority queue stores a collection of elements and is always
able to provide the most “extreme” element, which is the
only way to interact with the priority queue. For the
remainder of this section, we will discuss max-priority
queues. Min-priority queues are analogous.
 Operations
A max-priority queue provides the following operations:
 insert: add an element to the priority queue.
 maxElement: return the largest element in the priority queue.
 removeMaxElement: remove the largest element from the priority
queue.
A max-priority queue can also provide these additional operations:
 size: return the number of elements in the priority queue.
 increaseKey: updates the key of an element to a larger value.
 updatePriorities: assume the values of the keys have been
changed and reorder the internal state of the priority queue.
The names of these methods may be different based on
implementations, but all priority queues should provide a way to do
these or similar operations.
 Implementations
Let’s explore several possibilities for data structures we could use to
implement a priority queue:
 Unordered array: A simple, yet inefficient implementation, as
retrieving the max element would require searching the entire array.
 Sorted array: This is not a very efficient implementation either.
Inserting a new element requires linearly searching the array for the
correct position. Removing similarly requires a linear time: the rest
of the elements need to be adjusted (shifted) into correct positions.
 Hash table: Although inserting into a hash table takes constant time
(given a good hash function), finding the max element takes linear
time. Therefore, this would be a poor choice for the underlying data
structure.
 Heap: It turns out that that a heap makes an efficient priority queue.
 Priority Queue Applications
Some of the applications of a priority queue are:
Dijkstra's algorithm
for implementing stack
for load balancing and interrupt handling in an operating
system
for data compression in Huffman code
 UGC NET CS 2016 Aug - III
A priority queue is implemented as a max-heap. Initially,
it has five elements. The level-order traversal of the heap
is as follows: 20, 18, 15, 13, 12 Two new elements ‘10’
and ‘17’ are inserted in the heap in that order. The level-
order traversal of the heap after the insertion of the
element is:
20, 18, 17, 15, 13, 12, 10
20, 18, 17, 12, 13, 10, 15
20, 18, 17, 10, 12, 13, 15
20, 18, 17, 13, 12, 10, 15
 GATE CS 2013
 Consider the following operation along with Enqueue and Dequeue
operations on queues, where k is a global parameter.
MultiDequeue(Q){
m=k
while (Q is not empty and m > 0)
{
Dequeue(Q) m = m - 1
}
}
What is the worst case time complexity of a sequence of n MultiDequeue()
operations on an initially empty queue?
 Θ(n)
 Θ(n+k)
 Θ(n2)
 Θ(nk)