Home » Queues | Data Structures for Beginners

AlgorithmsData structures

Queues | Data Structures for Beginners

Arpit Jain

May 8, 2021

0

SaveSavedRemoved 0

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:
  • Addition
  • 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.

Addition ( Enqueue) operation

• 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.

Algorithm for addition

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.