Queue

A Queue Data Structure is a fundamental concept in computer science used for storing and
managing data in a specific order. Queue is a linear data structure that follows FIFO (First In
First Out) Principle, so the first element inserted is the first to be popped out.
FIFO Principle in Queue:
FIFO Principle states that the first element added to the Queue will be the first one to be
removed or processed. So, Queue is like a line of people waiting to purchase tickets, where the
first person in line is the first person served. (i.e. First Come First Serve).

Basic Terminologies of Queue

• Front: Position of the entry in a queue ready to be served, that is, the first entry that
will be removed from the queue, is called the front of the queue. It is also referred as
the head of the queue.
• Rear: Position of the last entry in the queue, that is, the one most recently added, is
called the rear of the queue. It is also referred as the tail of the queue.
• Size: Size refers to the current number of elements in the queue.
• Capacity: Capacity refers to the maximum number of elements the queue can hold.
REPRESENATION OF QUEUE
To implement a queue of size n using an array, the operations are as follows:
• Enqueue: Adds new elements to the end of the queue. Checks if the queue has space
before insertion, then increments the size.
• Dequeue: Removes the front element by shifting all remaining elements one position
to the left. Decrements the queue size after removal.
• getFront: Returns the first element of the queue if it’s not empty. Returns -1 if the
queue is empty.
• Display: Iterates through the queue from the front to the current size and prints each
element.
Linked List implementation of Queue
In a linked queue, each node of the queue consists of two parts i.e. data part and the link part.
Each element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear
pointer. The front pointer contains the address of the starting element of the queue while the
rear pointer contains the address of the last element of the queue
Insertion and deletions are performed at rear and front end respectively. If front and rear both
are NULL, it indicates that the queue is empty.
The linked representation of queue is shown in the following figure.

Types of Queues
There are four different types of queues that are listed as follows -
 o Simple Queue or Linear Queue
o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)
Let's discuss each of the type of queue.

Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which
the deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even
though the space is available in a Linear Queue. In this case, the linear Queue shows the
overflow condition as the rear is pointing to the last element of the Queue.

Operations on Simple Queue

1. Enqueue:
The enqueue() is a data manipulation operation that is used to insert elements into the stack.
The following algorithm describes the enqueue() operation in a simpler way.
Algorithm
1. START
2. Check if the queue is full.
3. If the queue is full, produce overflow error and exit.
4. If the queue is not full, increment rear pointer to point the next empty space.
5. Add data element to the queue location, where the rear is pointing.
6. return success.
7. END
Dequeue:
The dequeue() is a data manipulation operation that is used to remove elements from the stack.
The following algorithm describes the dequeue() operation in a simpler way.
Algorithm
1. START
2. Check if the queue is empty.
3. If the queue is empty, produce underflow error and exit.
4. If the queue is not empty, access the data where front is pointing.
5. Increment front pointer to point to the next available data element.
6. Return success.
7. END

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known as
Ring Buffer, as all the ends are connected to another end. The representation of circular queue
is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If the
empty space is available in a circular queue, the new element can be added in an empty space
by simply incrementing the value of rear. The main advantage of using the circular queue is
better memory utilization.
To know more about the circular queue, you can click the link - circular-queue

Priority Queue
It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -
Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.
There are two types of priority queue that are discussed as follows -
o Ascending priority queue - In ascending priority queue, elements can be inserted in
arbitrary order, but only smallest can be deleted first. Suppose an array with elements
7, 5, and 3 in the same order, so, insertion can be done with the same sequence, but the
order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted in
arbitrary order, but only the largest element can be deleted first. Suppose an array with
elements 7, 3, and 5 in the same order, so, insertion can be done with the same sequence,
but the order of deleting the elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from both
front and rear ends of the queue. Deque can be used as a palindrome checker means that if we
read the string from both ends, then the string would be the same.
Deque can be used both as stack and queue as it allows the insertion and deletion operations
on both ends. Deque can be considered as stack because stack follows the LIFO (Last In First
Out) principle in which insertion and deletion both can be performed only from one end. And
in deque, it is possible to perform both insertion and deletion from one end, and Deque does
not follow the FIFO principle.
The representation of the deque is shown in the below image -
Circular Queue
Why was the concept of the circular queue introduced?
There was one limitation in the array implementation of Queue. If the rear reaches to the end
position of the Queue then there might be possibility that some vacant spaces are left in the
beginning which cannot be utilized. So, to overcome such limitations, the concept of the
circular queue was introduced.
As we can see in the above image, the rear is at the last position of the Queue and front is
pointing somewhere rather than the 0th position. In the above array, there are only two elements
and other three positions are empty. The rear is at the last position of the Queue; if we try to
insert the element then it will show that there are no empty spaces in the Queue. There is one
solution to avoid such wastage of memory space by shifting both the elements at the left and
adjust the front and rear end accordingly. It is not a practically good approach because shifting
all the elements will consume lots of time. The efficient approach to avoid the wastage of the
memory is to use the circular queue data structure.
What is a Circular Queue?
A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out)
principle except that the last position is connected to the first position in a circular queue that
forms a circle. It is also known as a Ring Buffer.

Key Differences Between Linear Queue and Circular Queue

The table below summarizes the key differences between linear queues and circular queues:

Feature Linear Queue Circular Queue

Linear, with a fixed start Circular, with the end connected back
Structure and end to the start
Feature Linear Queue Circular Queue

Representation Array or linked list Array or linked list

Inefficient, can lead to

Efficient, utilizes all available space
Memory Utilization wastage of space

At the rear, but wraps around if the end

Insertion Always at the rear of the array is reached and space is
(Enqueue) available at the front

From the front, but wraps around if

Always from the front
Deletion (Dequeue) necessary

Occurs when the rear Occurs when the queue is full and
reaches the maximum size there is no space even after wrapping
Overflow Condition of the array around

Occurs when trying to

Occurs when trying to dequeue from
Underflow dequeue from an empty
an empty queue
Condition queue

Front and Rear Simple indices indicating Indices that wrap around, requiring
Indicators the start and end positions modulo operations

Implementation More complex due to the need to

Simpler
Complexity manage wrapping around

Simple scenarios where Scenarios where efficient memory

memory usage is not a usage is critical, such as in systems
Example Use Cases concern with limited memory

The circular queue has more advantages than a linear queue. Other advantages of circular
queue are:
o Easier for insertion-deletion: In the circular queue, elements can be inserted
easily if there are vacant locations until it is not fully occupied, whereas in the
case of a linear queue insertion is not possible once the rear reaches the last
index even if there are empty locations present in the queue.
o Efficient utilization of memory: In the circular queue, there is no wastage of
memory as it uses the unoccupied space, and memory is used properly in a
valuable and effective manner as compared to a linear queue.
 o Ease of performing operations: In the linear queue, FIFO is followed, so the
element inserted first is the element to be deleted first. This is not the scenario
in the case of the circular queue as the rear and front are not fixed so the order
of insertion-deletion can be changed, which is very useful.

Algorithm
Insertion of an element
Steps:

1. If ((REAR+1) MOD LENGTH = FRONT) then

2. Print "Queue is full"

3. Exit

4. Else

5. CQIREAR] = ITEM

6. REAR = (REAR +1) MOD LENGTH

7. EndIf

8. Stop
 Algorithm

Deletion of an element
Steps:

1. If (REAR= FRONT) then

2. Print "Qucue is empty"

3. Exit

4. Else

[Link]= CQ(FRONT]

6. FRONT (FRONT + 1) MOD LENGTH

7. EndIf
8. Stop

SORTING
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the
way to arrange data in a particular order. Most common orders are in numerical or
lexicographical order.
The importance of sorting lies in the fact that data searching can be optimized to a very
high level, if data is stored in a sorted manner. Sorting is also used to represent data in
more readable formats.
MERGE SORT
Sort the array given below using merge sort.

The merge sort algorithm uses a function merge which combines the sub-arrays to form a sorted
array. While the merge sort algorithm recursively divides the list into smaller lists, the merge
algorithm conquers the list to sort the elements in individual lists. Finally, the smaller lists are
merged to form one list.
To understand the merge algorithm, consider the figure below which shows how we merge
two lists to form one list. For ease of understanding, we have taken two sub-lists each
containing four elements. The same concept can be utilized to merge four sub-lists containing
two elements, or eight sub-lists having one element each.
To understand merge sort, we take an unsorted array as the following −

We know that merge sort first divides the whole array iteratively into equal halves unless the
atomic values are achieved. We see here that an array of 8 items is divided into two arrays of
size 4.

This does not change the sequence of appearance of items in the original. Now we divide these
two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more be divided.

Now, we combine them in exactly the same manner as they were broken down. Please note the
color codes given to these lists.
We first compare the element for each list and then combine them into another list in a sorted
manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the target
list of 2 values we put 10 first, followed by 27. We change the order of 19 and 35 whereas 42
and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values, and merge
them into a list of found data values placing all in a sorted order.

After the final merging, the list becomes sorted and is considered the final solution.
Merge Sort Algorithm
Merge sort keeps on dividing the list into equal halves until it can no more be divided. By
definition, if it is only one element in the list, it is considered sorted. Then, merge sort combines
the smaller sorted lists keeping the new list sorted too.

INSERTION SORT
Insertion sort is a very simple method to sort numbers in an ascending or descending order.
This method follows the incremental method. It can be compared with the technique how cards
are sorted at the time of playing a game.
This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is
always sorted. For example, the lower part of an array is maintained to be sorted. An element
which is to be 'inserted' in this sorted sub-list, has to find its appropriate place and then it has
to be inserted there. Hence the name, insertion sort.
The array is searched sequentially and unsorted items are moved and inserted into the sorted
sub-list (in the same array). This algorithm is not suitable for large data sets as its average and
worst case complexity are of (n2), where n is the number of items.
Insertion Sort Algorithm
Now we have a bigger picture of how this sorting technique works, so we can derive simple
steps by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Pseudocode
Example
We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position. It swaps 33 with 27. It also checks with all the
elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and
27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10. These values
are not in a sorted order.

So they are swapped.

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

We swap them again.

By the end of third iteration, we have a sorted sub-list of 4 items.

This process goes on until all the unsorted values are covered in a sorted sub-list.

Selection Sort Algorithm

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. That
is: we first find the smallest value in the array and exchange it with the element in the first
position, then find the second smallest element and exchange it with the element in the
second position, and we continue the process in this way until the entire array is sorted.
Example

Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first position where
14 is stored presently, we search the whole list and find that 10 is the lowest value.

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list,
appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner.

We find that 14 is the second lowest value in the list and it should appear at the second place. We
swap these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.
The same process is applied to the rest of the items in the array −

..

Time Complexity Analysis of Selection Sort:

• Best-case: O(n2), best case occurs when the array is already sorted. (where n is the
number of integers in an array)
• Average-case: O(n2), the average case arises when the elements of the array are in a
disordered or random order, without a clear ascending or descending pattern.
• Worst-case: O(n2), The worst-case scenario arises when we need to sort an array in
ascending order, but the array is initially in descending order.
The time complexity of the Selection sort remains constant regardless of the input array's initial
order. At each step, the algorithm identifies the minimum element and places it in its correct
position. However, the minimum element cannot be determined until the entire array is
traversed.
Breakdown for Time Complexity for Selection Sort:
Number of iterations Comparisons

1st (n-1)

2nd (n-2)

3rd (n-3)

........ ........

last 1

• The number of comparisons in selection sort can be calculated as the sum of (𝑛 −

1) + (𝑛 − 2) + (𝑛 − 3)+. . . +1 , which is approximately equal to 𝑛(𝑛 − 1)/2 or
roughly n^2. This results in a time complexity of O(n^2).
• Another way to analyze the complexity is by observing the number of loops, which in
selection sort is two nested loops. Hence, the overall complexity is proportional to n^2.
Auxiliary Space Complexity Analysis of Selection Sort:
• Space Complexity: O(1), as no extra space is required for the Selection sort algorithm

Difference between Insertion sort and Selection sort

Insertion sort and selection sort are two popular sorting algorithms, and their main difference
lies in how they select and place elements in a sorted sequence.
Selection Sort:
1. In selection sort, the input array is divided into two parts: a sorted part and an unsorted
part.
2. The algorithm repeatedly finds the minimum element in the unsorted part and swaps it
with the leftmost element of the unsorted part, thus expanding the sorted part by one
element.
3. Selection sort has a time complexity of O(n^2) in all cases.
Insertion Sort:
1. In insertion sort, the input array is also divided into two parts: a sorted part and an
unsorted part.
 The algorithm picks up an element from the unsorted part and places it in the correct
position in the sorted part, shifting the larger elements one position to the right.
Insertion sort has a time complexity of O(n^2) in the worst case, but can perform better
on partially sorted arrays, with a best-case time complexity of O(n).
Main differences:
2. Selection sort scans the unsorted part to find the minimum element, while insertion sort
scans the sorted part to find the correct position to place the element.
Selection sort requires fewer swaps than insertion sort, but more comparisons.
Insertion sort is more efficient than selection sort when the input array is partially sorted
or almost sorted, while selection sort performs better when the array is highly unsorted.
In summary, both algorithms have a similar time complexity, but their selection and
placement methods differ. The choice between them depends on the characteristics of
the input data and the specific requirements of the problem at hand.

Insertion Sort Selection Sort

1. Inserts the value in the presorted array to sort the Finds the minimum / maximum
set of values in the array. number from the list and sort it in
ascending / descending order.

2. It is a stable sorting algorithm. It is an unstable sorting algorithm.

3. The best-case time complexity is Ω(N) when the For best case, worst case and
array is already in ascending order. It have Θ(N2) average selection sort have
in worst case and average case. complexity Θ(N2).

4. The number of comparison operations performed The number of comparison

in this sorting algorithm is less than the swapping operations performed in this sorting
performed. algorithm is more than the swapping
performed.

5. It is more efficient than the Selection sort. It is less efficient than the Insertion
sort.

6. Here the element is known beforehand, and we The location where to put the
search for the correct position to place them. element is previously known we
 Insertion Sort Selection Sort

search for the element to insert at

that position.

7. The insertion sort is used when: The selection sort is used when
The array is has a small number of elements A small list is to be sorted
There are only a few elements left to be sorted The cost of swapping does not
matter
Checking of all the elements is
compulsory
Cost of writing to memory matters
like in flash memory (number of
Swaps is O(n) as compared to O(n2)
of bubble sort)

8. The insertion sort is Adaptive, i.e., efficient for Selection sort is an in-place
data sets that are already substantially sorted: the comparison sorting algorithm
time complexity is O(kn) when each element in
the input is no more than k places away from its
sorted position

Compare selection sort, insertion sort, and merge sort in terms of time complexity.

1. Selection Sort
Selection sort works by repeatedly finding the minimum element from the
unsorted part and placing it at the beginning.
• Best Case: O(n²)
• Average Case: O(n²)
• Worst Case: O(n²)
Explanation:
Even if the array is already sorted, selection sort still compares each element
with the rest of the array to find the minimum. Hence, the number of
comparisons remains the same in all cases.
2. Insertion Sort
Insertion sort builds the sorted array one element at a time by inserting each
element into its correct position.
• Best Case: O(n)
• Average Case: O(n²)
• Worst Case: O(n²)
Explanation:
• In the best case (already sorted), only one comparison is needed per
element → O(n).
• In the worst case (reverse order), each element must be compared and
shifted multiple times → O(n²).
• Hence, performance depends on how sorted the data already is.

3. Merge Sort
Merge sort uses the divide-and-conquer approach:
• Divide the array into halves
• Sort each half recursively
• Merge the sorted halves
• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)
Explanation:
The array is always divided into log n levels, and merging at each level takes
O(n) time. Therefore, total time is O(n log n), regardless of input order.
Comparison Summary Table

Algorithm Best Case Average Case Worst Case Key Idea

Selection Sort O(n²) O(n²) O(n²) Find minimum each time

Insertion Sort O(n) O(n²) O(n²) Insert into sorted part

Merge Sort O(n log n) O(n log n) O(n log n) Divide and merge

Which sorting algorithm is best suited for a nearly sorted array? Justify your answer.
Insertion sort is the best-suited algorithm for nearly sorted arrays because it runs in almost
linear time when the array is already close to sorted, outperforming more complex algorithms
like Merge Sort or QuickSort in such cases.
Why Insertion Sort Works Best
• Time Complexity Advantage:
o Worst case: 𝑂(𝑛2 )
o Best case (already sorted): 𝑂(𝑛)
o For nearly sorted arrays, the number of inversions is small, so insertion sort
performs close to 𝑂(𝑛).
• Adaptive Nature: Insertion sort adapts to the degree of disorder. If only a few elements
are misplaced, it requires minimal swaps and comparisons.
• Low Overhead: Unlike Merge Sort or Heap-based approaches, insertion sort doesn’t
require extra memory or complex recursive calls.
Suppose we have the array:
[1, 2, 3, 5, 4, 6, 7]
• Step 1: Compare 5 and 4 → swap them.
• Step 2: Array becomes [1, 2, 3, 4, 5, 6, 7].
• Done! Only one swap was needed.
If we used Merge Sort or QuickSort, the algorithm would still go through all recursive steps,
taking much longer.
Linear Search
(Linear Search) LINEAR(DATA, N, ITEM, LOC)

Here DATA is a linear array with N elements, and ITEM is a given item of information. This
algorithm finds the location LOC of ITEM in DATA, or sets LOC:= 0 if the search is
unsuccessful.

1. [Insert ITEM at the end of DATA.] Set DATA[N + 1] := ITEM.

2. [Initialize counter.] Set LOC : 1.

3. [Search for ITEM.]

Repeat while DATA[LOC] ITEM:

Set LOC: LOC + 1.

[End of loop.]

4. [Successful?] If LOC = N + 1, then

Binary Search Algorithm

Binary Search algorithm is an interval searching method that performs the searching in
intervals only. The input taken by the binary search algorithm must always be in a sorted array
since it divides the array into subarrays based on the greater or lower values. The algorithm
follows the procedure below −
Step 1 − Select the middle item in the array and compare it with the key value to be searched.
If it is matched, return the position of the median.
Step 2 − If it does not match the key value, check if the key value is either greater than or less
than the median value.
Step 3 − If the key is greater, perform the search in the right sub-array; but if the key is lower
than the median value, perform the search in the left sub-array.
Step 4 − Repeat Steps 1, 2 and 3 iteratively, until the size of sub-array becomes 1.
Step 5 − If the key value does not exist in the array, then the algorithm returns an unsuccessful
search.
Example
For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the
process of binary search with a pictorial example. The following is our sorted array and let us
assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2
Here it is, 0 + (9 - 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find
that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we
have a sorted array, so we also know that the target value must be in the upper portion of the
array.

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.
The value stored at location 7 is not a match, rather it is less than what we are looking for. So,
the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be
made to very less numbers.
Implementation
Binary search is a fast search algorithm with run-time complexity of (log n). This search
algorithm works on the principle of divide and conquer. For this algorithm to work properly,
the data collection should be in a sorted form.