Array implementation of Queue

Array implementation of Queue and its Operations in Data Structure

In the last docs on the implementation of queues using arrays, we discussed the basic operations and their optimal methods. We concluded that by maintaining two index variables, frontInd and backInd, we can achieve both enqueue (insertion) and dequeue (deletion) in constant time complexity.

1. Insertion (enqueue):

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

2. Deletion (dequeue):

   • Remove the element at index frontInd + 1.
   • Increment frontInd by 1.
   • Time complexity: O(1).

3. Indices:

   • The first element is at index frontInd + 1.
   • The rearmost element is at index backInd.

4. Conditions:

   • Condition for queue empty: frontInd = backInd.
   • Condition for queue full: backInd = size - 1.

Given array below represents a queue:

To implement this, we’ll use a structure with the following members:

1. size: to store the size of the array.

2. frontInd: to store the index prior to the first element.

3. backInd: to store the index of the rearmost element.

4. arr: to store the address of the array dynamically allocated in the heap.

struct queue
{
    int size;
    int frontInd;
    int backInd;
    int* arr;
};

Now to use this struct element as a queue, you just need to initialize its instances as:

1. struct Queue q; (we are not dynamically allocating q here for now, as we did in stacks).
2. Use dot here, and not arrow operator to assign values to struct members, since q is not a pointer.
3. q.size = 10; (this gives size element the value 10)
4. q.frontInd = q.backInd = -1;(this gives both the indices element the value -1)
5. Use malloc to assign memory to the arr element of struct q. And this is how you initialize a queue. We will now devote our attention to two important operations in a queue: enqueue and dequeue.

Enqueue:

Enqueuing is inserting a new element in a queue. Prior to inserting an element into a queue, we need to take note of a few points.

1. First, check if the queue is already not full.
2. If it is, it is the case of queue overflow, else just increment backInd by 1, insert the new element there. Follow the illustration below

Dequeue:

Dequeuing is the process of deleting the element in a queue that is the first among all the elements to get inserted. Before deleting that element from a queue, we need to follow these points:

3. First, check if the queue is already not empty.

4. If it is empty, this indicates a case of queue underflow. Otherwise, just increment frontInd by 1. In arrays, we don’t delete elements; we simply stop referring to the element. Follow the illustration below:

Condition for isEmpty:

• If frontInd equals backInd, then there are no elements in our queue, indicating an empty queue.

Condition for isFull:

• If backInd equals (size of the array) - 1, then there is no space left in our queue, indicating a full queue.

So, these are the basic operations of a queue. We have implemented everything using arrays. We’ll see the programming part in the next Docs. Keep up with the docs, and you won’t miss anything.