Queue Implementation

Queue Implementation: Array Implementation of Queue in Data Structure

In the last document, we introduced a new data structure: the queue. we’ll learn how to implement the queue ADT using arrays. During our discussion, we compared its representation to our own lives. It is analogous to a queue in front of any ticket counter or an ice cream shop, as illustrated below.

Here, we have shown a branded ice cream shop that is famous enough to have a queue of people waiting to get one of their choices. The shop owner wants to store the information of these people, so he uses an array to accomplish that. Assuming that we have 8 people and we want to store their information, we’ll have an array as illustrated below:

Here, we’ll maintain an index variable, backInd, to store the index of the rearmost element. When we insert an element, we simply increment the value of backInd and insert the element at the current backInd value. Follow the array below to understand how inserting works:

Now suppose we want to remove an element from the queue. Since a queue follows the FIFO discipline, we can only remove the element at the zeroth index, as that is the element inserted first in the queue. We will remove the element at the zeroth index and shift all the elements to their adjacent left. Follow the illustrations below:

But this removal of the zeroth element and shifting of other elements to their immediate left features O(n) time complexity.

Summing up this method of enqueue and dequeue, we can say:

1. Insertion (enqueue):

   • Increment backInd by 1.
   • Insert the element.
   • Time complexity: O(1).

2. Deletion (dequeue):

   • Remove the element at the zeroth index.
   • Shift all other elements to their immediate left.
   • Decrement backInd by 1.

3. Here, our first element is at index 0, and the rearmost element is at index backInd.

4. Condition for queue empty: backInd = -1.

5. Condition for queue full: backInd = size - 1.

Can there be a better way to accomplish these tasks? The answer is yes.

We can use another index variable called frontInd, which stores the index of the cell just before the first element. We’ll maintain both these indices to bring about all our operations. Let’s now enlist the changes we’ll see after we introduce this new variable:

1. Insertion (enqueue):

   • Increment backInd by 1.
   • Insert the element.
   • Time complexity: O(1).

2. Deletion (dequeue):

   • Remove the element at the zeroth index (no need for that in an array).
   • Increment frontInd by 1.
   • Time complexity: O(1).

3. Our first element is at index frontInd + 1, and the rearmost element is at index backInd.

4. Condition for queue empty: frontInd = backInd.

5. Condition for queue full: backInd = size - 1.

Now, we were able to achieve both operations in constant run time. The new dequeue operation goes as follows:

The act of optimizing a solution/program is very important, and should always strive for a better solution to a problem. And a solution that takes less time is always preferred. So, this is how we implement the queue ADT using an array.