Lecture Notes Series for

CSC 204: Fundamentals of Data Structures

Unit 6: Queues

Dr Fatimah Adamu-Fika

Department of Cyber Security

Faculty of Computing

Air Force Institute of Technology

Kaduna, Nigeria

Version of 2020/2021 Academic Session

© 2020-2022
 CSC 204: FUNDAMENTALS OF DATA STRUCTURES

UNIT 6: QUEUES

TABLE OF CONTENTS

Overview, Concepts and the Queue ADT ..................................................................................................... 4

Specifying a Queue ADT .......................................................................................................................................4

Representation .......................................................................................................................................... 5

Implementation ......................................................................................................................................... 5
Array Implementation..........................................................................................................................................5
Performance and Limitations ..........................................................................................................................6
Circular Queue .................................................................................................................................................6
Linked List Implementation..................................................................................................................................7
Priority Queue ......................................................................................................................................................8
Double Ended Queue (DeQue) .............................................................................................................................9

Basic Operations ........................................................................................................................................ 9

Insertion Operation (Enqueue) ......................................................................................................................... 10
Putting an element in an Array-Based Queue.............................................................................................. 10
The Putting an element Into a Linked-list-Based Queue ............................................................................. 12
Deletion Operation (Dequeue) .......................................................................................................................... 15
Removing an element from an Array-Based Queue .................................................................................... 15
Removing an element from a Linked-List-Based Queue .............................................................................. 17
Queue Status Checking Operations .................................................................................................................. 19
Peek Operation............................................................................................................................................. 19
(Is) Empty Operation .................................................................................................................................... 21
(Is) Full Operation ......................................................................................................................................... 22
Other support Operations of a Queue .............................................................................................................. 23
Size Operation .............................................................................................................................................. 23
Clear Operation ............................................................................................................................................ 24
Display Operation ......................................................................................................................................... 25
Search Operation.......................................................................................................................................... 27
Complexity of Queue Operations ...................................................................................................................... 30

More on Deque........................................................................................................................................ 30
Operations on a DeQue..................................................................................................................................... 31
Memory Representation of a Deque................................................................................................................. 31
Implementation of a DeQue using a Circular Queue ........................................................................................ 31
Enqueue at Front .......................................................................................................................................... 31
Dequeue at Rear........................................................................................................................................... 32
Peeking at Rear ............................................................................................................................................. 33
Processing a Circular Deque ......................................................................................................................... 33
Implementation of a Deque using a Doubly Linked List ................................................................................... 33
 Insertion at Front.......................................................................................................................................... 33
Insertion at Rear ........................................................................................................................................... 34
Deletion from Front ...................................................................................................................................... 35
Deletion from Rear ....................................................................................................................................... 35

Real Life Examples ................................................................................................................................... 36

Stack vs Queues ....................................................................................................................................... 37

Summary ................................................................................................................................................. 38
What Comes Later ............................................................................................................................................ 39

Exercises.................................................................................................................................................. 39
 OVERVIEW, CONCEPTS AND THE QUEUE ADT

A queue is an abstract data type that represents a collection of objects, called elements. A queue ADT
allows insertion operation at one end of the queue and deletion operation at another end. At any given
time, we can access the front element of the queue and the back of the queue. Hence, the element
which is placed first is accessed first.

A queue is empty when it contains no elements. Like with stack, to efficiently utilise a queue, we need
to check the status of queue.

The queue data structure can be implemented using arrays (usually static arrays) or linked lists (usually
singly linked list). An array implemented queue can organise only a limited number of elements, i.e.,
the queue has a static (fixed) size. A linked list implemented queue can organise an unlimited number
of elements, i.e., the queue has a dynamic size.

• A queue is a linear data structure whose operations are done based on the FIFO, “first-in”,
“first-out”, (or LILO, “last-in”, “last out”) principle. This means that the least recently added
elements in the queue are removed first.
• In a queue, elements are added at the end of the queue and removed from the beginning of
the queue.
• A queue is a structure that maintains two pointers. One pointer references the element that
was least recently added in the queue, this pointer is called 𝒇𝒓𝒐𝒏𝒕 (or head). And the other is
called rear (or tail), and it references the element that is most recently added to the queue.
• In queue terminology, insertion operation is called 𝒆𝒏𝒒𝒖𝒆𝒖𝒆 , and removal operation is
called 𝒅𝒆𝒒𝒖𝒆𝒖𝒆.
• The number of elements currently organised in the queue is referred to as its 𝒔𝒊𝒛𝒆.
• For a static queue, the total number of elements that can be enqueued into the queue is called
its 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚.
• If the static queue is full and does not contain enough space to accept the element to be
enqueued, the queue is then considered to be in an 𝒐𝒗𝒆𝒓𝒇𝒍𝒐𝒘 state.
• If a queue has no element, it is known as an 𝒆𝒎𝒑𝒕𝒚 𝒒𝒖𝒆𝒖𝒆. For an 𝒆𝒎𝒑𝒕𝒚 𝒒𝒖𝒆𝒖𝒆, both
𝒇𝒓𝒐𝒏𝒕 and the 𝒓𝒆𝒂𝒓 are −𝟏 (for an array implemented queue), or 𝒏𝒖𝒍𝒍 (for a linked list
implemented queue).
• If the queue is empty and a dequeue operation is attempted on it, the queue is then considered
to be in an 𝒖𝒏𝒅𝒆𝒓𝒇𝒍𝒐𝒘 state.

SPECIFYING A QUEUE ADT

The common set of operations that can be performed on a queue are:

• A constructor for creating an empty queue.

• Enqueue: adds an element to the rear of the queue, if it is not full.
• Dequeue: removes an element from the front of the queue, if the queue is not empty.
• Peek: If queue is not empty, it looks at the element at the front of the queue without modifying
the queue.
• isEmpty or empty: checks if the queue is empty, and only returns true if the queue is empty.
• isFull or full: Checks if a static queue is full and returns true if the queue is full. This behaviour
is only applicable for a static queue.
• Size: returns the size of the queue.
 REPRESENTATION

. Figure 1 depicts what a typical queue looks like.

front of
queue

dequeue enqueue

rear of
queue

FIGURE 1. SIMPLE REPRESENTATION OF A QUEUE.

How a queue is represented in memory depends on its implementation. The elements in an array-based
queue are organised in contiguous memory locations. Whereas the elements in a linked-list-based
queue are organised in random memory locations and are ordered via the reference links stored in the
nodes.

IMPLEMENTATION

We actualise the queue ADT to turn it into a useable data structure. List structures such as array and
linked list can be used to implement a queue. Representing a queue with arrays or linked lists is a natural
idea. Array implementation of a queue is usually static. And linked list implementation is dynamic and
in general does not become full. Now, we will look at how to use these two list structures to implement
queues.

ARRAY IMPLEMENTATION

Since the array implementation is static, we need to declare the 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 (maximum size, i.e., the
total number of elements the queue can store) of the array ahead of time. We maintain an instance
variable, 𝒔𝒊𝒛𝒆, to keep track of the number of elements in the queue. An array, 𝒂𝒓𝒓𝑸𝒖𝒆𝒖𝒆, that stores
𝒔𝒊𝒛𝒆 elements, with the most recently added element in 𝒂𝒓𝒓𝑺𝒕𝒂𝒄𝒌[𝒔𝒊𝒛𝒆 − 𝟏] and the least recently
added element in 𝒂𝒓𝒓𝑺𝒕𝒂𝒄𝒌[𝟎] . This principle allows us to insert at the end of the queue in
𝒂𝒓𝒓𝑺𝒕𝒂𝒄𝒌[𝒔𝒊𝒛𝒆], and delete elements at the start of the array in 𝒂𝒓𝒓𝑺𝒕𝒂𝒄𝒌[𝟎] without moving any
other elements in the queue. As 𝑓𝑟𝑜𝑛𝑡 is usually the index of the first element in the queue and 𝑟𝑒𝑎𝑟,
the index of the last element, we can compute 𝑠𝑖𝑧𝑒 by adding 1 to 𝑟𝑒𝑎𝑟 − 𝑠𝑖𝑧𝑒, i.e., 𝒔𝒊𝒛𝒆 = 𝒓𝒆𝒂𝒓 −
𝒇𝒓𝒐𝒏𝒕 + 𝟏. So, we do not need to keep incrementing or decrementing 𝑠𝑖𝑧𝑒 with every enqueue or
dequeue operation. When the queue is full, 𝑟𝑒𝑎𝑟 will have its maximum value, which is 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 – 𝟏.

A queue can be implemented using array as follows

1. Define an instance variable 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 with specific value.

 2. Declare all the functions used in queue implementation.
3. Create a one-dimensional array with fixed size 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚.
4. Define an integer variable 𝒇𝒓𝒐𝒏𝒕 and initialise it with -1.
5. Define an integer variable 𝒓𝒆𝒂𝒓 and initialise it with -1.
6. Implement method calls for queue operations. We will explore this in more detail, in
the next section of this unit.

PERFORMANCE AND LIMITATIONS

So far, we have been discussing linear (or simple) queue. An array-based queue has fast operations, all
operations are completed in constant time. The implementation has a space complexity of linear time.
Although the array implementation of queue has efficient time, it has a major limitation: capacity is
fixed, which may also lead to the risk of space being wasted. We have to know the upper bound of
growth and allocate memory accordingly, which does not change during execution. If the 𝑟𝑒𝑎𝑟 reaches
the end position of the queue, then there might be a chance that some vacant spaces are left in the
beginning which cannot be reused. The queue has to be reset or a new one with larger capacity has to
be created, and elements of the old one would have to be copied unto the new queue If the array is
full and there is another enqueue operation, we will then encounter an implementation-specific
exception.

The case where the array is full is not an exception defined in the Queue ADT. If the array is filled, then
we have a few options. The first option is to throw an exception. Another way is to disregard the excess
element being enqueued. We can also adopt the concept of a circular structure to circumvent the
limitation of space wastage when rear reaches the limit of the queue.

Thus, a queue can be implemented as a cyclic array.

CIRCULAR QUEUE

Circular Queue is also called a ring-buffer. The circular queue is an improvement over the simple array
queue, it logically connects the last position of the queue to the first position of the queue. It still
operates on the FIFO principle. Its operations and algorithms remain the same as with the simple queue.
To form the circle, the front and rear indices are calculated by performing a modulo operation on
indices (as computed in linear queue) against the capacity of the queue: 𝒇𝒓𝒐𝒏𝒕 = (𝒇𝒓𝒐𝒏𝒕 +
𝟏) % 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 and 𝒓𝒆𝒂𝒓 = (𝒓𝒆𝒂𝒓 + 𝟏) % 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚.

Example 1: Assuming the array size for a simple queue is 8, and we enqueued four elements to 𝑞𝑢𝑒𝑢𝑒
and did three dequeue operations. When we try to enqueue two more elements to 𝑞𝑢𝑒𝑢𝑒, there will
be an 𝒐𝒗𝒆𝒓𝒇𝒍𝒐𝒘 on the second enqueue operation even though we have three empty slots at the
beginning of 𝑞𝑢𝑒𝑢𝑒 as shown in Figure 2.

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

Overflowed
9 10 6 7 5
element
8
0 1 2 3 4 5 6 7

FIGURE 2. A SIMPLE QUEUE WITH EMPTY SPACES AT THE BEGINNING OF THE

QUEUE.
Using a circular queue efficiently reutilises the available space. It doesn’t cause an overflow if there is
available space at the front of the queue. To check for an 𝑜𝑣𝑒𝑟𝑓𝑙𝑜𝑤, all we need to check is the 𝑠𝑖𝑧𝑒
of the queue. If 𝑠𝑖𝑧𝑒 of 𝑞𝑢𝑒𝑢𝑒 is less than 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 of 𝑞𝑢𝑒𝑢𝑒, i.e., 𝑠𝑖𝑧𝑒 < 𝑐𝑎𝑝𝑐𝑖𝑡𝑦, then there is at
least one empty space to add a new element in the queue. Our second enqueue operation will be
successful in a circular queue. The element will be inserted at the first available empty space, in our
example, this will be index 0. Figure 3 shows our queue as a circular queue.

𝒓𝒆𝒂𝒓 𝒇𝒓𝒐𝒏𝒕

8 9 10 6 7 5

0 1 2 3 4 5 6 7

FIGURE 3. A CIRCULAR QUEUE WITH EMPTY SPACES BEING REUSED.

The circular queue works like a ring, hence why it is called the ring-buffer. Figure 4 shows ring view of
our circular queue.

Front

FIGURE 4. SIMPLE RING REPRESENTATION OF THE

CIRCULAR QUEUE FROM FIGURE 3.

Although, the circular queue reuses freed up space from dequeue operations, it does not solve the
problem of limited capacity of the array implementation. An overflow will still occur when the queue is
at full capacity. For example, in our Example 1 above, if we enqueue two more elements and try to
enqueue a third without performing any dequeue operation, our queue will go into overflow.

LINKED LIST IMPLEMENTATION

A linked list can be used to implement a queue, this will give the queue a dynamic capacity. Remember,
even though the elements of the queue are logically linear, physically, they are stored in arbitrarily
memory locations that may not be close to each other. The elements are linked with pointers. A linked-
list-based Implementation of the queue ADT is required when the queue needs to grow and shrink
dynamically (without the overhead of copying the entire list when more memory is needed).
We maintain an instance variable 𝒇𝒓𝒐𝒏𝒕 that stores a reference to the least recently added element,
and 𝒓𝒆𝒂𝒓 that stores a reference to the most recently added element. This notion allows us to insert
elements at the end of the linked list and delete elements at the beginning of it, without accessing links
of any other elements in the linked list. We do not have to worry about the size when the queue grows.
The entire memory pool is the limit for a linked-list-based queue. Since the queue only requires us to
keep track of only a single link for its manipulations (we only move between elements in one direction),
singly linked list is the natural choice for implementing it. The, 𝑓𝑟𝑜𝑛𝑡 is basically the ℎ𝑒𝑎𝑑 pointer of
the linked list and 𝑟𝑒𝑎𝑟 is the 𝑡𝑎𝑖𝑙 pointer. Hence, enqueue is the same as adding a new 𝑡𝑎𝑖𝑙 and
dequeue is equivalent to deleting the ℎ𝑒𝑎𝑑.

To represent a queue using a linked list, we need to set the following things before implementing
actual operations.

1. Define a 𝑵𝒐𝒅𝒆 structure with two attributes 𝒅𝒂𝒕𝒂 and 𝒏𝒆𝒙𝒕

2. Define a 𝑵𝒐𝒅𝒆 pointer 𝒇𝒓𝒐𝒏𝒕 and set it to 𝑵𝑼𝑳𝑳.
3. Define a 𝑵𝒐𝒅𝒆 pointer 𝒓𝒆𝒂𝒓 and set it to 𝑵𝑼𝑳𝑳.
4. Implement method calls for queue operations.

To keep the size operation constant time, we maintain an instance variable, 𝒔𝒊𝒛𝒆, to keep track of the
number of elements in the queue. Whenever we enqueue an element into the queue, we increment
𝑠𝑖𝑧𝑒 and decrement it when we dequeue an element out of the queue.

PRIORITY QUEUE

A priority queue is a type of queue, where every node has some sort of priority attached to it. The nodes
are processed based on this priority. The application of the queue and its implementation defines the
domain of the priority.

• A higher priority element is processed before a lower priority one.

• If two elements are of the same priority, they will be processed according to their sequence in
the queue.
• When deletion is performed, the element which has the highest priority is removed. This
element is usual at the front of the queue.
• When insertion is performed, the priority of the elements determines its position in the queue.
Higher priority elements are placed towards the front of the work, this means, the highest
priority element in the queue will always be the one at the front of the queue. And the lowest
priority will always be at the end of the queue. Since insertions is determined by the priorities
of the elements, the priority queue does not maintain a 𝑡𝑎𝑖𝑙 pointer.
Figure 5 shows an example representation of the priority queue. In this example, the number on the
node denotes the priority of the element, not the value of the element. Also, in this particular case,
larger valued priority indicates higher priority.

5 front

Dequeue 5 3 2 2 1 1

Enqueue

FIGURE 5. A SIMPLE REPRESENTATION OF A PRIORITY QUEUE.

There are two types of priority queue:

• Ascending order priority queue, where a lower numbered priority is considered to have a
higher priority than a larger numbered one.
• Descending order priority queue, where a larger numbered priority is given as having a higher
priority than a lower numbered one.

A priority queue can be implemented using arrays or linked list.

DOUBLE ENDED QUEUE (DEQUE)

A double ended queue also called a deque (pronounced deck) is a queue variant where enqueue and
dequeue operations are done from both ends of the queue. A deque can be implemented with an array
or a linked list.

front
Dequeue Enqueue

6 8 7 9 10

Enqueue Dequeue
rear

FIGURE 6. A SIMPLE REPRESENTATION OF A DEQUE.

Figure 6 depicts a simple deque. We will discuss more on deque in later section of this unit.

BASIC OPERATIONS

As we have mentioned earlier, queue operations may involve initialising the queue, using it and then
de-initialising it. In addition to these, we mentioned the two primary operations of a queue: enqueue
and dequeue. Also, we indicated the need to check the status of the queue using operations such as
peek, full and empty.
Now we study the procedures that make queue usable.

INSERTION OPERATION (ENQUEUE)

The process of placing a new element at the back of a queue is known as an enqueue operation. How
the queue is implemented determines how the enqueue operation is performed.

PUTTING AN ELEMENT IN AN ARRAY-BASED QUEUE

Enqueue operation involves a series of steps:

5. Check if the queue is full.

6. If the queue is 𝑓𝑢𝑙𝑙, produces an error and exit.
7. If the queue is not 𝑓𝑢𝑙𝑙, increments 𝒓𝒆𝒂𝒓 to point to the next empty space.
8. Add new element to the queue location where 𝒓𝒆𝒂𝒓 is pointing.
9. Check if queue was previously empty.
10. If 𝑒𝑚𝑝𝑡𝑦, point 𝑓𝑟𝑜𝑛𝑡 to the new element.

ENQUEUE ALGORITHM FOR AN ARRAY-BASED (SIMPLE) QUEUE

Algorithm Enqueue( 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 )
Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the new element to be added.
Output: A 𝑞𝑢𝑒𝑢𝑒 with a newly enqueued 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 at 𝒓𝒆𝒂𝒓 position, if 𝑞𝑢𝑒𝑢𝑒 is not 𝑓𝑢𝑙𝑙.
Data Structure: An array queue with pointer to the end position, 𝒓𝒆𝒂𝒓 and pointer to the front position,
𝒇𝒓𝒐𝒏𝒕.
Begin
1. If 𝑞𝑢𝑒𝑢𝑒 is 𝑓𝑢𝑙𝑙 Then
2. Print “Queue Overflow!”
3. Exit
4. Else
5. 𝑟𝑒𝑎𝑟 = 𝑟𝑒𝑎𝑟 + 1
6. 𝑞𝑢𝑒𝑢𝑒[𝑟𝑒𝑎𝑟] = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
7. If 𝑞𝑢𝑒𝑢𝑒 was 𝑒𝑚𝑝𝑡𝑦 Then
8. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 + 1
9. End If
10. End If
End

JAVA IMPLEMENTATION OF THE ENQUEUE ALGORITHM

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑒𝑛𝑞𝑢𝑒𝑢𝑒( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {
// 𝐴𝑑𝑑 𝑑𝑎𝑡𝑎 𝑎𝑠 𝑡ℎ𝑒 𝑟𝑒𝑎𝑟 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.

𝒊𝒇( ! 𝑖𝑠𝐹𝑢𝑙𝑙() ) {
𝑟𝑒𝑎𝑟 + +;
𝑞𝑢𝑒𝑢𝑒[𝑟𝑒𝑎𝑟] = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑓𝑟𝑜𝑛𝑡 + +;
}
 𝒆𝒍𝒔𝒆 {
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("𝑂𝑉𝐸𝑅𝐹𝐿𝑂𝑊! 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐹𝑢𝑙𝑙! ");
}
}

HOW ENQUEUING ELEMENTS INTO AN ARRAY-IMPLEMENTED QUEUE WORKS

front = 0
front = -1 Empty queue enqueue 8

rear = -1
rear = 0

front = 0 front = 0
enqueue 7 enqueue 4

8 7 8 7 4

rear = 1 rear = 2

FIGURE 7. SIMPLE REPRESENTATION OF A (ARRAY) QUEUE RUNTIME WITH ENQUEUE OPERATION.

Example 2: Assuming we have an array queue with a capacity of 5 elements and we then add the
elements 8, 7, and 4 at end of the queue (in the same sequence) . Figure 7 shows the state of the
𝑞𝑢𝑒𝑢𝑒 after each enqueue operation. The 𝑟𝑒𝑎𝑟 is usually set as -1 for an empty queue, and the 𝑠𝑖𝑧𝑒 is
of course 0. When we enqueue an element into a queue (array implementation) the 𝑟𝑒𝑎𝑟 is increased
by 1. When we perform an enqueue operation, the 𝑓𝑟𝑜𝑛𝑡 pointer is not usually affected except if the
queue was empty before the enqueue operation started. In this case, the 𝑓𝑟𝑜𝑛𝑡 will be -1, and we will
need to increase it by 1 to point to the location of the newly inserted element. The process of enqueuing
a queue is shown in Figure 7.

ENQUEUING A CIRCULAR QUEUE

The enqueuing process of a circular queue is almost the same with that of a simple queue. The
difference is in how we perform the 𝑟𝑒𝑎𝑟 and 𝑓𝑟𝑜𝑛𝑡 pointers increment. After incrementing as for
simple queue, we will then perform a modulo operation against the capacity of the queue. Thus, 𝑟𝑒𝑎𝑟
is incremented as 𝑟𝑒𝑎𝑟 = (𝑟𝑒𝑎𝑟 + 1) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 , and 𝑓𝑟𝑜𝑛𝑡 as 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 +
1 % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦. Another difference is, to keep track of the 𝑠𝑖𝑧𝑒 of the queue, we need to increase it by
1 after each enqueue operation.

Example 3: The following is the Java implementation of the enqueuing a circular queue.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑒𝑛𝑞𝑢𝑒𝑢𝑒( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {

// 𝐴𝑑𝑑 𝑑𝑎𝑡𝑎 𝑎𝑠 𝑡ℎ𝑒 𝑟𝑒𝑎𝑟 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.

𝒊𝒇( ! 𝑖𝑠𝐹𝑢𝑙𝑙() ) {
 𝑟𝑒𝑎𝑟 = (𝑟𝑒𝑎𝑟 + 1)% 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
𝑞𝑢𝑒𝑢𝑒[𝑟𝑒𝑎𝑟] = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑓𝑟𝑜𝑛𝑡 = (𝑓𝑟𝑜𝑛𝑡 + 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
}

𝑠𝑖𝑧𝑒 + +;
𝒆𝒍𝒔𝒆 {
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("𝑂𝑉𝐸𝑅𝐹𝐿𝑂𝑊! 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐹𝑢𝑙𝑙! ");
}
}

THE PUTTING AN ELEMENT INTO A LINKED-LIST-BASED QUEUE

If a linked list is used to implement the queue ADT, we check whether the queue is empty but NOT full.
And we dynamically allocate the empty space needed for the new element.

1. Create a new node.

2. Set the 𝑣𝑎𝑙𝑢𝑒 of the new node as the element.
3. Set the successor of the new node as NULL.
4. Check whether the 𝑞𝑢𝑒𝑢𝑒 is 𝑒𝑚𝑝𝑡𝑦
5. If 𝑒𝑚𝑝𝑡𝑦, set the newly created node as both the new 𝑓𝑟𝑜𝑛𝑡 and the new 𝑟𝑒𝑎𝑟.
6. If not 𝑒𝑚𝑝𝑡𝑦, set the 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑜𝑟 (𝑛𝑒𝑥𝑡 𝑙𝑖𝑛𝑘) of 𝑟𝑒𝑎𝑟 to the new node.
7. Set the newly created node as the new 𝑟𝑒𝑎𝑟.
8. Increment the 𝑠𝑖𝑧𝑒 of the queue by 1.

ENQUEUE ALGORITHM FOR A LINKED-LIST-BASED QUEUE

Algorithm Enqueue(element)
Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the new element to be enqueued.
Output: A 𝒒𝒖𝒆𝒖𝒆 with a newly enqueued 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 at the 𝒓𝒆𝒂𝒓 position.
Data Structure: A singly linked list structure whose pointer to the head is known from 𝒉𝒆𝒂𝒅, pointer to
the tails is known from 𝒕𝒂𝒊𝒍, 𝒇𝒓𝒐𝒏𝒕 is the pointer to the first node, 𝒓𝒆𝒂𝒓 is the pointer to the
last node and 𝒔𝒊𝒛𝒆 is the number of elements in 𝒒𝒖𝒆𝒖𝒆.
Begin
/* create a new node with the given value, element */
1. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 = 𝑛𝑒𝑤 𝑆𝐿𝐿𝑁𝑜𝑑𝑒( )
2. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑑𝑎𝑡𝑎 = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
3. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 = 𝑁𝑈𝐿𝐿
/* Check whether 𝑞𝑢𝑒𝑢𝑒 is 𝒆𝒎𝒑𝒕𝒚
(𝑓𝑟𝑜𝑛𝑡 == 𝑁𝑈𝐿𝐿 OR 𝑓𝑟𝑜𝑛𝑡 = 𝑟𝑒𝑎𝑟 → 𝑛𝑒𝑥𝑡) */
4. If 𝑞𝑢𝑒𝑢𝑒 is 𝑒𝑚𝑝𝑡𝑦 Then
5. 𝑓𝑟𝑜𝑛𝑡 = 𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
/* Add node to the front of the list*/
6. Else
7. 𝑟𝑒𝑎𝑟 → 𝑛𝑒𝑥𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
8. 𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
9. End If
10. 𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 + 1
11.
End

JAVA IMPLEMENTATION OF THE ENQUEUE ALGORITHM

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑒𝑛𝑞𝑢𝑢𝑒 ( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {

// 𝐴𝑑𝑑 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑠 𝑡ℎ𝑒 𝑟𝑒𝑎𝑟 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒.

𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒 𝑜𝑙𝑑𝑅𝑒𝑎𝑟 = 𝑟𝑒𝑎𝑟;
𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤 𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒( 𝑒𝑙𝑒𝑚𝑒𝑛𝑡, 𝒏𝒖𝒍𝒍 );
𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑓𝑟𝑜𝑛𝑡 = 𝑟𝑒𝑎𝑟;
}
𝑒𝑙𝑠𝑒 {
𝑜𝑙𝑑𝑅𝑒𝑎𝑟. 𝑛𝑒𝑥𝑡 = 𝑟𝑒𝑎𝑟;
}
𝑠𝑖𝑧𝑒 + +;
}

HOW ENQUEUING ELEMENTS ONTO A LINKED-LIST-IMPLEMENTED QUEUE WORKS

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓 𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

8
𝑵𝑼𝑳𝑳

Empty queue enqueue 8

𝑵𝑼𝑳𝑳

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

8 7

enqueue 7

𝑵𝑼𝑳𝑳

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

8 7 4

enqueue 4

𝑵𝑼𝑳𝑳

FIGURE 8. SIMPLE REPRESENTATION OF A (LINKED LIST) ARRAY RUNTIME WITH ENQUEUE OPERATION.

Example 4: Assuming we implemented a queue using linked list, and added the elements 8, 7 and 4 at
its end. Figure 8 shows the state of the queue when it is created, as well as after each enqueue
operation. For an empty queue, the 𝑓𝑟𝑜𝑛𝑡 and the 𝑟𝑒𝑎𝑟 point to 𝑛𝑢𝑙𝑙, and the 𝑠𝑖𝑧𝑒 is set to 0. When
we enqueue an element into a queue, the successor of 𝑟𝑒𝑎𝑟 is set to the new element and the new
element becomes the new 𝒓𝒆𝒂𝒓.

ENQUEUING A PRIORITY QUEUE

Adding elements to a linked list priority queue, works slightly different from a standard linked list queue.
A linked list priority queue only maintains the front pointer, because insertion locations are determined
by priority of the element. The node of the element has an extra attribute, priority.

Example 5: Let’s assume, the priority of an element is an integer, and the lower the value of the integer
the greater the priority. The following is the steps we will need to insert a new element into the priority
queue.

1. Create new node, set its value as the new element, and its priority as the priority of the new
element
2. Check whether the queue is empty. If 𝒇𝒓𝒐𝒏𝒕 is null, then the queue is empty.
3. If 𝑒𝑚𝑝𝑡𝑦, insert the new element as 𝑓𝑟𝑜𝑛𝑡 of the queue.
4. If not empty, check whether the priority of the 𝑓𝑟𝑜𝑛𝑡 element is larger than the priority of the
new element.
5. If priority of 𝑓𝑟𝑜𝑛𝑡 is larger, insert the new element at the 𝑓𝑟𝑜𝑛𝑡 of the queue. Set the
successor of the new element to point to 𝑓𝑟𝑜𝑛𝑡 and make the new element to be the new
𝑓𝑟𝑜𝑛𝑡.
6. If priority of 𝑓𝑟𝑜𝑛𝑡 is lower, traverse the queue to find an element that has a larger priority
than the new element, and insert the new element before it.
7. Create a temporary node, 𝒄𝒖𝒓𝒓𝒆𝒏𝒕, to keep track of the element we are currently processing.
Copy 𝑓𝑟𝑜𝑛𝑡 to it.
8. While 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 is not the last node( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡 is not null) and the priority of its
successor is less than the priority of the new element ( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 is less than
element’s priority), move 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 forward along the queue (𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 → 𝑛𝑒𝑥𝑡).
9. When we get to the end of the queue or find an element with a larger priority, we add the
element there. Set successor of the new element to the successor of 𝑐𝑢𝑟𝑟𝑒𝑛𝑡. Set the new
element as the new successor of 𝑐𝑢𝑟𝑟𝑒𝑛𝑡.
10. Increase 𝑠𝑖𝑧𝑒 of the queue by 1.

The following is the Java implementation of the enqueue method for a priority queue.

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑒𝑛𝑞𝑢𝑒𝑢𝑒 ( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡, 𝑖𝑛𝑡 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) {

// 𝐴𝑑𝑑 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑠 𝑎 𝑛𝑒𝑤 𝑛𝑜𝑑𝑒 𝑖𝑛 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.

𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡 = 𝒏𝒆𝒘 𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒( 𝑒𝑙𝑒𝑚𝑒𝑛𝑡, 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦, 𝒏𝒖𝒍𝒍 );
𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤 𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒( 𝑒𝑙𝑒𝑚𝑒𝑛𝑡, 𝒏𝒖𝒍𝒍 );
𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡;
}
𝒆𝒍𝒔𝒆 {
𝒊𝒇( 𝑓𝑟𝑜𝑛𝑡. 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 > 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 ){
𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = 𝑓𝑟𝑜𝑛𝑡;
𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡;
}
𝒆𝒍𝒔𝒆 {
// 𝑇𝑟𝑎𝑣𝑒𝑟𝑠𝑒 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒 𝑎𝑛𝑑 𝑓𝑖𝑛𝑑 𝑎
 // 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑡𝑜 𝑖𝑛𝑠𝑒𝑟𝑡 𝑛𝑒𝑤 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝒕𝒉𝒊𝒔. 𝑓𝑟𝑜𝑛𝑡;
𝒘𝒉𝒊𝒍𝒆( 𝑐𝑢𝑟𝑟𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 ! = 𝒏𝒖𝒍𝒍 &&
𝑐𝑢𝑟𝑟𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡. 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 < 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦) {
𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑁𝑜𝑑𝑒. 𝑛𝑒𝑥𝑡;
}

𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡;

𝑐𝑢𝑟𝑟𝑒𝑛𝑡. 𝑛𝑒𝑥𝑡 = 𝑛𝑒𝑤𝐸𝑙𝑒𝑚𝑒𝑛𝑡;
}
}

𝑠𝑖𝑧𝑒 + +;
}

DELETION OPERATION (DEQUEUE)

The process of removing an element from a queue is called a dequeue operation. Similar with enqueue
operation, the operation is determined by the implementation of the queue.

REMOVING AN ELEMENT FROM AN ARRAY-BASED QUEUE

Since in an array-based queue the element is always removed from the front position. The dequeue
operation does not take any value as input. We can use the following steps to dequeue an element
from the queue.

1. Check whether 𝒒𝒖𝒆𝒖𝒆 is 𝒆𝒎𝒑𝒕𝒚.

2. If it is 𝒆𝒎𝒑𝒕𝒚, throw an exception and exit.
3. If it is not 𝒆𝒎𝒑𝒕𝒚, then delete 𝒒𝒖𝒆𝒖𝒆[𝒇𝒓𝒐𝒏𝒕] and move 𝒇𝒓𝒐𝒏𝒕 to point to the next element
in the queue.
4. Return the element deleted.

DEQUEUE ALGORITHM FOR AN ARRAY-BASED QUEUE

Algorithm Dequeue()
Input: none.
Output: Removed element is stored in 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, if 𝑞𝑢𝑒𝑢𝑒 is not empty.
Data Structure: An array, 𝒒𝒖𝒆𝒖𝒆, with 𝒇𝒓𝒐𝒏𝒕 as a pointer to the index of the first element.
Begin

1. If 𝑒𝑚𝑝𝑡𝑦 is 𝑒𝑚𝑝𝑡𝑦 Then

2. Print “Quick Underflow!”
3. Exit
4. Else
5. 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡]
6. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 + 1
7. Return 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
8. End If

End
 JAVA IMPLEMENTATION OF THE DEQUEUE ALGORITHM
𝒑𝒖𝒃𝒍𝒊𝒄 𝑂𝑏𝑗𝑒𝑐𝑡 𝑑𝑒𝑞𝑢𝑒𝑢𝑒() {

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("𝑈𝑁𝐷𝐸𝑅𝐹𝐿𝑂𝑊! 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦! ");
𝒓𝒆𝒕𝒖𝒓𝒏 𝑛𝑢𝑙𝑙
}

// 𝑅𝑒𝑚𝑜𝑣𝑒 𝑎𝑛𝑑 𝑟𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑓𝑟𝑜𝑚 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒.

𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡];
𝑓𝑟𝑜𝑛𝑡 + +;

𝒓𝒆𝒕𝒖𝒓𝒏 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

HOW DEQUEUING ELEMENTS FROM AN ARRAY-IMPLEMENTED QUEUE WORKS

front = 0
Initial state

8 7 4

rear = 2

front = 1 front = 2
dequeue dequeue

7 4 4

rear = 2 rear = 2

FIGURE 9. SIMPLE REPRESENTATION OF A (ARRAY) QUEUE RUNTIME WITH DEQUEUE

OPERATION.

Example 6: Let’s continue to manipulate our queue from Example 2. Let’s perform two 𝑑𝑒𝑞𝑢𝑒𝑢𝑒
operations on it. Each time we 𝑑𝑒𝑞𝑢𝑒𝑢𝑒 an element, 𝑓𝑟𝑜𝑛𝑡 is increased by 1. Rear never changes in a
dequeue operation. Figure 9 shows the state of the queue after each 𝑑𝑒𝑞𝑢𝑒𝑢𝑒 operation.

If we perform a third dequeue, 𝑓𝑟𝑜𝑛𝑡 will become 3. And we will not be able to do anymore dequeue
operations until, at least one enqueue operation occurs.

DEQUEUING A CIRCULAR QUEUE

Similar to the enqueuing operation of a circular queue, its dequeuing operation is almost identical to
dequeuing a simple queue. The dissimilarity is how front is adjusted and the size of the queue is
decreased by 1 when an element is dequeued. The 𝑓𝑟𝑜𝑛𝑡 is adjusted the same way as in enqueuing
operation, i.e., 𝑓𝑟𝑜𝑛𝑡 = (𝑓𝑟𝑜𝑛𝑡 + 1) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦.

The following is the Java implementation of the dequeuing a circular queue.

𝒑𝒖𝒃𝒍𝒊𝒄 𝑂𝑏𝑗𝑒𝑐𝑡 𝑑𝑒𝑞𝑢𝑒𝑢𝑒() {
 𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("𝑈𝑁𝐷𝐸𝑅𝐹𝐿𝑂𝑊! 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦! ");
𝒓𝒆𝒕𝒖𝒓𝒏 𝑛𝑢𝑙𝑙
}

// 𝑅𝑒𝑚𝑜𝑣𝑒 𝑎𝑛𝑑 𝑟𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑓𝑟𝑜𝑚 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒.

𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡];
𝑓𝑟𝑜𝑛𝑡 = (𝑓𝑟𝑜𝑛𝑡 + 1) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;

𝑠𝑖𝑧𝑒 − −;

𝒓𝒆𝒕𝒖𝒓𝒏 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}

REMOVING AN ELEMENT FROM A LINKED-LIST-BASED QUEUE

As deletion is always done at the head of the linked list, the dequeue operation does not require an
input value. We can use the following steps to delete a node from the queue.

1. Check whether 𝒒𝒖𝒆𝒖𝒆 is 𝒆𝒎𝒑𝒕𝒚

2. If it is 𝒆𝒎𝒑𝒕𝒚, then throw an exception and exit.
3. If it is not 𝒆𝒎𝒑𝒕𝒚, then define a new object to copy the value of the 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 at the front
position.
4. Then set 𝒔𝒖𝒄𝒄𝒆𝒔𝒔𝒐𝒓 of 𝒇𝒓𝒐𝒏𝒕 to be the new 𝒇𝒓𝒐𝒏𝒕, i.e., 𝒇𝒓𝒐𝒏𝒕 = 𝒇𝒓𝒐𝒏𝒕 → 𝒏𝒆𝒙𝒕
5. Check whether the queue has become empty
6. If 𝒒𝒖𝒆𝒖𝒆 is 𝒆𝒎𝒑𝒕𝒚, set 𝒓𝒆𝒂𝒓 to 𝒏𝒖𝒍𝒍. Otherwise do nothing.
7. Decrease 𝒔𝒊𝒛𝒆 of the queue by 1.
8. Return 𝒆𝒍𝒆𝒎𝒆𝒏𝒕.

DEQUEUE ALGORITHM FOR A LINKED-LIST-BASED QUEUE

Algorithm Dequeue()
Input: None.
Output: Removed element is stored in 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, if 𝒒𝒖𝒆𝒖𝒆 is not 𝒆𝒎𝒑𝒕𝒚.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node, point to the last node is known as 𝒓𝒆𝒂𝒓, pointer to the last node and
𝒔𝒊𝒛𝒆 is the number of elements in 𝒒𝒖𝒆𝒖𝒆.
Begin

1. If 𝑞𝑢𝑒𝑢𝑒 is 𝑒𝑚𝑝𝑡𝑦 Then

2. Print “Queue Underflow!”
3. Exit
4. Else
5. 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑑𝑎𝑡𝑎
6. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥t
7. If 𝑞𝑢𝑒𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then
8. 𝑟𝑒𝑎𝑟 = 𝑛𝑢𝑙𝑙
9. End if
12. 𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 – 1
13. Return 𝑒𝑙𝑒𝑚𝑒𝑛𝑡
 14. End if

End

JAVA IMPLEMENTATION OF THE DEQUEUE ALGORITHM

𝒑𝒖𝒃𝒍𝒊𝒄 𝑂𝑏𝑗𝑒𝑐𝑡 𝑑𝑒𝑞𝑢𝑒𝑢𝑒() {

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("𝑈𝑁𝐷𝐸𝑅𝐹𝐿𝑂𝑊! 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦! ");
𝒓𝒆𝒕𝒖𝒓𝒏 𝑛𝑢𝑙𝑙;
}

// 𝑅𝑒𝑚𝑜𝑣𝑒 𝑎𝑛𝑑 𝑟𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑓𝑟𝑜𝑚 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒.

𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑑𝑎𝑡𝑎;
𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥𝑡;

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑟𝑒𝑎𝑟 = 𝑛𝑢𝑙𝑙;
}

𝑠𝑖𝑧𝑒 − −;

𝒓𝒆𝒕𝒖𝒓𝒏 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}
 HOW DEQUEUING ELEMENTS OUT OF A LINKED-LIST-IMPLEMENTED QUEUE WORKS

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

8 7 4

Initial state

𝑵𝑼𝑳𝑳

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

8 7

dequeue

𝑵𝑼𝑳𝑳

𝒇𝒓𝒐𝒏𝒕 𝒓𝒆𝒂𝒓

dequeue
𝑵𝑼𝑳𝑳

FIGURE 10. SIMPLE REPRESENTATION OF A (LINKED LIST) QUEUE RUNTIME WITH DEQUEUE
OPERATION.

Example 7: Continuing with our queue Example 4, we will perform two 𝑑𝑒𝑞𝑢𝑒𝑢𝑒 operations on the
𝑞𝑢𝑒𝑢𝑒. Figure 10 shows the state of the queue after each dequeue operation.

DEQUEUING A PRIORITY QUEUE

Removing elements from a linked list priority queue works the same way as a standard linked list queue.
The only variance is in priority queue we do not reset 𝑟𝑒𝑎𝑟 since it is not defined.

QUEUE STATUS CHECKING OPERATIONS

As we have discussed, we need functionality of checking the status of the queue to be able to use the
structure efficiently. In this section we will learn the secondary operations we need to support the
primary queue functions. These operations do not alter the queue. They access the queue without
transforming it.

PEEK OPERATION

The peek operation provides a quick look at the front position of the queue. It returns the element at
𝑓𝑟𝑜𝑛𝑡 without removing it from the queue.
 PEEKING INTO AN ARRAY-BASED QUEUE
Algorithm Peek()
Input: None.
Output: Element at the front position is stored in 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, if 𝒒𝒖𝒆𝒖𝒆 is not 𝒆𝒎𝒑𝒕𝒚.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒇𝒓𝒐𝒏𝒕, pointer to the first element in the array.
Begin

1. If 𝑞𝑢𝑒𝑢𝑒 is 𝑒𝑚𝑝𝑡𝑦 Then

2. Print “Queue is Empty!”
3. Exit
4. Else
5. Return 𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡]

End

JAVA IMPLEMENTATION OF THE PEEK OPERATION FOR ARRAY -BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑝𝑒𝑒𝑘() {
𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛( "𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦! " );
𝒓𝒆𝒕𝒖𝒓𝒏 𝑛𝑢𝑙𝑙;
}
// 𝑅𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑡 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑜𝑓 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.
𝒓𝒆𝒕𝒖𝒓𝒏 𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡];
}

PEEKING INTO A LINKED-LIST-BASED QUEUE

Algorithm Peek()
Input: None.
Output: Element at the front position is stored in 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, if 𝒒𝒖𝒆𝒖𝒆 is not 𝒆𝒎𝒑𝒕𝒚.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node in 𝒒𝒖𝒆𝒖𝒆.
Begin

1. If 𝑞𝑢𝑒𝑢𝑒 is 𝑒𝑚𝑝𝑡𝑦 Then

2. Print “Queue is Empty!”
3. Exit
4. Else
5. Return 𝑓𝑟𝑜𝑛𝑡 → 𝑑𝑎𝑡𝑎

End

JAVA IMPLEMENTATION OF THE PEEK OPERATION FOR LINKED -LIST-BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑝𝑒𝑒𝑘() {
𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛( "𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦! " );
𝒓𝒆𝒕𝒖𝒓𝒏 𝑛𝑢𝑙𝑙;
}
 // 𝑅𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑡 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑜𝑓 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.
𝒓𝒆𝒕𝒖𝒓𝒏 𝑓𝑟𝑜𝑛𝑡. 𝑑𝑎𝑡𝑎;
}

(IS) EMPTY OPERATION

The Is Empty functionality returns true only when there are zero elements in the queue.

TESTING WHETHER AN ARRAY-BASED QUEUE IS EMPTY

Algorithm IsEmpty()
Input: None.
Output: 𝒕𝒓𝒖𝒆, if 𝒒𝒖𝒆𝒖𝒆 is 𝒆𝒎𝒑𝒕𝒚, otherwise return 𝒇𝒂𝒍𝒔𝒆.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒇𝒓𝒐𝒏𝒕, pointer to the first element in the array and
𝒓𝒆𝒂𝒓, pointer to the last element in the array.
Begin

1. If 𝑓𝑟𝑜𝑛𝑡 = −1 Or 𝑓𝑟𝑜𝑛𝑡 > 𝑟𝑒𝑎𝑟 Then

2. [queue has no elements]
3. Return 𝑡𝑟𝑢𝑒
4. Else
5. Return 𝑓𝑎𝑙𝑠𝑒

End

JAVA IMPLEMENTATION OF THE ISEMPTY OPERATION FOR ARRAY -BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒃𝒐𝒐𝒍𝒆𝒂𝒏 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() {
𝒊𝒇( 𝑓𝑟𝑜𝑛𝑡 == −1 || 𝑓𝑟𝑜𝑛𝑡 > 𝑟𝑒𝑎𝑟 ) {
// 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦!
𝒓𝒆𝒕𝒖𝒓𝒏 𝑡𝑟𝑢𝑒;
}

𝒓𝒆𝒕𝒖𝒓𝒏 𝑓𝑎𝑙𝑠𝑒
}

HOW TO DETERMINE WHETHER A CIRCULAR QUEUE IS EMPTY

The nature of a circular queue necessitates checking for emptiness by testing the equality of 𝑠𝑖𝑧𝑒 to 0,
i.e., if( 𝑠𝑖𝑧𝑒 == 0 ).

TESTING WHETHER A LINKED-LIST-BASED QUEUE IS EMPTY

Algorithm IsEmpty()
Input: None.
Output: 𝒕𝒓𝒖𝒆, if 𝒒𝒖𝒆𝒖𝒆 is 𝒆𝒎𝒑𝒕𝒚, otherwise return 𝒇𝒂𝒍𝒔𝒆.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node in the linked list and pointer to the 𝒕𝒂𝒊𝒍 is known from 𝒓𝒆𝒂𝒓, pointer
to the last node in the linked list.
Begin

1. If 𝑓𝑟𝑜𝑛𝑡 → 𝑑𝑎𝑡𝑎 = 𝑛𝑢𝑙𝑙 Or 𝑓𝑟𝑜𝑛𝑡 = 𝑟𝑒𝑎𝑟 → 𝑛𝑒𝑥𝑡 Then

2. [queue has no elements]
 3. Return 𝑡𝑟𝑢𝑒
4. Else
5. Return 𝑓𝑎𝑙𝑠𝑒

End

JAVA IMPLEMENTATION OF THE ISEMPTY OPERATION FOR LINKED -LIST-BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒃𝒐𝒐𝒍𝒆𝒂𝒏 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() {
𝒊𝒇( 𝑓𝑟𝑜𝑛𝑡. 𝑑𝑎𝑡𝑎 == 𝑛𝑢𝑙𝑙 || 𝑓𝑟𝑜𝑛𝑡 = 𝑟𝑒𝑎𝑟. 𝑛𝑒𝑥𝑡) ){
// 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦!
𝒓𝒆𝒕𝒖𝒓𝒏 𝑡𝑟𝑢𝑒;
}

𝒓𝒆𝒕𝒖𝒓𝒏 𝑓𝑎𝑙𝑠𝑒;
}

HOW TO DETERMINE WHETHER A PRIORITY QUEUE IS EMPTY

Owing to the fact that a priority queue does not maintain a rear, the second condition is irrelevant.
So, the only test parameter for a priority queue is, 𝒊𝒇( 𝑓𝑟𝑜𝑛𝑡. 𝑑𝑎𝑡𝑎 == 𝑛𝑢𝑙𝑙 ).

(IS) FULL OPERATION

The Is Full functionality is required only for queue with a fixed 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦. It returns 𝑡𝑟𝑢𝑒 only when the
queue is filled to 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦.

TESTING WHETHER AN ARRAY-BASED QUEUE IS FULL

Algorithm IsFull()
Input: None.
Output: 𝒕𝒓𝒖𝒆, if 𝒒𝒖𝒆𝒖𝒆 is 𝒇𝒖𝒍𝒍, otherwise return 𝒇𝒂𝒍𝒔𝒆.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒓𝒆𝒂𝒓, pointer to the last element in the array and
𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 is the maximum number of elements the array can hold.
Begin

1. If 𝑟𝑒𝑎𝑟 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 − 1 Then

2. [queue has is filled to maximum size]
3. Return 𝑡𝑟𝑢𝑒
4. Else
5. Return 𝑓𝑎𝑙𝑠𝑒

End

JAVA IMPLEMENTATION OF THE ISFULL OPERATION FOR ARRAY -BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒃𝒐𝒐𝒍𝒆𝒂𝒏 𝑖𝑠𝐹𝑢𝑙𝑙() {
𝒊𝒇( 𝑟𝑒𝑎𝑟 == 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 − 1 ) ){
// 𝑄𝑢𝑒𝑢𝑒 𝑖𝑠 𝐹𝑢𝑙𝑙!
𝒓𝒆𝒕𝒖𝒓𝒏 𝑡𝑟𝑢𝑒;
}
 𝒓𝒆𝒕𝒖𝒓𝒏 𝑓𝑎𝑙𝑠𝑒;
}

HOW TO DETERMINE WHETHER A CIRCULAR QUEUE IS FULL

Due to the characteristics of a circular queue, the queue is checked for fullness by testing the equality
of 𝑠𝑖𝑧𝑒 to 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦, i.e., 𝒊𝒇( 𝑠𝑖𝑧𝑒 == 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 ).

OTHER SUPPORT OPERATIONS OF A QUEUE

In addition to the functions we have mentioned, we can add more functionality to the queue. For
example, we have mentioned that maintaining an instance variable to keep track of 𝑠𝑖𝑧𝑒 in a linked-
list-based queue can improve the efficiency of computing the size from linear time to constant time.
We can provide a functionality to return the size of the queue. Another example is, we may provide
functionality for operations we often do with our queue such as resetting (emptying) the queue,
displaying the content of the queue or searching through the queue to test whether an element exists
in it.

SIZE OPERATION

The size operation returns the number of current elements in the queue.

SIZING AN ARRAY-BASED QUEUE

Algorithm Size()
Input: None.
Output: 𝒔𝒊𝒛𝒆, the number of elements currently in the array.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒇𝒓𝒐𝒏𝒕, pointer to the first element in the array and
𝒓𝒆𝒂𝒓, pointer to the last element in the array. 𝒔𝒊𝒛𝒆 is 0, when then queue is empty.
Begin

1. If 𝑞𝑢𝑒𝑢𝑒 is 𝑒𝑚𝑝𝑡𝑦 Then

2. Return 𝑠𝑖𝑧𝑒
3. Else
4. Return ( 𝑟𝑒𝑎𝑟 − 𝑓𝑟𝑜𝑛𝑡 ) + 1
5. End If

End

JAVA IMPLEMENTATION OF THE SIZE OPERATION FOR ARRAY -BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑠𝑖𝑧𝑒() {
𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() )
𝒓𝒆𝒕𝒖𝒏 𝑠𝑖𝑧𝑒;
𝒆𝒍𝒔𝒆
𝒓𝒆𝒕𝒖𝒏 ( 𝑟𝑒𝑎𝑟 − 𝑓𝑟𝑜𝑛𝑡) + 1;
}

SIZING A CIRCULAR QUEUE

Owing to the nature of a circular queue, the size() function simply returns the value of 𝑠𝑖𝑧𝑒 attribute of
the queue.

SIZING A LINKED-LIST-BASED QUEUE

Algorithm Size()
Input: None.
Output: 𝒔𝒊𝒛𝒆, the number of elements currently in the linked list.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node in the linked list; and 𝒔𝒊𝒛𝒆 is the number of elements in the linked list.
Begin

1. Return 𝑠𝑖𝑧𝑒

End

JAVA IMPLEMENTATION OF THE SIZE OPERATION FOR LINKED -LIST-BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑠𝑖𝑧𝑒() {
𝒓𝒆𝒕𝒖𝒏 𝑠𝑖𝑧𝑒;
}

CLEAR OPERATION

The clear operation transforms the queue. It resets 𝑓𝑟𝑜𝑛𝑡 and 𝑟𝑒𝑎𝑟 to their default value, -1 or 𝑛𝑢𝑙𝑙
for array-based queue and linked-list-based queue respectively.

CLEARING AN ARRAY-BASED QUEUE

Algorithm clear()
Input: None.
Output: None.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒇𝒓𝒐𝒏𝒕, pointer to the first element in the array and
𝒓𝒆𝒂𝒓, pointer to the last element in the array.
Begin

1. 𝑓𝑟𝑜𝑛𝑡 = −1
2. 𝑟𝑒𝑎𝑟 = −1

End

JAVA IMPLEMENTATION OF THE CLEAR OPERATION FOR ARRAY -BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑐𝑙𝑒𝑎𝑟() {
// 𝑀𝑎𝑘𝑒 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒 𝑒𝑚𝑝𝑡𝑦
𝑓𝑟𝑜𝑛𝑡 = −1 ;
𝑓𝑟𝑜𝑛𝑡 = −1 ;
}

RESETTING A CIRCULAR QUEUE

The nature of a circular queue makes its clear() method also resets the 𝑠𝑖𝑧𝑒 attribute of the queue,
i.e., 𝑠𝑖𝑧𝑒 = 0.
 CLEARING A LINKED-LIST-BASED QUEUE
Algorithm Size()
Input: None.
Output: None.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node in the linked list; and 𝒔𝒊𝒛𝒆 is the number of elements in the linked list.
Begin

1. 𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑢𝑙𝑙
2. 𝑠𝑖𝑧𝑒 = 0

End

JAVA IMPLEMENTATION OF THE CLEAR OPERATION FOR LINKED -LIST-BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑐𝑙𝑒𝑎𝑟() {
// 𝑀𝑎𝑘𝑒 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒 𝑒𝑚𝑝𝑡𝑦
𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑢𝑙𝑙;
𝑠𝑖𝑧𝑒 = 0;
}

DISPLAY OPERATION

Display operation is essentially a traversal operation in which each element of the queue is printed,
starting from front to back. This operation accesses the queue without modifying its content. Similar to
stack, traversal operation is not a normal behaviour for a queue. However, it can be achieved by altering
front (i.e., the pointer itself and not the element at that position) during the process, and at the end of
the process resetting front back to its original state.

PRINTING THE ELEMENTS OF AN ARRAY-BASED QUEUE

Algorithm DisplayElements()
Input: None.
Output: None.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒇𝒓𝒐𝒏𝒕, pointer to the first element of the array and
𝒓𝒆𝒂𝒓, pointer to the last element in the array.
Begin

1. 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡
2. While 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦 Do
3. Print element at the 𝑓𝑟𝑜𝑛𝑡
4. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 + 1
5. End While
6. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡𝑇𝑜𝑝

End

JAVA IMPLEMENTATION OF THE DISPLAY OPERATION FOR ARRAY -BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑑𝑖𝑠𝑝𝑙𝑎𝑦𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑠() {

𝒊𝒏𝒕 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡

 // 𝑝𝑟𝑖𝑛𝑡 𝑒𝑎𝑐ℎ 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑠𝑡𝑎𝑐𝑘
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡("[ ");
𝒘𝒉𝒊𝒍𝒆( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡( 𝑝𝑒𝑒𝑘() + " " );
𝑓𝑟𝑜𝑛𝑡 + +;
}
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("]");

𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡;
}

DISPLAYING ELEMENTS OF A CIRCULAR QUEUE

Due to the nature of a circular queue, printing its elements varies slightly from the above. As previously
mentioned, the adjustment of 𝑓𝑟𝑜𝑛𝑡 is always ( 𝑓𝑟𝑜𝑛𝑡 + 1) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 . Also, a local variable,
𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒, is initialised and set to the number of elements in the queue. During each iteration of the
loop 𝑠𝑖𝑧𝑒 is decreased by 1. After the loop, 𝑠𝑖𝑧𝑒 is restored to its original value, i.e., 𝑠𝑖𝑧𝑒 = 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒.

𝒊𝒏𝒕 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒();

𝒘𝒉𝒊𝒍𝒆( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡( 𝑝𝑒𝑒𝑘() + " " );
𝑓𝑟𝑜𝑛𝑡 = ( 𝑓𝑟𝑜𝑛𝑡 + 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
𝑠𝑖𝑧𝑒 − −;
}

𝑠𝑖𝑧𝑒 = 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒;

PRINTING THE ELEMENTS OF A LINKED-LIST-BASED QUEUE

Algorithm DisplayElements()
Input: None.
Output: None.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node in the linked list.
Begin

1. 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡
2. While 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦 Do
3. Print element at the 𝑓𝑟𝑜𝑛𝑡
4. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥𝑡
5. End While
6. 𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡

End

JAVA IMPLEMENTATION OF THE DISPLAY OPERATION FOR LINKED -LIST-BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑑𝑖𝑠𝑝𝑙𝑎𝑦𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑠() {

𝑁𝑜𝑑𝑒 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡

 // 𝑝𝑟𝑖𝑛𝑡 𝑒𝑎𝑐ℎ 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑠𝑡𝑎𝑐𝑘
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡("[ ");
𝒘𝒉𝒊𝒍𝒆( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡( 𝑝𝑒𝑒𝑘() + " " );
𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡. 𝑛𝑒𝑥𝑡;
}
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛("]");

𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡;
}

SEARCH OPERATION

The search operation is also not an fundamental behaviour of the queue. Given a queue, to check
whether it contains an element requires traversing the queue starting from 𝒇𝒓𝒐𝒏𝒕, if the queue is not
𝑒𝑚𝑝𝑡𝑦, until the element is found, or the end of the queue is reached.

SEARCHING AN ARRAY-BASED QUEUE

The following steps are needed to search a non-empty array implemented queue.

1. Initialise a local variable, 𝒕𝒆𝒎𝒑𝑭𝒓𝒐𝒏𝒕, with the value of 𝒇𝒓𝒐𝒏𝒕.

2. While queue is not empty and search 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 is not found at 𝒇𝒓𝒐𝒏𝒕; repeat 3 and 4.
3. Increase 𝒇𝒓𝒐𝒏𝒕 by 1 (for a circular queue, then do a modulo operation against 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦)
4. Initialise a local variable 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏, to 1 if element is found at 𝑓𝑟𝑜𝑛𝑡, otherwise to the value
of current 𝑓𝑟𝑜𝑛𝑡, i.e., the value of 𝒇𝒓𝒐𝒏𝒕 at the end of the loop.
5. Restore 𝒇𝒓𝒐𝒏𝒕 to its original value, i.e., set 𝒇𝒓𝒐𝒏𝒕 to 𝒕𝒆𝒎𝒑𝑭𝒓𝒐𝒏𝒕.
6. Return 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏. This will return -1, if the search element is not found or the position of the
element in the queue.

Algorithm search(element)
Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the value to look for in the queue.
Output: 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏, the position of 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 in the queue or -1 if 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 is not in the queue or the
queue is 𝑒𝑚𝑝𝑡𝑦.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, an array structure with 𝒇𝒓𝒐𝒏𝒕, pointer to the last element in the array.
Begin

1. 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡
2. 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒
3. While 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦 And 𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡 ] ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 Do
4. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 + 1
5. End While
6. If 𝑞𝑢𝑒𝑢𝑒[𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡] = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 Then
7. 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = 1
8. Else
9. 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = 𝑓𝑟𝑜𝑛𝑡
10. 𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡
11. Return 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛

End
 JAVA IMPLEMENTATION OF THE SEARCH OPERATION FOR ARRAY -BASED QUEUE
𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑠𝑒𝑎𝑟𝑐ℎ( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {

𝒊𝒏𝒕 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = −1

𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){

𝒊𝒏𝒕 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡;

𝒘𝒉𝒊𝒍𝒆( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() && 𝑝𝑒𝑒𝑘() ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){

𝑓𝑟𝑜𝑛𝑡 + +;
}

𝒊𝒇( 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 < 0 && 𝑞𝑢𝑒𝑢𝑒[𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡] == 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 )

𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 + +;
𝒆𝒍𝒔𝒆 𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() && 𝑝𝑒𝑒𝑘() == 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 )
𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = 𝑓𝑟𝑜𝑛𝑡;

// 𝑅𝑒𝑠𝑡𝑜𝑟𝑒 𝑓𝑟𝑜𝑛𝑡 𝑡𝑜 𝑖𝑡𝑠 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑣𝑎𝑙𝑢𝑒.

𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡;
}
// 𝑅𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑜𝑓 𝑡ℎ𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒.
𝒓𝒆𝒕𝒖𝒓𝒏 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛;
}

SEARCHING A CIRCULAR QUEUE

A circular queue is searched the same as a simple queue. However, a second local variable, 𝒕𝒆𝒎𝒑𝑺𝒊𝒛𝒆
is initialised and set to the current 𝒔𝒊𝒛𝒆 of the queue. As we traverse the queue, we decrement 𝑠𝑖𝑧𝑒
by 1, whenever the search condition holds. As usual, front is adjusted against the modulo of the
capacity. After the loop, we restore size to its original state, i.e., 𝑠𝑖𝑧𝑒 = 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒.

𝒊𝒏𝒕 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒();

𝒘𝒉𝒊𝒍𝒆( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() && 𝑝𝑒𝑒𝑘() ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {

𝑓𝑟𝑜𝑛𝑡 = ( 𝑓𝑟𝑜𝑛𝑡 + 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
𝑠𝑖𝑧𝑒 − −;
}

𝑠𝑖𝑧𝑒 = 𝑡𝑒𝑚𝑝𝑆𝑖𝑧𝑒;

SEARCHING A LINKED-LIST-BASED QUEUE

The following steps are needed to search a linked list implemented queue.

1. Initialise a local variable 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏, set it to -1.

2. Test whether the queue is empty.
3. If it is empty go to step 13.
4. Initialise a local variable, 𝒕𝒆𝒎𝒑𝑭𝒓𝒐𝒏𝒕, set it 𝒇𝒓𝒐𝒏𝒕.
5. While queue is not empty and search 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 is not found at 𝒇𝒓𝒐𝒏𝒕; repeat steps 6 and 7.
6. Set 𝒇𝒓𝒐𝒏𝒕 to the node that follows it.
 7. Increment 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏 by 1.
8. Check whether the element was found at the beginning of the queue.
9. If element is the first element of the queue, set 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏 to 0.
10. Test to see if the end of queue was reached and element was not found.
11. If element is not found, reset 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏 to -1.
12. Restore 𝒇𝒓𝒐𝒏𝒕 to its original value, i.e., set 𝒇𝒓𝒐𝒏𝒕 to 𝒕𝒆𝒎𝒑𝑭𝒓𝒐𝒏𝒕.
13. Return the 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏. This will return -1, if the search element is not in the queue or if the
queue is empty.

Algorithm search(element)
Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the value to look for in the queue.
Output: 𝒑𝒐𝒔𝒊𝒕𝒊𝒐𝒏, the position of 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 in the queue or -1 if 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 is not in the queue or the
queue is 𝑒𝑚𝑝𝑡𝑦.
Data Structure: 𝒒𝒖𝒆𝒖𝒆, a singly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕,
pointer to the first node in the linked list.
Begin

1. 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = −1
2. If 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦
3. 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡
4. While 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦 And 𝑓𝑟𝑜𝑛𝑡 → 𝑑𝑎𝑡𝑎 ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 Do
5. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥𝑡
6. 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 + 1
7. End While
8. if 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦 And 𝑓𝑟𝑜𝑛𝑡 → 𝑑𝑎𝑡𝑎 == 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 Do
9. 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 + 1
10. Else
11. if 𝑞𝑢𝑒𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then
12. 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = −1
13. End If
14. End If
15. 𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡
16. End if
17. Return 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛

End

JAVA IMPLEMENTATION OF THE SEARCH OPERATION FOR LINKED -LIST-BASED QUEUE

𝒑𝒖𝒃𝒍𝒊𝒄 𝒊𝒏𝒕 𝑠𝑒𝑎𝑟𝑐ℎ(𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡) {

𝒊𝒏𝒕 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = −1;

if( !isEmpty() ) {
𝑄𝑢𝑒𝑢𝑒𝑁𝑜𝑑𝑒 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡;

𝒘𝒉𝒊𝒍𝒆( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() && 𝑝𝑒𝑒𝑘() ! = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){

𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥𝑡;
𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 + +;
}
𝒊𝒇( ! 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() && 𝑝𝑒𝑒𝑘() == 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ){
 // 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑠 𝑡ℎ𝑒 𝑓𝑖𝑟𝑠𝑡 𝑛𝑜𝑑𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒
𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 + +;
}
𝒆𝒍𝒔𝒆 {
𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
// 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑠 𝑛𝑜𝑡 𝑓𝑜𝑢𝑛𝑑 𝑖𝑛 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒
𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 = −1;
}
}

// 𝑅𝑒𝑠𝑡𝑜𝑟𝑒 𝑓𝑟𝑜𝑛𝑡 𝑡𝑜 𝑖𝑡𝑠 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑣𝑎𝑙𝑢𝑒.

𝑓𝑟𝑜𝑛𝑡 = 𝑡𝑒𝑚𝑝𝐹𝑟𝑜𝑛𝑡;

// 𝑅𝑒𝑡𝑢𝑟𝑛 𝑡ℎ𝑒 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑜𝑓 𝑡ℎ𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒.

𝒓𝒆𝒕𝒖𝒓𝒏 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛;
}

COMPLEXITY OF QUEUE OPERATIONS

Queue has an efficient (constant time) implementation using cyclic arrays (circular queues) and singly
linked lists. The time complexity for common queue operations and space complexity for queue are
summarised in the following table:

Operations Array Queue Linked Queue

Time Complexity

enqueue 𝑂(1) 𝑂(1)

dequeue 𝑂(1) 𝑂(1)

search 𝑂(𝑛) 𝑂(𝑛)

peek 𝑂(1) 𝑂(1)

empty 𝑂(1) 𝑂(1)

full 𝑂(1) 𝑂(1)

Space complexity

𝑂(𝑛) 𝑂(𝑛)

MORE ON DEQUE

We cannot conclude our discussion on queues without exploring deque in greater detail. As we have
mentioned earlier, insertions and deletions operations are performed from both front and rear. Thus,
we can say a deque is a generalised variant of the queue data structure.

As deque allows insertions and deletions from both ends, it can be used as both a stack and a queue.
 • In deque, insertion and deletion can be done on a single end. The stack follows the LIFO
principle which permits insertion and deletions of elements from a single point.
• In deque, insertion can be done at one end and deletion can be from another end. The queue
follows FIFO principle which permits elements to be inserted at one end and removed from
another end.

There are two types of deques:

• Input-restricted deque: In this type of deque, restriction is applied to insertion operations. So,
insertion operation is only done from one end whereas deletion operation can be done from
both ends.
• Output-restricted deque: In this type of deque, a constraint is placed on deletion operations.
So, deletion operation is limited to one end while insertion operation is possible at both ends.

OPERATIONS ON A DEQUE

All queue operations can be done on a deque. However, because of the nature of deque, the main
queue operations are adapted as follows:

• Insert at front: adds an element to the front position, if deque is not full (only for a static deque).
• Delete from front: removes an element from the front position, if deque is not empty.
• Insert at rear: adds an element to the rear position, if deque is not full (applicable only to a
static deque).
• Delete from rear: removes an element from the rear position, if deque is not empty.

Similarly, we can perform the peek operation at both ends of the deque.

MEMORY REPRESENTATION OF A DEQUE

How a deque is represented in memory depends on its implementation. A deque can be implemented
using a circular queue and a doubly linked list.

IMPLEMENTATION OF A DEQUE USING A CIRCULAR QUEUE

Operations of a deque that are common to a circular queue are executed exactly as in circular queue.
Let’s look at the operations that are not intrinsic to the circular queue.

ENQUEUE AT FRONT

Inserting at front of an empty deque, works the same way as enqueuing a normal circular queue. The
element will be inserted at the first empty space and both front and rear will point to it. If we want to
insert at the front point of the deque, we first have to a decrement of front, i.e., move the front pointer
one step backwards. Once the front pointer is set, we will insert the value. Because we are working
with circular queue, when we decrease front by 1, we will perform a modulo operation against capacity,
i.e., front = ( front – 1) % capacity. However, for Java we will need to use Math.floorMod() method to
perform an obtain an accurate modulo for negative numbers.

Example 8: The following is Java implementation of the enqueuing an element at the front of a deque.
 𝒑𝒖𝒃𝒍𝒊𝒄 𝒗𝒐𝒊𝒅 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐹𝑟𝑜𝑛𝑡( 𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 ) {
// 𝐴𝑑𝑑 𝑣𝑎𝑙𝑢𝑒 𝑎𝑠 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.

𝒊𝒇( 𝑖𝑠𝐹𝑢𝑙𝑙() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛( "𝐷𝑒𝑄𝑢𝑒 𝑖𝑠 𝑓𝑢𝑙𝑙! " );
𝒓𝒆𝒕𝒖𝒓𝒏;
}

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑓𝑟𝑜𝑛𝑡 = ( 𝑓𝑟𝑜𝑛𝑡 + 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
𝑟𝑒𝑎𝑟 = ( 𝑟𝑒𝑎𝑟 + 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
}
𝒆𝒍𝒔𝒆{
𝑓𝑟𝑜𝑛𝑡 = 𝑀𝑎𝑡ℎ. 𝑓𝑙𝑜𝑜𝑟𝑀𝑜𝑑( ( 𝑓𝑟𝑜𝑛𝑡() – 1 ), 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 () );
//𝑓𝑟𝑜𝑛𝑡 = ( 𝑓𝑟𝑜𝑛𝑡 − 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦
}

𝑞𝑢𝑒𝑢𝑒[𝑓𝑟𝑜𝑛𝑡] = 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
𝑠𝑖𝑧𝑒 + +;
}

DEQUEUE AT REAR

Attempting to dequeue from the rear of an empty deque behaves the same way as attempting to
dequeue the front of a standard circular queue. To remove an element at the rear, first we take out the
element and then do a decrement on rear, i.e., move rear one spot backwards. To adjust rear, we will
need to decrease it by 1 and then perform a modulo operation against capacity, i.e., rear = ( rear – 1 )
% capacity. Remember when implementing in Java we will use Math.floorMod() method to get accurate
modulo when having negative dividend.

Example 9: The following is Java implementation of the dequeuing an element from the rear of a deque.

𝒑𝒖𝒃𝒍𝒊𝒄 𝑶𝒃𝒋𝒆𝒄𝒕 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟( ) {

// 𝐴𝑑𝑑 𝑣𝑎𝑙𝑢𝑒 𝑎𝑠 𝑡ℎ𝑒 𝑓𝑟𝑜𝑛𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑛 𝑡ℎ𝑖𝑠 𝑞𝑢𝑒𝑢𝑒.

𝒊𝒇( 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ){
𝑆𝑦𝑠𝑡𝑒𝑚. 𝒐𝒖𝒕. 𝑝𝑟𝑖𝑛𝑡𝑙𝑛( "𝐷𝑒𝑄𝑢𝑒 𝑖𝑠 𝐸𝑚𝑝𝑡𝑦! " );
𝒓𝒆𝒕𝒖𝒓𝒏;
}

𝑂𝑏𝑗𝑒𝑐𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑝𝑜𝑙𝑙𝑅𝑒𝑎𝑟();

𝑟𝑒𝑎𝑟 = 𝑀𝑎𝑡ℎ. 𝑓𝑙𝑜𝑜𝑟𝑀𝑜𝑑 ( ( 𝑟𝑒𝑎𝑟() – 1 ), 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 () );
// 𝑟𝑒𝑎𝑟 = ( 𝑟𝑒𝑎𝑟 − 1 ) % 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦;
𝑠𝑖𝑧𝑒 − −;
}
𝒓𝒆𝒕𝒖𝒓𝒏 𝑒𝑙𝑒𝑚𝑒𝑛𝑡;
}
 PEEKING AT REAR

Peeking at rear, simply return the element at the rear of the deque if the deque is not empty, i.e.,
𝒓𝒆𝒕𝒖𝒓𝒏 𝑞𝑢𝑒𝑢𝑒[𝑟𝑒𝑎𝑟].

PROCESSING A CIRCULAR DEQUE

Example 9: Let’s continue with the queue from Example 2. Assuming the structure is a deque. Let’s add
10 at the front of deque. Then dequeue from the rear. And add 5 at the front again.

front = 0 front = 4
Enqueuing 10 at front

8 7 4 8 7 4 10

rear = 2 rear = 2

front = 4 front = 3
Dequeuing from rear Enqueuing 5 at front

8 7 10 8 7 5 10

rear = 1 rear = 1

IMPLEMENTATION OF A DEQUE USING A DOUBLY LINKED LIST

A deque is implemented as a linked list using doubly linked list because due to the nature of a deque
elements are processed in both directions. Like with regular queues, we keep track of two pointers,
front and rear.

We enqueue (push) an item at the rear or the front end of the deque and dequeue(pop) an item from
both rear and front end.

INSERTION AT FRONT

To insert an element at the front of deque we do following steps:

1. Create a new doubly linked list node, with the element to be inserted as its value and set both
its links rear and front to null.
2. Check if deque is empty.
3. If empty, then set both front and rear to the new node.
4. If not empty, then do steps 5 to 8
5. Set successor of the new element to front.
6. Set the predecessor of front to the new element.
7. Make the new element the new front.
8. Increase size by 1.
Algorithm enqueueFront(element)
Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the item to add to the front of deque.
Output: nothing, but deque will be modified to with the element as its new from.
Data Structure: 𝒅𝒆𝒒𝒖𝒆 , a doubly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from
𝒇𝒓𝒐𝒏𝒕, pointer to the first node in the linked list and 𝒔𝒊𝒛𝒆 is the number of elements in 𝑑𝑒𝑞𝑢𝑒.
Begin

1. 𝑁𝑜𝑑𝑒 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 = 𝑛𝑒𝑤 𝑁𝑜𝑑𝑒()

2. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑑𝑎𝑡𝑎 = 𝑛𝑢𝑙𝑙
3. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙
4. If 𝑑𝑒𝑞𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then
5. 𝑟𝑒𝑎𝑟 = 𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
6. Else
7. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 = 𝑓𝑟𝑜𝑛𝑡
8. 𝑓𝑟𝑜𝑛𝑡 → 𝑝𝑟𝑒𝑣 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
9. 𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
10. 𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 + 1
11. End If

End

INSERTION AT REAR

To insert an element at the front of deque we do following steps:

1. Create a new doubly linked list node, with the element to be inserted as its value and set both
its links to rear and front to null.
2. Check if deque is empty.
3. If empty, then set both front and rear to the new node.
4. If not empty, then do steps 5 to 8
5. Set predecessor of the new element to rear.
6. Set the successor of rear to the new element.
7. Make the new element the new rear.
8. Increase size by 1.

Algorithm enqueueRear(element)
Input: 𝒆𝒍𝒆𝒎𝒆𝒏𝒕, the item to add to the rear of the deque.
Output: nothing, but deque will be modified to with the element as its new from.
Data Structure: 𝒅𝒆𝒒𝒖𝒆, a doubly linked list structure whose pointer to the 𝒕𝒂𝒊𝒍 is known from 𝒓𝒆𝒂𝒓,
pointer to the last node in the linked list and 𝒔𝒊𝒛𝒆 is the number of elements in 𝑑𝑒𝑞𝑢𝑒.
Begin

1. 𝑁𝑜𝑑𝑒 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 = 𝑛𝑒𝑤 𝑁𝑜𝑑𝑒()

2. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑑𝑎𝑡𝑎 = 𝑛𝑢𝑙𝑙
3. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙
4. If 𝑑𝑒𝑞𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then
5. 𝑓𝑟𝑜𝑛𝑡 = 𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
6. Else
7. 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑝𝑟𝑒𝑣 = 𝑟𝑒𝑎𝑟
8. 𝑟𝑒𝑎𝑟 → 𝑛𝑒𝑥𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
9. 𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
 10. 𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 + 1
11. End If

End

DELETION FROM FRONT

To delete an element from front of deque we do following steps:

1. Check if deque is empty.

2. If empty, then throw and underflow error and exit.
3. If not empty, then do steps 4 to 10.
4. Create a new doubly linked list node and initialise with front.
5. Make the successor of element at front the new front.
6. Check if deque has become empty.
7. If empty, then set rear to null.
8. If not empty, then set the predecessor of front to null.
9. Decrease size by 1.
10. Return the value of the deleted node.

Algorithm dequeueFront()
Input: none.
Output: 𝒅𝒆𝒍𝒆𝒕𝒆𝒅𝑵𝒐𝒅𝒆 → 𝒅𝒂𝒕𝒂, the value of the deleted node.
Data Structure: 𝒅𝒆𝒒𝒖𝒆, a doubly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕
(pointer to the first node in the linked list), pointer to the 𝒕𝒂𝒊𝒍 is known from 𝒓𝒆𝒂𝒓 (pointer to
the last node in the linked list) and 𝒔𝒊𝒛𝒆 is the number of elements in 𝑑𝑒𝑞𝑢𝑒.
Begin

1. If 𝑑𝑒𝑞𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then

2. Print "Underflow"
3. Exit
4. Else
5. 𝑑𝑒𝑙𝑒𝑡𝑒𝑑𝑁𝑜𝑑𝑒 = 𝑓𝑟𝑜𝑛𝑡
6. 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥𝑡
7. If 𝑑𝑒𝑞𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then
8. 𝑟𝑒𝑎𝑟 = 𝑛𝑢𝑙𝑙
9. Else
10. 𝑓𝑟𝑜𝑛𝑡 → 𝑝𝑟𝑒𝑣 = 𝑛𝑢𝑙𝑙
11. End If
12. 𝑆𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 – 1
13. Return 𝑑𝑒𝑙𝑒𝑡𝑒𝑑𝑁𝑜𝑑𝑒 → 𝑑𝑎𝑡𝑎
14. End If

End

DELETION FROM REAR

To delete an element from the rear of the deque we do following steps:

1. Check if deque is empty.

2. If empty, then throw and underflow error and exit.
 3. If not empty, then do steps 4 to 10.
4. Create a new doubly linked list node and initialise with rear.
5. Make the predecessor of element at rear the new rear.
6. Check if deque has become empty.
7. If empty, then set front to null.
8. If not empty, then set the successor of rear to null.
9. Decrease size by 1.
10. Return the value of the deleted node.

Algorithm dequeueRear()
Input: none.
Output: 𝒅𝒆𝒍𝒆𝒕𝒆𝒅𝑵𝒐𝒅𝒆 → 𝒅𝒂𝒕𝒂, the value of the deleted node.
Data Structure: 𝒅𝒆𝒒𝒖𝒆, a doubly linked list structure whose pointer to the 𝒉𝒆𝒂𝒅 is known from 𝒇𝒓𝒐𝒏𝒕
(pointer to the first node in the linked list), pointer to the 𝒕𝒂𝒊𝒍 is known from 𝒓𝒆𝒂𝒓 (pointer to
the last node in the linked list) and 𝒔𝒊𝒛𝒆 is the number of elements in 𝑑𝑒𝑞𝑢𝑒.
Begin

1. If 𝑑𝑒𝑞𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then

2. Print "Underflow"
3. Exit
4. Else
5. 𝑑𝑒𝑙𝑒𝑡𝑒𝑑𝑁𝑜𝑑𝑒 = 𝑟𝑒𝑎𝑟
6. 𝑟𝑒𝑎𝑟 = 𝑟𝑒𝑎𝑟 → 𝑝𝑟𝑒𝑣
7. If 𝑑𝑒𝑞𝑢𝑒 Is 𝑒𝑚𝑝𝑡𝑦 Then
8. 𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑢𝑙𝑙
9. Else
10. 𝑟𝑒𝑎𝑟 → 𝑛𝑒𝑥𝑡 = 𝑁𝑈𝐿𝐿
11. End If
12. 𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 – 1
13. Return 𝑑𝑒𝑙𝑒𝑡𝑒𝑑𝑁𝑜𝑑𝑒 → 𝑑𝑎𝑡𝑎
14. End If

End

REAL LIFE EXAMPLES

What are real life applications of the queue data structure?

• Print spooling.
• CPU scheduling and disk scheduling. Operating systems often maintain a queue of processes
that are ready to execute or that are waiting for a particular event to occur.
• Data transfer between two processes in the asynchronous manner. In this application, the
queue is used for synchronization. For example – IO buffers, pipes, file IO, etc.
• Handling interruptions in real-time systems
• The call centre phone systems also use the queue structure. It is used to hold the customer
calls in order until a representative is free.
 • Traffic System. In computer-controlled traffic system, circular queues are used to switch on the
traffic lights one by one repeatedly as per the time set. Converting decimal numbers into binary
numbers.
• Performing Breadth First Search (BFS). BFS is an algorithm in data structure that traverses and
searches a graph.

STACK VS QUEUES

Stacks and queues are similar data structures. There are two major similarities between the stack and
queue:

• They are both linear data structure, which means that their elements are stored sequentially
and accessed in a single run.
• They can both be static or dynamic.
o The static implementation of the stack and queue can be done with the help of arrays.
This means their capacity (maximum number of elements they can hold) is bounded at
run time.
o The dynamic implementation of the stack and queue can be done with the help of a
linked list. This means they can grow and shrink according to the requirements at the
run-time.

The following table summarises and highlights the differences between the array-based stack and
array-based queue.

Basis for Array Stack Simple Queue

Comparison

Principle LIFO (Last-In First-Out) or FILO (First- FIFO (First-In First-Out) or LILO (Last-In
In Last-Out) Last-Out)

Structure It only uses one end, called top, for It uses two ends, one end is called rear,
both insertions and deletions of for insertions and another end, called
elements. front, for deletions.

Number of It has one pointer, top. The top It has two pointers, front and rear. The
pointers used references the last inserted or the front pointer references the first
topmost element of the stack. element, whereas the rear pointer
references the last element in a queue.

Main operations Push and pop. Enqueue and dequeue

performed

Checking for 𝒕𝒐𝒑 == −1 (same 𝑎𝑠 𝒕𝒐𝒑 < 0 ), 𝒇𝒓𝒐𝒏𝒕 == −1 OR 𝒇𝒓𝒐𝒏𝒕 ==

empty condition which means that the stack is empty. 𝒓𝒆𝒂𝒓 + 1 (same as 𝒇𝒓𝒐𝒏𝒕 > 𝒓𝒆𝒂𝒓),
which means that the queue is empty.

Checking for full top == capacity – 1 (same as (𝒕𝒐𝒑 + 𝒓𝒆𝒂𝒓 = 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 – 1 (same as
condition 1) == 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 ), this condition ( 𝒓𝒆𝒂𝒓 + 1) == 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 ), this
implies that the stack is full. condition implies that the stack is full.
Variants Double stacks Circular queue, priority queue and
double-ended queue.

Implementation Simpler Comparatively more complex than stack

Visualisation Typically visualized as vertical. Typically visualized as horizontal.

SUMMARY

• A queue is collection of similar data items in which insertion and deletion operations are
performed based on FIFO principle.
• A queue is an abstract data type, and the implemented queue ADT becomes a queue data
structure.
• The queue structure is characterised by four major operations: create the collection, insert an
element, delete an element and check whether the collection is empty.
• A major disadvantage of the array-based queue is spaces freed from dequeuing operations
remain unused.
• Circular queues bypass this drawback. However, the disadvantage of having a fixed capacity
remains. Thus, at any point of time, the array is either filled or not. This means memory is either
not enough or is being wasted.
• Linked list implementation solves this problem. However, the drawback of the linked list
implementation is that it needs to store several addresses (in pointer fields of nodes). If the
data type of the elements in the queue is small compared to pointer, then this implementation
is not memory efficient.
• The table that follows compares the array and linked list implementations of the queue ADT.

Array Implemented Queue Linked List Implemented Queue

They are generally static. They are dynamic.
They have a fixed 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚, which is the Have “unlimited” 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚.
maximum number of elements the queue
can hold.
𝒇𝒓𝒐𝒏𝒕 is the index of element at the front of 𝒇𝒓𝒐𝒏𝒕 is the node at the start of the queue
the quest (first element in the array). (head of the linked list).
𝒓𝒆𝒂𝒓 is the index of element at the end of 𝒓𝒆𝒂𝒓 is the node at the end of the queue
the quest (last element in the array). (tail of the linked list).
The 𝒔𝒊𝒛𝒆 of the queue is usually 𝒓𝒆𝒂𝒓 − The 𝒔𝒊𝒛𝒆 of the queue is usually the number
𝒇𝒓𝒐𝒏𝒕 + 𝟏 and 𝒔𝒊𝒛𝒆 ≤ 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚. of 𝒆𝒏𝒒𝒖𝒆𝒖𝒆𝒔 operations done on the
queue minus the number of 𝒅𝒆𝒒𝒖𝒆𝒖𝒆𝒔
operations done. Hence, 𝒔𝒊𝒛𝒆 is
𝒊𝒏𝒄𝒓𝒆𝒂𝒔𝒆𝒅 𝒃𝒚 𝟏 with every enqueue
operation and 𝒅𝒆𝒄𝒓𝒆𝒂𝒔𝒆𝒅 𝒃𝒚 𝟏 with every
dequeue operation.

• The following tables summarise statuses of an array implemented queue with 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 N
based on the values of the 𝒇𝒓𝒐𝒏𝒕 and 𝒓𝒆𝒂𝒓:

Values Meaning
𝒇𝒓𝒐𝒏𝒕 = Queue is 𝒆𝒎𝒑𝒕𝒚. When a dequeue operation is attempted on an empty
−𝟏 queue, the queue goes into 𝒖𝒏𝒅𝒆𝒓𝒇𝒍𝒐𝒘.
 𝑶𝑹 𝒇𝒓𝒐𝒏𝒕 >
𝒓𝒆𝒂𝒓
𝒓𝒆𝒂𝒓 = 𝟎 Queue has a single element.
𝒓𝒆𝒂𝒓 The queue is 𝒇𝒖𝒍𝒍.
= 𝑵−𝟏
𝒓𝒆𝒂𝒓 = 𝑵 The queue is in 𝒐𝒗𝒆𝒓𝒇𝒍𝒐𝒘, this happens when an enqueue is attempted on
an already 𝒇𝒖𝒍𝒍 queue.
• For a linked list implemented queue, when queue is empty, 𝒇𝒓𝒐𝒏𝒕 is 𝒏𝒖𝒍𝒍.
• In Java, Queue is represented as an interface, java.util.Queue that falls under the Collection
Framework. Most frequently used Java Queue implementation classes are LinkedList,
PriorityQueue and BlockingQueue. AbstractQueue provides a skeletal implementation of the
Queue interface to reduce the effort in implementing Queue. Deque is represented as an
interface, java.utiil.Deque and it is implemented by ArrayDeque and LinkedList.
• Deque is a generalised version of a queue. It allows insertion at front and rear and also permits
deletion from front and rear. This property of a deque makes it possible to be as both a stack
and a queue.
• There are two types of deques:
1. Input-restricted queue: In this queue, elements can be removed from both ends of the
queue but can only be inserted at one end.
2. Output-redistricted queue: In this queue, elements can be inserted at both ends of the
queue but can only be removed from one end.
•

WHAT COMES LATER

• In later units, we will look at a data structure called heap and how it can be used to implement
a priority queue.

• In the next unit, we will revisit stacks and look at the concept of recursion. We will also look at
some of their applications including how they are used to keep track of system function calls.

EXERCISES

1. Consider the situation where a stack is the only data structure you have available.
a. How many stacks do you need to implement a queue?
b. How can you implement the queue, if you are allowed to push onto one stack only?
c. How can you implement the queue, if you are allowed to pop from one stack only?
2. Consider the situation where a queue is the only data structure you have available.
a. How many queues do you need to implement a stack?
b. How can you implement the stack, if you are allowed to enqueue to one queue only?
c. How can you implement the stack, if you are allowed to dequeue from one queue only?
3. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, what
is the order of removal?
4. What does the following code fragment do to the Stack 𝑠𝑡𝑎𝑐𝑘?.

𝑄𝑢𝑒𝑢𝑒 𝑞𝑢𝑒𝑢𝑒 = 𝑛𝑒𝑤 𝑄𝑢𝑒𝑢𝑒();

𝒘𝒉𝒊𝒍𝒆 ( ! 𝑠𝑡𝑎𝑐𝑘. 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑞𝑢𝑒𝑢𝑒. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒( 𝑠𝑡𝑎𝑐𝑘. 𝑝𝑜𝑝() );
}
 𝒘𝒉𝒊𝒍𝒆 ( ! 𝑞𝑢𝑒𝑢𝑒. 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
𝑠𝑡𝑎𝑐𝑘. 𝑝𝑢𝑠ℎ( 𝑞𝑢𝑒𝑢𝑒. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒() );
}

5. Implement the algorithms of the deque operations in the Section: Implementation of a Deque
using a Doubly Linked List.
6. Following is a Java like pseudocode of a function that takes a Queue 𝑞𝑢𝑒𝑢𝑒 as an argument and
uses a Stack 𝑠𝑡𝑎𝑐𝑘 to do processing.

𝒗𝒐𝒊𝒅 𝑚𝑦𝑠𝑡𝑒𝑟𝑦(𝑄𝑢𝑒𝑢𝑒 𝑞𝑢𝑒𝑢𝑒) {

// 𝑎𝑠𝑠𝑢𝑚𝑒𝑠 𝑡ℎ𝑖𝑠 𝑐𝑟𝑒𝑎𝑡𝑒𝑠 𝑎𝑛 𝑒𝑚𝑝𝑡𝑦 𝑠𝑡𝑎𝑐𝑘.

𝑆𝑡𝑎𝑐𝑘 𝑠𝑡𝑎𝑐𝑘;

// 𝑒𝑥𝑒𝑐𝑢𝑡𝑒 𝑤ℎ𝑖𝑙𝑒 𝑞𝑢𝑒𝑢𝑒 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦.

𝒘𝒉𝒊𝒍𝒆( ! 𝑞𝑢𝑒𝑢𝑒. 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
/ / 𝑑𝑒𝑞𝑢𝑒𝑢𝑒 𝑎𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑓𝑟𝑜𝑚 𝑞𝑢𝑒𝑢𝑒 𝑎𝑛𝑑 𝑝𝑢𝑠ℎ 𝑖𝑡 𝑜𝑛𝑡𝑜 𝑠𝑡𝑎𝑐𝑘.
𝑠𝑡𝑎𝑐𝑘. 𝑝𝑢𝑠ℎ( 𝑞𝑢𝑒𝑢𝑒. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒() );
}

// 𝑒𝑥𝑒𝑐𝑢𝑡𝑒 𝑤ℎ𝑖𝑙𝑒 𝑠𝑡𝑎𝑐𝑘 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦.

𝒘𝒉𝒊𝒍𝒆( ! 𝑠𝑡𝑎𝑐𝑘. 𝑖𝑠𝐸𝑚𝑝𝑡𝑦() ) {
/ / 𝑝𝑜𝑝 𝑎𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑓𝑟𝑜𝑚 𝑠𝑡𝑎𝑐𝑘 𝑎𝑛𝑑 𝑒𝑛𝑞𝑢𝑒𝑢𝑒 𝑖𝑡 𝑖𝑛 𝑞𝑢𝑒𝑢𝑒.
𝑞𝑢𝑒𝑢𝑒. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒( 𝑠𝑡𝑎𝑐𝑘. 𝑝𝑜𝑝() );
}

}
What does the above function do in general?

7. Given the following empty (output-restricted) deque (circular queue implementation). In this
implementation of deque, when a queue becomes empty as a result of a dequeuing operation,
the deque is reset.

a. If the following sequence of operations is performed:

1. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐹𝑟𝑜𝑛𝑡(′𝐴′);
2. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟(′𝐵′);
3. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟(′𝐶′);
4. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟(′𝐸′);
5. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟();
6. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟();
7. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟();
8. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟();
9. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐹𝑟𝑜𝑛𝑡(′𝐹′);
10. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐹𝑟𝑜𝑛𝑡(′𝐺′);
11. 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟();
12. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝑅𝑒𝑎𝑟(′𝐷′);
 With the aid of pictorial representation of the deque, show after each operation the
content of the deque and the positions of 𝑓𝑟𝑜𝑛𝑡 and 𝑟𝑒𝑎𝑟.

b. What will happen if we call a 𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝐹𝑟𝑜𝑛𝑡()?

c. From the operations in (a) above, determine what is the principle governing the deque,
in terms of the ends the deletion and insertion operations are permitted?
8. A priority queue can be implemented with arrays. The priorities of the elements can be
represented as one dimension while the values of the elements can be represented as a second
dimension.
a. Write an algorithm or pseudocode for the main operations.
b. Implement your operations in (a).
9. Let 𝒒𝒖𝒆𝒖𝒆 denote a queue containing 8 elements and 𝒔𝒕𝒂𝒄𝒌 be an empty stack. front(queue)
returns the element at the front of queue without removing it from queue. Similarly, top(stack)
returns the element at the top of stack without removing it from stack. Consider the following
algorithm snippet.
1. While 𝑞𝑢𝑒𝑢𝑒 Is Not 𝑒𝑚𝑝𝑡𝑦 Do
2. If 𝑠𝑡𝑎𝑐𝑘 Is 𝑒𝑚𝑝𝑡𝑦 Or 𝑡𝑜𝑝(𝑠𝑡𝑎𝑐𝑘) ≤ 𝑓𝑟𝑜𝑛𝑡(𝑞𝑢𝑒𝑢𝑒) Then
3. 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑑𝑒𝑞𝑢𝑒𝑢𝑒 (𝑞𝑢𝑒𝑢𝑒)
4. 𝑝𝑢𝑠ℎ(𝑠𝑡𝑎𝑐𝑘, 𝑒𝑙𝑒𝑚𝑒𝑛𝑡)
5. Else
6. 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 = 𝑑𝑒𝑞𝑢𝑒𝑢𝑒 (𝑞𝑢𝑒𝑢𝑒)
7. 𝑒𝑛𝑞𝑢𝑒𝑢𝑒(𝑞𝑢𝑒𝑢𝑒, 𝑒𝑙𝑒𝑚𝑒𝑛𝑡)
8. End If
9. End While
a. What does the algorithm do?
b. What is the maximum possible number of iterations of the while loop in the algorithm?
c. Let 𝒒𝒖𝒆𝒖𝒆 denote a queue containing 8 elements and 𝒔𝒕𝒂𝒄𝒌 be an empty stack.
front(queue).
10. Five (5) items: 1, 2, 3, 4, and 5 are pushed on top of a stack, one after the other starting with
A. Fours item were popped out of the stack, and each element was inserted in a queue as soon
as it was deleted. Two elements are deleted from the queue and pushed back on top of the
stack. What element is at top of the stack?