Queue Implementation using Single Pointer

Back to: Data Structures and Algorithms Tutorials

Queue Implementation using Single Pointer:

In this article, I will discuss how to Implement a Queue using a Single Pointer in C Language with an Example. Please read our previous article on Introduction to Queue Data Structure. Now, we will learn how to implement a queue using an array.

We’ll implement a queue using a single pointer, explaining its problems and drawbacks. Next, we’ll demonstrate how to implement a queue using two pointers, namely front and rear. Finally, we’ll discuss the drawbacks of the two-pointer approach. So, let’s begin with the implementation of a queue using a single pointer.

We need to use a fixed-size array to implement a queue. Here, we have an array of size 7. Additionally, we need one pointer, which we’ll call rear. Since the array is currently empty, or there is nothing in the queue, the rear is initialized to -1. It’s important to note that -1 is not a valid index in an array; array indices start from 0 onwards. Therefore, -1 indicates that the queue is empty. As we’re explaining the single-pointer approach, there is only one pointer, rear. Now, let’s see how we can insert or delete elements in our queue using only the rear pointer. First, let’s insert a few elements.

Inserting elements into a queue:

If we want to insert elements into a queue, we need to move the rear pointer to the next location in the array and then insert the element at that location.

1.) Move rear to next location:

2.) Insert the element:

In this way, we have inserted a new element into the queue. Now, let’s add a few more elements.

2 is inserted at index 1.

7 is inserted at index 2.

5 is inserted at index 3.

This is how insertion can be done. How much time does it take? Since the steps are simple: move the rear and insert the element, The time taken is constant. Insertion – O (1)

Now, let’s see the deletion process.

Deleting elements from a queue:

Now, we want to delete elements from the queue. Which element can be deleted? We can delete elements from the left side.

In the above queue, we can delete only 4, which is present at index 0, because 4 is the very first element in the queue. Queues follow the First In, First Out (FIFO) discipline, so the element that was inserted first will be deleted first. Suppose we have deleted the element 4 from the queue.

Here, after deleting the element, the 0th index is empty. In an array, we don’t leave blank spaces, so we shouldn’t have any empty spaces. We need to fill that space. To do so, we have to left-shift all the elements present in the array.

As all the elements are shifted by one to the right side, we also need to move the rear pointer to the previous location. In this case, the rear will point to index 2.

So, after deletion, the 0th index becomes vacant, and our queue starts from the 0 index. We shouldn’t have blank spaces in an array. If there are blank spaces, we have to check every time whether there is an element or a blank space. This requires extra work to check the spaces, which is why we avoid blank spaces whenever we are using an array. To occupy the blank space, we fill it with the next element. We shift all the elements to remove the blank space from the array. The time taken to shift the elements will be O(n). Deletion – O (n)

This drawback indicates that deletion takes O(n) time. We aim for the delete operation also to take constant time. To achieve this, we need to implement the queue using the two-pointer approach.

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