MODULE 03
THE QUEUE DATA
STRUCTURES
LEARNING OBJECTIVES
At the end of this module, you should be able to:
1. describe queue data structure;
2. perform the queue data structure operations;
3. describe circular queue; and
4. perform the circular queue operations;
LOADING YOUR KNOWLEDGE
There are many real-life examples of a queue. Consider the simple
example of single-lane one-way road, where the vehicle enters first, exits first.
More real-world examples can be seen as queues at the ticket windows and
bus-stops. In this module, you will learn the operations and application of
queue.
INITIALIZE YOUR KNOWLEDGE
LESSON 3.1
BASIC CONCEPTS OF QUEUE DATA STRUCTURES
LET’S PROCESS
Queue is a linear data structure, just like stack data structure. A real-
world example of queue can be a single-lane one-way road, where the vehicle
enters first, exits first (see figure 3.1).
Source: https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
Figure 3.1. Single-lane one-way road
Practical Applications
So what makes queues special? A queue follows First-In-First-Out (FIFO)
— which means the first item to enter the queue is the first to leave the queue.
In computer science this pattern is useful when processes need to be
executed in the order that they are created. It is also used to send messages to
a receiver in the order that they were generated.
Queues are useful in the scenario where there is only a single resource,
but multiple objects that want to use or access this resource. So a queue can be
thought of like a waiting list, for a resource. This resource can be a processor,
or maybe a service that executes a function or it could even be a receiver for a
message. Introducing this concept of a waiting list for a resource helps us create
asynchronous systems, increasing processing speed and also ensures the
resource is utilised efficiently.
Here are some of the common places where queues are used:
Message Queues – A message queue is a general concept used for
communication between processes. Basically a sender sends a message, and
if the receiver cannot receive it immediately maybe because it is busy with
something or offline, the message instead of dropping off, waits in some kind
of a queue, and when the receiver is ready to receive it, the message is
consumed or removed from the queue and sent to the receiver.
CC 33 | Data Structures & Algorithms 2
For example, when you send an email, it waits in a queue called the
SMTP queue, until the receiver logs into their inbox. Same concept is
applied when you send a message to someone who is not online on a social
network. Your message waits in some kind of a queue on a server, and
when the recipient comes online, it is sent to them.
Process Scheduling – All the processes running on your computer now,
first wait in a queue called ready queue, waiting to be executed by your
processor. There are various scheduling algorithms that decide which
process should be executed next based on certain criteria like priority.
Data Buffers – A buffer implements a queue and is typically used in
communication when there is difference between the rate at which data is
received and the rate at which it can be processed.
For example in video streaming applications, the video is streamed in
bursts and stored in a buffer so that even if the network becomes slow for a
while, the playback is not interrupted. Say for example the video is playing
at 24fps, then the streaming app may store 240 frames in its buffer, so that
it can continue playing for the next 10 seconds even if the network is
interrupted. The buffer is also used for sequencing frames, for example, if
frames come out of order, they are sorted in the buffer before being played.
Buffers also used in disk drives, input/output devices and communication
over networks.
SELF–CHECK!
iCONNECT
You can visit this link for more information.
1. Educational video about queue data structure:
https://www.youtube.com/watch?v=XuCbpw6Bj1U
Title of the video: Data structures: Introduction to Queues
CC 33 | Data Structures & Algorithms 3
LESSON 3.2
QUEUE OPERATIONS
LET’S PROCESS
In queue, the first element is inserted from one end called the REAR and
the removal of existing element takes place from the other end called
as FRONT (see figure 3.2).
This makes queue as FIFO (First in First Out) data structure, which
means that element inserted first will be removed first which is exactly how
queue system works in real world. If you go to a ticket counter to buy movie
tickets, and are first in the queue, then you will be the first one to get the
tickets. Same is the case with Queue data structure. Data inserted first, will
leave the queue first.
The process to add an element into queue is called Enqueue and the
process of removal of an element from queue is called Dequeue.
Source: https://www.studytonight.com/data-structures/queue-data-structure
Figure 3.2. Representation of a FIFO (first in, first out) queue
Initially, the FRONT and the REAR of the queue points at the first index
of the array (starting the index of array from 0). As we add elements to the
queue, the REAR keeps on moving ahead, always pointing to the position
where the next element will be inserted, while the FRONT remains at the first
index (see figure 3.3).
To use a queue efficiently, we need to check the status of queue as well.
For the same purpose, the following functionality is added to queue –
isFull() − check if queue is full. This means that you cannot add
another element onto the queue.
CC 33 | Data Structures & Algorithms 4
isEmpty() − check if queue is empty.
Figure 3.3. Linear Queue operations
Consider the following example:
Example:
Given the queue below (see figure 3.4) in linear representation, perform
the operations given in table 3.1 and write in the table the locations of the
front and rear.
Figure 3.4. Queue Example #1
CC 33 | Data Structures & Algorithms 5
Table 3.1. Example of Queue Operation
Operation front() Rear() Status
1. Initial location -1 -1 isEmpty()
2. Enqueue() 0 0
3. Enqueue() 0 1
4. Enqueue() 0 2
5. Enqueue() 0 3
6. Dequeue() 1 3
7. Dequeue() 2 3
8. Enqueue() 2 4
9. Dequeue() 3 4
10. Dequeue() 4 4
SELF–CHECK!
iCONNECT
You can visit this link for more information.
1. Educational video about queue operation:
https://www.youtube.com/watch?v=okr-XE8yTO8
Title of the video: Data structures: Array implementation of Queue
CC 33 | Data Structures & Algorithms 6
LESSON 3.3
CIRCULAR QUEUE
LET’S PROCESS
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. It is also called ‘Ring
Buffer’ (see figure 3.5).
Source: https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation
Figure 3.5. A circular Queue
Difference between linear queue and circular queue
BASIS FOR
LINEAR QUEUE CIRCULAR QUEUE
COMPARISON
Basic Organizes the data elements Arranges the data in the
and instructions in a circular pattern where
sequential order one after the last element is
the other. connected to the first
element.
Order of task Tasks are executed in order Order of executing a
execution they were placed before task may change.
(FIFO).
Insertion and The new element is added Insertion and deletion
deletion from the rear end and can be done at any
removed from the front. position.
Performance Inefficient Works better than the
linear queue.
CC 33 | Data Structures & Algorithms 7
Advantages and Disadvantages of Circular Queue
Advantages
Circular Queues offer a quick and clean way to store FIFO data with a
maximum size.
Doesn’t use dynamic memory → No memory leaks
Conserves memory as we only store up to our capacity (opposed to a
queue which could continue to grow if input outpaces output.)
Simple Implementation → easy to trust and test
Never has to reorganize / copy data around
All operations occur in constant time O(1)
Disadvantages
Circular Queues can only store the pre-determined maximum number of
elements.
Have to know the max size beforehand
Circular Queue Operation
In a linear queue, we can insert elements until queue becomes full (see
figure 3.6). But once queue becomes full, we cannot insert the next element
even if there is a space in front of queue.
Source: https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation
Figure 3.6. Circular Queue Operation
Consider the following example.
CC 33 | Data Structures & Algorithms 8
Example:
Given the circular queue below (see figure 3.7), perform the operations
given in table 3.2 and write in the table the locations of the front and rear.
Figure 3.7. Example of circular queue operation
Operation front() Rear() Status
1. Initial 0 0
location
2. Enqueue() 0 1
CC 33 | Data Structures & Algorithms 9
3. Enqueue() 0 2
4. Enqueue() 0 3
5. Enqueue() 0 4
6. Dequeue() 1 4
CC 33 | Data Structures & Algorithms 10
7. Enqueue() 1 5
8. Enqueue() 1 6
9. Enqueue() 1 7
10. Dequeue() 2 7
SELF–CHECK!
iCONNECT
You can visit this link for more information about circular queue.
https://www.youtube.com/watch?v=8sjFA-IX-Ww
Title of the video: Circular Queue Implementation - Array
CC 33 | Data Structures & Algorithms 11
DEBUG YOUR KNOWLEDGE
REFERENCES
1. https://www.geeksforgeeks.org/queue-set-1introduction-and-array-
implementation/
2. https://medium.com/@adarsh_menon_/queue-data-structure-practical-
applications-operations-43efec72a58d
3. https://www.studytonight.com/data-structures/queue-data-structure
4. https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-
implementation/#:~:text=Circular%20Queue%20is%20a%20linear,eleme
nts%20until%20queue%20becomes%20full.
5. https://techdifferences.com/difference-between-linear-queue-and-
circular-queue.html
6. https://towardsdatascience.com/circular-queue-or-ring-buffer-
92c7b0193326
CC 33 | Data Structures & Algorithms 12
