Queue Data Structure
Check out one in-depth details about queue data structure
Queue is also a linear and logical data structure, meaning it can be implemented using the physical data structure either Array or a Linked List. Queue works on the principle of First In First Out (FIFO). This means the first element inside the queue will be removed first, like cars passing through a toll tax following each other.
The queue data structure uses both ends for performing operations, known as Front and Rear, using Rear elements can be added to the queue, and using the Front we can remove elements from the queue.
Abstract Data Type
- Space for storing data, elements
- Front pointer for deletion
- Rear pointer for insertion
Operations
- Enqueue(x), to insert an element in the queue
- Dequeue( ), to remove an element from the queue
- isEmpty( ), to check if the queue is empty
- isFull( ), to check if the queue is full
Queue using an Array
- Queue using a single pointer
- Queue using front and rear pointer
Queue using a single pointer
If we think of only insertion here, it’s quite fruitful! just increase the rear index pointer and add an element at that index at a constant time, but when it comes to deleting an element, you will notice the drawback.
When we delete an element from a certain index, that index will become empty, so we do not keep the position empty in an array. To fill that particular position we have to shift all array elements towards the front.
This is the drawback every time we have to check after deletion for any vacant location. To overcome this problem we use the two pointer method.
Queue using front and rear pointers (two-pointer method)
Here we will use two pointers front and rear, in an array insert elements using the rear as you already know, and delete using the front pointer.
So here after deleting an element, instead of shifting all other elements forward we only move the front pointer to the next vacant location. Just move the front pointer over the element and delete, that’s it!
Get Owais Ahmad’s stories in your inbox
Join Medium for free to get updates from this writer.
here both insertion and deletion take constant time, O(1).
Drawbacks of Queue Using an Array
We can not use the spaces of deleted elements. because due to the deletion the front moves towards the rear as mentioned earlier, and also as you know insertion is always being done at the rear. So here every location can be used only once.
In addition to that sometimes we will end up with a situation where the queue becomes empty as well as full at the same time. because we know that when (rear == size -1 ) our queue is full and when (front === rear) queue is empty.
solution for that is Resetting pointers and Circular Queue.
Resetting pointers
At any time if the Queue is becoming empty, bring the front and rear pointers at the beginning, and reinitialize them from the beginning. But the problem is that, when a Queue is not getting empty at any time we can not reset the pointers.
Circular Queue
The type of Queue where the rear after reaching the end will move back to the first index where it started and insert elements from there again if the front has deleted some elements and there is space available.
Note! wherever the front is pointing it must be left empty. therefore circular queue store elements size -1.
Circular Queue formula
rear = (rear + 1)% size;
In a circular queue, this formula ensures that the rear index wraps around when it reaches the end of the queue, it allows efficient reuse of space. The modulo (%) operation ensures that when the rear reaches the last index (size-1), it wraps around to index 0.
Queue using Linked List
As you already know how a linked list works, here we implement a linked list in a way that acts as a Queue we can only add elements at the rear of the linked list and remove them from the front.
Double ended Queue
Insertion and deletion can be done at both ends, FIFO principle is not strictly followed here.
we have two types of double-ended queues one is input-restricted and another is output-restricted.
Input-restricted
Here the front is only used for deletion we can not use it for insertion, but the rear will be used for both insertion and deletion.
Output-restricted
Here the rear is only used for insertion we can not use it for deletion, but the front will be used for both insertion and deletion.
Happy Learning! :😊
