# Queues | Data Structures for Beginners

## Topics to be covered:

• Definition of queues
• Queues of processes
• Array representation of queues
• Operations on queues with algorithms
• Performance

### Definition

• A queue is a linear data structure of varying sizes i.e. the size of a queue depends upon the number of items currently present in it.
• The size of the queue increases on addition and decreases on deletion.
• The queue is also a dynamic data structure that can enlarge or compress its size.
• The end where all additions are done is called the rear end. The other end from where the deletions are made is called the front end.
• It works on the principle of FIFO(First In First Out) or LILO(Last In Last Out).

## Queue of Processes

• The operating system maintains a queue for scheduled processes that are ready to run.
• The dispatcher picks the process from the front end of the queue and dispatches it to the CPU, and a new process joins at the rear end of the queue.
• When the new processes join in, the size of the queue increases whereas the size of the queue will reduce when processes finish their job and leave the system.

## Array Representation

Consider a queue maintained in an array called Queue[N]. Front points to an empty location in the queue and rear points to a location containing the item ‘G’.

## Queue Operations

• A queue can be mapped on a one-dimensional array. Operations on the queues are:
• Deletion
• A variable called front points to the logical front end of the queue from where the insertion and deletion takes place.
• Similarly, a variable called rear points to the logical rear end of the queue where the new elements can be added.

• Adding an item ‘H’ into the queue.
• Before the item is added into the queue, the Rear is incremented by one to point to the next vacant location.
• The new item ‘H’ is added at location currently being pointed by Rear.
• If more additions are made on the queue, then a stage would come when Rear = N − 1, i.e., last location of the array. Now, no more additions can be performed on the queue. This condition (Rear = N − 1) is called queue full.
``````Enqueue (item): Description: Here QUEUE is an array with N
locations.
FRONT and REAR points to the front and rear of the QUEUE.
ITEM is the value to be inserted.
Steps:
1. If (REAR == N-1) Then [Check for overflow]
2.   Print: Overflow
3. Else
4.    If (FRONT and REAR == -1)
5.       Then [Check if QUEUE is empty]
6.         (a) Set FRONT = 0 (b) Set REAR = 0
7. Else
8.       Set REAR = REAR + 1 [Increment REAR by 1]
[End of Step 4 If]
9. QUEUE [REAR] = ITEM
10. Print: ITEM inserted
[End of Step 1 If]
11. Exit``````

### Deletion ( Dequeue ) operation

• Deleting an item from the queue.
• Before an item is deleted or removed, the Front is incremented by one to point to the next location, i.e., the location containing item ‘A’.
• The item (i.e., ‘A’) is then deleted
• If more deletions are done on this queue, then a stage would reach when there will be no items on the queue, i.e., Front = Rear. This condition (Front = Rear) is called queue empty.
##### Algorithm for deletion
``````Dequeue(): Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of the QUEUE.
1. If (FRONT == -1) [Check for underflow]
2.    Print: Underflow
3. Else
4.    ITEM = QUEUE [FRONT]
5. If (FRONT == REAR) Then [if only one element is left]
6.    (a) Set FRONT = -1 [ Deleting it makes queue empty]
7.    (b) Set REAR = -1
8. Else
9.       Set FRONT = FRONT + 1 [Increment FRONT by 1]
10.   [End of Step 5 If]
11. Print: ITEM deleted [End of Step 1 If]
12. Exit``````

#### Performance

• Space complexity is O(n).
• Time complexity for each operation is O(1).
• The size of the queue, implemented using array, must be defined in advance, i.e., a priori. Moreover, the size cannot be changed.

You can try the practical on this on virtual labs.

We will be happy to hear your thoughts
Hello!👋