DataStructures Series — 6
N.B. This article would make more sense if you read previous articles in this series.
In case you missed last week on the data-structures series here.
We discussed the stack ADT and we wrote some pseudocode using an array to implement it. We also discussed how some popular applications use the stack data structure.
This week we would be discussing the Queue ADT.
The Queue ADT
The queue allows operations at both ends unlike the stack that allows operations only at one end. The insertion is performed at a position called the ‘rear’ and the deletion operation is performed at a position called the ‘front’. The operations in a queue are performed based on the FIFO (First in First out) principle.
Queue Operations:
- EnQueue Element
- DeQueue Element
- Peek Element
EnQueue — This would insert an element at the rear of the queue.
DeQueue — This would remove an element at the front of the queue.
Peek — This would fetch and not remove an element at the front of the queue.
Implementation
One way to implement the Queue ADT is to use an array.
Below is a pseudocode implementation:
- new array {size}- currentRearIndex = 0; - enQueue(element): set array[0] = element,
currentRearIndex++;- deQueue(): if (currentRearIndex == 0), return null
otherwise: value = array[0],
for all elements in array > currentTopIndex,
set array[elementPosition - 1] = array[elementPosition],
set array[currentRearIndex - 1] = NULL,
currentRearIndex--;
return value;- peek(): if (currentRearIndex == 0), return null
otherwise: return array[currentTopIndex];
This implementation is inefficient as we can see, we have to move all elements by a place after every deQueue operation, imagine we had 1 million data in the array, it would mean the the computer would have to perform around a million operations just to remove one element. Another bottleneck we would have is if the queue gets filled up, this would mean we have to create a bigger array and transfer all the data from the old one to the new one. This too can be very expensive if we are dealing with plenty of data. We would discuss other alternatives to implement a queue as we move forward in the series.
Applications:
- Operating Systems Job Scheduling— Queues are used in your Operating system for task scheduling
- Customer Service call management — When you call a customer service and you are told to wait, your call is actually in a queue.
Next week, we would be discussing another interesting Abstract Data Type, The Linked List.
REFERENCES:
