Queue Implementation using Two Pointers

Back to: Data Structures and Algorithms Tutorials

Queue Implementation using Two Pointers:

In this article, I will discuss Queue Implementation using Two Pointers in C Language with an Example. Please read our previous article on how to Implement a Queue using a Single Pointer in C.

Queue Implementation using Two Pointers

Before discussing the two-pointer approach, let’s understand the drawbacks of the one-pointer approach with an example.

These people are standing in a queue to avail themselves of some services, following a first-in-first-out (FIFO) fashion. When a new person arrives, they join the queue from the right-hand side. When a person finishes their task, they leave the queue from the left-hand side. Let’s observe what happens when a person leaves the queue, which is equivalent to deletion.

After deletion, the space will be empty. Therefore, that space should be occupied. Typically, in a queue, when a person leaves, all the people behind that person move one step forward.

When one person leaves the queue, all the people shift left by one step. So, how many steps are taken when one person steps out from the queue? N steps are taken (where n = the total number of people in the queue). Therefore, the time for deletion is O(n).

Can the counter move one step to the right instead? If that’s possible, then we don’t have to shift all those people. That’s the idea we will use to implement a queue using two pointers in an array. We will use one pointer for insertion and the other for deletion. So, instead of shifting the elements, we will move the pointers. Let us see the implementation.

Implementation of a Queue using Two Pointers:

Here, we have taken a fixed-size array with a size of 7. We have two pointers, front and rear, both pointing at -1, indicating that there is nothing in the queue. So, currently, both front and rear are at -1 and are equal. Let’s see how to insert elements.

Insertion of elements into the queue:

To insert an element, we need to move the rear pointer to the next location and then insert the element.

It is simple to insert an element into the queue. How much time does it take to insert an element? It takes constant time. Let’s insert a few more elements.

Here, we’ve inserted some elements into the queue. The rear pointer is pointing at the last element, which is the most recently inserted element. However, even though the first index is 0, the front pointer is still pointing at -1. Let’s see how to delete elements.

Deletion of elements from the queue:

To delete an element, we need to move the front pointer to its next location and then remove that element.

1.) Move front to next index:

2.) Delete the element:

Deletion is also simple. We need to increment the front location and then delete the element from the queue. Let’s delete one more element.

That’s how we deleted another element. How much time does deletion take? It also takes constant time. The idea here is the same as the example we explained above. You can think of it as people standing at their own places while the counter is moving as people leave the queue. One more thing to observe is that the front pointer is pointing before the first element, not at the first element in the queue. Meanwhile, the rear pointer is pointing at the last element in the queue. Logically, if you see, the counter will not be on the first person, it will be in front of the first person. So, the front pointer is acting like a counter.

Now, both enqueue (insertion) and dequeue (deletion) operations take constant time, so our queue becomes faster.

Enqueue – O (1)

Dequeue – O (1)

Now, let us look at the condition of empty queues and full queues.

When the queue is empty:

Here, only one element is present in the queue. Let’s delete this element.

Now, there is nothing in the queue. So, what’s the condition when the queue becomes empty? When the front and rear pointers are equal, or we can say both are pointing at the same index, it means the queue is empty. Initially, when we hadn’t inserted any element in the queue, at that time also, the front and rear pointers were equal. So, whenever they are equal, it means the queue is empty.

Empty Condition: if (Front == Rear)

Why is the front pointing before the first element and not at the first element?

There are two elements in the queue. The front is pointing before the first element, and the rear is pointing at the last element. Suppose the front is pointing to the first element instead of pointing before the first element,

Now, if we delete 3,

Now, both are pointing at the same index. As we know, front == rear is the empty condition, so is the queue empty? No. So, this is a problem. Let’s assume front == rear is not the empty condition. Let’s delete this single element also.

Here, the front is greater than the rear. Now, the queue is empty. So, if you say that the front should point at the first element, then you have to write Front > Rear as the queue empty condition. So, if you want, you can implement it like this, but you have to make a front point to the first element. However, we prefer that front pointing before the first element is more comfortable. Let’s see the condition when the queue is full.

When the queue is full:

Here, we have inserted 7 elements in the queue. Can we add one more element? No, there is no space because the queue is already full. So, how can we say the queue is full? The rear pointer is pointing at index 6, and the size of the array is 7, so the queue full condition will be Rear = Size – 1.

Full Condition: Rear = Size – 1;

So, we have studied how to implement a queue using 2 pointers in an array.

Key Points:

1. The front is used for deletion.
2. The rear is used for insertion.
3. Initially, the Front is equal to the Rear and both are pointing at -1
4. The front is pointing before the first element, and the rear is pointing at the last element.
5. Enqueue – O (1), Dequeue – O (1)
6. Queue Empty Condition: if (Front == Rear)
7. Queue Full Condition: Rear = Size – 1;

In the next article, I will discuss how to Implement a Queue using an Array in C Language. In this article, I explain how to Implement a Queue Data Structure using Two Pointers in C Language. I hope you enjoy this article on implementing a Queue Data Structure using Two Pointers.