5.1 What is a Queue?

A queue is a data structure used for storing data (similar to Linked Lists and Stacks). In queue, the
order in which data arrives is important. In general, a queue is a line of people or things waiting
to be served in sequential order starting at the beginning of the line or sequence.

Definition: A queue is an ordered list in which insertions are done at one end (rear) and
deletions are done at other end (front). The first element to be inserted is the first one to be
deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.

Similar to Stacks, special names are given to the two changes that can be made to a queue. When
an element is inserted in a queue, the concept is called EnQueue, and when an element is
removed from the queue, the concept is called DeQueue.

DeQueueing an empty queue is called underflow and EnQueuing an element in a full queue is
called overflow. Generally, we treat them as exceptions. As an example, consider the snapshot of
the queue.

5.2 How are Queues Used?

The concept of a queue can be explained by observing a line at a reservation counter. When we
enter the line we stand at the end of the line and the person who is at the front of the line is the one
who will be served next. He will exit the queue and be served.

As this happens, the next person will come at the head of the line, will exit the queue and will be
served. As each person at the head of the line keeps exiting the queue, we move towards the head
of the line. Finally we will reach the head of the line and we will exit the queue and be served.
This behavior is very useful in cases where there is a need to maintain the order of arrival.

5.3 Queue ADT

The following operations make a queue an ADT. Insertions and deletions in the queue must
follow the FIFO scheme. For simplicity we assume the elements are integers.

Main Queue Operations

• EnQueue(int data): Inserts an element at the end of the queue
• int DeQueue(): Removes and returns the element at the front of the queue

Auxiliary Queue Operations

• int Front(): Returns the element at the front without removing it
• int QueueSize(): Returns the number of elements stored in the queue
• int IsEmptyQueueQ: Indicates whether no elements are stored in the queue or not

5.4 Exceptions
Similar to other ADTs, executing DeQueue on an empty queue throws an “Empty Queue
Exception” and executing EnQueue on a full queue throws “Full Queue Exception”.

5.5 Applications

Following are some of the applications that use queues.

Direct Applications
• Operating systems schedule jobs (with equal priority) in the order of arrival (e.g., a
print queue).
• Simulation of real-world queues such as lines at a ticket counter or any other first-
come first-served scenario requires a queue.
• Multiprogramming.
• Asynchronous data transfer (file IO, pipes, sockets).
• Waiting times of customers at call center.
• Determining number of cashiers to have at a supermarket.

Indirect Applications
• Auxiliary data structure for algorithms
• Component of other data structures

5.6 Implementation

There are many ways (similar to Stacks) of implementing queue operations and some of the
commonly used methods are listed below.
• Simple circular array based implementation
• Dynamic circular array based implementation
• Linked list implementation

Why Circular Arrays?

First, let us see whether we can use simple arrays for implementing queues as we have done for
stacks. We know that, in queues, the insertions are performed at one end and deletions are
performed at the other end. After performing some insertions and deletions the process becomes
easy to understand.

In the example shown below, it can be seen clearly that the initial slots of the array are getting
wasted. So, simple array implementation for queue is not efficient. To solve this problem we
assume the arrays as circular arrays. That means, we treat the last element and the first array
elements as contiguous. With this representation, if there are any free slots at the beginning, the
rear pointer can easily go to its next free slot.

Note: The simple circular array and dynamic circular array implementations are very similar to
stack array implementations. Refer to Stacks chapter for analysis of these implementations.

Simple Circular Array Implementation

This simple implementation of Queue ADT uses an array. In the array, we add elements circularly
and use two variables to keep track of the start element and end element. Generally, front is used
to indicate the start element and rear is used to indicate the end element in the queue. The array
storing the queue elements may become full. An EnQueue operation will then throw a full queue
exception. Similarly, if we try deleting an element from an empty queue it will throw empty
queue exception.

Note: Initially, both front and rear points to -1 which indicates that the queue is empty.
Performance and Limitations

Performance: Let n be the number of elements in the queue:

Space Complexity (for n EnQueue operations) O(n)

Time Complexity of EnQueue() O(1)
Time Complexity of DeQueue() O(1)
Time Complexity of IsEmptyQueue() O(1)
Time Complexity of IsFullQueue() O(1)
Time Complexity of QueueSize() O(1)

Time Complexity of DeleteQueue() O(1)

Limitations: The maximum size of the queue must be defined as prior and cannot be changed.
Trying to EnQueue a new element into a full queue causes an implementation-specific exception.

Dynamic Circular Array Implementation

Performance

Let n be the number of elements in the queue.

Space Complexity (for n EnQueue operations) O(n)

Time Complexity of EnQueue() O(1) (Average)
Time Complexity of DeQueue() O(1)
Time Complexity of QueueSize() O(1)
Time Complexity of IsEmptyQueue() O(1)
Time Complexity of IsFullQueue() O(1)
Time Complexity of QueueSize() O(1)
Time Complexity of DeleteQueue() O(1)

Linked List Implementation

Another way of implementing queues is by using Linked lists. EnQueue operation is implemented
by inserting an element at the end of the list. DeQueue operation is implemented by deleting an
element from the beginning of the list.
Performance

Let n be the number of elements in the queue, then

Space Complexity (for n EnQueue operations) O(n)

Time Complexity of EnQueue() O(1) (Average)
Time Complexity of DeQueue() O(1)

Time Complexity of IsEmptyQueue() O(1)

Time Complexity of DeleteQueue() O(1)

Comparison of Implementations

Note: Comparison is very similar to stack implementations and Stacks chapter.

5.7 Queues: Problems & Solutions

Problem-1 Give an algorithm for reversing a queue Q. To access the queue, we are only
allowed to use the methods of queue ADT.
Solution:

Time Complexity: O(n).

Problem-2 How can you implement a queue using two stacks?
Solution: Let SI and S2 be the two stacks to be used in the implementation of queue. All we have
to do is to define the EnQueue and DeQueue operations for the queue.
EnQueue Algorithm
• Just push on to stack S1

Time Complexity: O(1).

DeQueue Algorithm
• If stack S2 is not empty then pop from S2 and return that element.
• If stack is empty, then transfer all elements from SI to S2 and pop the top element
from S2 and return that popped element [we can optimize the code a little by
transferring only n – 1 elements from SI to S2 and pop the nth element from SI and
return that popped element].
• If stack S1 is also empty then throw error.

Time Complexity: From the algorithm, if the stack S2 is not empty then the complexity is O(1). If
the stack S2 is empty, then we need to transfer the elements from SI to S2. But if we carefully
observe, the number of transferred elements and the number of popped elements from S2 are
equal. Due to this the average complexity of pop operation in this case is O(1).The amortized
complexity of pop operation is O(1).
Problem-3 Show how you can efficiently implement one stack using two queues. Analyze the
 running time of the stack operations.
Solution: Yes, it is possible to implement the Stack ADT using 2 implementations of the Queue
ADT. One of the queues will be used to store the elements and the other to hold them temporarily
during the pop and top methods. The push method would enqueue the given element onto the
storage queue. The top method would transfer all but the last element from the storage queue onto
the temporary queue, save the front element of the storage queue to be returned, transfer the last
element to the temporary queue, then transfer all elements back to the storage queue. The pop
method would do the same as top, except instead of transferring the last element onto the
temporary queue after saving it for return, that last element would be discarded. Let Q1 and Q2 be
the two queues to be used in the implementation of stack. All we have to do is to define the push
and pop operations for the stack.

In the algorithms below, we make sure that one queue is always empty.

Push Operation Algorithm: Insert the element in whichever queue is not empty.
• Check whether queue Q1 is empty or not. If Q1 is empty then Enqueue the element
into Q2.
• Otherwise EnQueue the element into Q1.

Time Complexity: O(1).

Pop Operation Algorithm: Transfer n – 1 elements to the other queue and delete last from queue
for performing pop operation.
• If queue Q1 is not empty then transfer n – 1 elements from Q1 to Q2 and then,
DeQueue the last element of Q1 and return it.
• If queue Q2 is not empty then transfer n – 1 elements from Q2 to Q1 and then,
DeQueue the last element of Q2 and return it.
Time Complexity: Running time of pop operation is O(n) as each time pop is called, we are
transferring all the elements from one queue to the other.
Problem-4 Maximum sum in sliding window: Given array A[] with sliding window of size
w which is moving from the very left of the array to the very right. Assume that we can
only see the w numbers in the window. Each time the sliding window moves rightwards by
one position. For example: The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position Max

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
 Input: A long array A[], and a window width w. Output: An array B[], B[i] is the
maximum value from A[i] to A[i+w-1]. Requirement: Find a good optimal way to get
B[i]
Solution: This problem can be solved with doubly ended queue (which supports insertion and
deletion at both ends). Refer Priority Queues chapter for algorithms.
Problem-5 Given a queue Q containing n elements, transfer these items on to a stack S
(initially empty) so that front element of Q appears at the top of the stack and the order of
all other items is preserved. Using enqueue and dequeue operations for the queue, and push
and pop operations for the stack, outline an efficient O(n) algorithm to accomplish the
above task, using only a constant amount of additional storage.
Solution: Assume the elements of queue Q are a1:a2 ...an. Dequeuing all elements and pushing
them onto the stack will result in a stack with an at the top and a1 at the bottom. This is done in
O(n) time as dequeue and each push require constant time per operation. The queue is now empty.
By popping all elements and pushing them on the queue we will get a1 at the top of the stack. This
is done again in O(n) time.

As in big-oh arithmetic we can ignore constant factors. The process is carried out in O(n) time.
The amount of additional storage needed here has to be big enough to temporarily hold one item.
Problem-6 A queue is set up in a circular array A[O..n - 1] with front and rear defined as
usual. Assume that n – 1 locations in the array are available for storing the elements (with
the other element being used to detect full/empty condition). Give a formula for the number
of elements in the queue in terms of rear, front, and n.
Solution: Consider the following figure to get a clear idea of the queue.
 • Rear of the queue is somewhere clockwise from the front.
• To enqueue an element, we move rear one position clockwise and write the element
in that position.
• To dequeue, we simply move front one position clockwise.
• Queue migrates in a clockwise direction as we enqueue and dequeue.
• Emptiness and fullness to be checked carefully.
• Analyze the possible situations (make some drawings to see where front and rear
are when the queue is empty, and partially and totally filled). We will get this:

Problem-7 What is the most appropriate data structure to print elements of queue in reverse
order?

Solution: Stack.
Problem-8 Implement doubly ended queues. A double-ended queue is an abstract data
structure that implements a queue for which elements can only be added to or removed
from the front (head) or back (tail). It is also often called a head-tail linked list.
Solution:
Problem-9 Given a stack of integers, how do you check whether each successive pair of
numbers in the stack is consecutive or not. The pairs can be increasing or decreasing, and
if the stack has an odd number of elements, the element at the top is left out of a pair. For
example, if the stack of elements are [4, 5, -2, -3, 11, 10, 5, 6, 20], then the output should
be true because each of the pairs (4, 5), (-2, -3), (11, 10), and (5, 6) consists of
consecutive numbers.
Solution:

Time Complexity: O(n). Space Complexity: O(n).

Problem-10 Given a queue of integers, rearrange the elements by interleaving the first half of
the list with the second half of the list. For example, suppose a queue stores the following
sequence of values: [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]. Consider the two halves of
this list: first half: [11, 12, 13, 14, 15] second half: [16, 17, 18, 19, 20]. These are
 combined in an alternating fashion to form a sequence of interleave pairs: the first values
from each half (11 and 16), then the second values from each half (12 and 17), then the
third values from each half (13 and 18), and so on. In each pair, the value from the first
half appears before the value from the second half. Thus, after the call, the queue stores the
following values: [11, 16, 12, 17, 13, 18, 14, 19, 15, 20].
Solution:

Time Complexity: O(n). Space Complexity: O(n).

Problem-11 Given an integer k and a queue of integers, how do you reverse the order of the
first k elements of the queue, leaving the other elements in the same relative order? For
example, if k=4 and queue has the elements [10, 20, 30, 40, 50, 60, 70, 80, 90]; the output
should be [40, 30, 20, 10, 50, 60, 70, 80, 90].
Solution:
Time Complexity: O(n). Space Complexity: O(n).