Topics to be covered:
- Definition of queues
- Queues of processes
- Array representation of queues
- Operations on queues with algorithms
- 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.
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’.
- A queue can be mapped on a one-dimensional array. Operations on the queues are:
- 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
- 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.