Implementation of Queue using Array

Last Updated on September 22, 2023 by Mayank Dham

Queues are essential in data structures for orderly data processing. Queue implementation becomes a powerful technique for organizing and controlling data flow when arrays are used as the foundation. This method enables first-in, first-out (FIFO) operations, which optimize tasks requiring structured data handling. In this article, we will see the implementation of Queue using Array.

What is the Queue?

A queue is a linear data structure in which there are two sides: the front side and the rear side. It follows the first in first out (FIFO) methodology. This is why it has two sides. From the front side, we will delete the data and from the rear side, we will insert the data in a queue. For example, people who stand in the queue at a bus station to buy a ticket.

Algorithm for the Implementation of Queue using Array

For Insertion:

Step 1: Get the position of the first empty space ( value of the rear variable)

Step 2: Assign the new value to position the rear in an array if the queue is not full.

Step 3: Increment the value of the rear variable

For Deletion:

Step 1: Get the position of the first non-empty element ( value of the front variable )

Step 2: return the value of the element present at the index front if the queue is not empty

Step 3: increment the value of the front variable

Algorithm of the Queue Implementation with an Example

We understood the concept of the queue. Now, we will learn about queue with the algorithm of a queue implementation with an example.

Initialize the front and rear variables with (-1).

Operation 1: enqueue(10)
In this operation, we will insert a new value 10 at the rear position. Before this operation value of the rear was (-1). we will increment the value of the rear position by 1.So now, the new value of the rear will be 0.and the value 10 will be added at position 0.
It is first element into the queue, that is why we will also increment the front position by 1 and the new value of the front will be also 0.

Operation 2: enqueue(20)
In this operation, we will insert a second value 20 at the rear position. Before this operation value of the rear was 0. we will increment the value of the rear position by 1.So now, the new value of the rear will be 1.and the value 20 will be added at position 1.So now, the new value of the front and rear will be 0 and 1 respectively.

Operation 3: dequeue()
In this operation, we will delete the value 10 at the front position. Before this operation value of the front was 0 and the value 10 will be removed at position 0. After the deletion value, we will increment the value of the front position by 1. So now, the new value of the front and rear will be 1 and 1 respectively.

Operation 4: enqeue(30)
In this operation, we will insert a third value 30 at the rear position. Before this operation value of the rear was 1. we will increment the value of the rear position by 1.So now, the new value of the rear will be 2.and the value 30 will be added at position 2.So now, the new value of the front and rear will be 1 and 2 respectively.

Operation 5: enqueue(40)
In this operation, we will insert a fourth value 40 at the rear position. Before this operation value of the rear was 2. we will increment the value of the rear position by 1.So now, the new value of the rear will be 3.and the value 40 will be added at position 3. So now, the new value of the front and rear will be 1 and 3 respectively.

Operation 6: dequeue()
In this operation, we will delete the value 20 at the front position. Before this operation value of the front was 1 and the value 20 will be removed at position 1. After the deletion value, we will increment the value of the front position by 1. So now, the new value of the front and rear will be 2 and 3 respectively.

Program for the Implementation of Queue using Array:

We have already seen how an array can be used to implement a queue. Now, let’s see how to write a program for the implementation of queue using array.

Code Implementation

// java program for the implementation of queue using array
public class StaticQueueinjava {
    public static void main(String[] args)
    {
        // Create a queue of capacity 4
        Queue q = new Queue(4);

        System.out.printf("Initial queue\n");
        q.queueDisplay();

        q.queueEnqueue(10);
        System.out.printf("\nQueue after operation enqueue(10)\n");
        q.queueDisplay();

        q.queueEnqueue(20);
        System.out.printf("\nQueue after operation enqueue(20)\n");
        q.queueDisplay();

        q.queueDequeue();
        System.out.printf("\nQueue after operation dequeue()\n");
        q.queueDisplay();

        q.queueEnqueue(30);
        System.out.printf("\nQueue after operation enqueue(30)\n");
        q.queueDisplay();

        q.queueEnqueue(40);
        System.out.printf("\nQueue after operation enqueue(20)\n");
        q.queueDisplay();

        q.queueDequeue();
        System.out.printf("\nQueue after operation dequeue()\n");
        q.queueDisplay();

    }
}

class Queue {
    static private int front, rear, capacity;
    static private int queue[];

    Queue(int c)
    {
        front = rear = 0;
        capacity = c;
        queue = new int[capacity];
    }

    // function to insert an element
    // at the rear of the queue
    static void queueEnqueue(int data)
    {
        // check queue is full or not
        if (capacity == rear) {
            System.out.printf("\nQueue is full\n");
            return;
        }

        // insert element at the rear
        else {
            queue[rear] = data;
            rear++;
        }
        return;
    }

    static void queueDequeue()
    {
        // if queue is empty
        if (front == rear) {
            System.out.printf("\nQueue is empty\n");
            return;
        }

        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }

            // store 0 at rear indicating there's no element
            if (rear < capacity)
                queue[rear] = 0;

            // decrement rear
            rear--;
        }
        return;
    }


    static void queueDisplay()
    {
        int i;
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }

        System.out.printf("| ");
        for (i = front; i < rear; i++) {
            System.out.printf("%d | ", queue[i]);
        }
        System.out.printf("\n");
        return;
    }
}

Output:

Initial queue
Queue is Empty

Queue after operation enqueue(10)
| 10 | 

Queue after operation enqueue(20)
| 10 | 20 | 

Queue after operation dequeue()
| 20 | 

Queue after operation enqueue(30)
| 20 | 30 | 

Queue after operation enqueue(20)
| 20 | 30 | 40 | 

Queue after operation dequeue()
| 30 | 40 | 

Time complexity: O(N)
Space complexity: O(N)

Application of Queue

• The queue is used for CPU scheduling and disk scheduling
• The queue is used for handling website traffic
• The queue is used to perform Breadth First Search (BFS) traversal
• The queue is used as a buffer on MP3 players and portable CD players.

Conclusion
The implementation of queue using array concludes with a versatile technique that simplifies data management. This approach, based on first-in, first-out processing, provides a useful tool for organizing and optimizing data flow.

Array-based queues strike a balance between simplicity and efficacy, improving your ability to manage tasks that require orderly data handling. Remember the importance of this technique in optimizing processes and strengthening your coding abilities as you apply this knowledge. Array-based queues are a valuable asset in any programmer’s toolkit, whether they are new or experienced.

FAQs on Queue

1. Which data structures can be used for queue implementation?
An array, stack, or linked list can be used to implement a queue. Using an Array is the simplest way to implement a queue.

2. Which operation is used in the queue implementation?
A queue is an object used to manipulate an ordered collection of various data types. Below are the operations which we can perform on the queue.

3. Which is better stack or queue?
The stack can be used to solve recursive problems such as pre-order, post-order, and in-order traversal of the binary tree, whereas the queue can be used to solve problems such as the producer-consumer problem, which involves sequential processing of underlying data. Stack follows LIFO methodology while queue follows FIFO methodology.