Implementation of Queue using Array in C++

A linear queue can be implemented using an Array. Firstly define an array of the desired type, a Front, and a Rear variable. Then, implement the enqueue(), dequeue(), and peek() functions to insert, delete, and fetch the elements respectively.

Representation of Queue using Array

Here is the representation of a Linear Queue with a capacity of 8. There are three elements inserted into the queue. So the Rear is at the index of 2 while the Front is at the index of 0.

Queue Implementation using Array

An example program to implement Queues using an array. The object-oriented implementation encapsulates the Queue data structure using a c++ class.

/**
 * C++ example to demonstrate Queue implementation using Array
 */
#include <iostream>
using namespace std;

// Queue maximum capacity
#define CAPACITY 10

/**
 * Linear Queue implementation using Array
 */
class Queue
{
private:
    // Queue
    int queue[CAPACITY];
    
    // Front position
    int front;
    
    // Rear position
    int rear;
    
public:
    // Constructor
    Queue() : front(-1), rear(-1) {}
    
    // Enqueue new element to the Queue
    void enqueue(int element);
    
    // Dequeue the element from Queue
    int dequeue();
    
    // Returns the Front element without deleting it
    int peek();

    // Check if the Queue is empty
    bool isEmpty();
    
    // Check if the Queue is full
    bool isFull();
    
    // Traverse and display the Queue
    void display(string msg);
};

// Enqueue new element to the Queue
void Queue::enqueue(int element) {
    // Step 1. Return if the Queue is full, proceed otherwise
    if (isFull()) {
        return;
    }
    
    // Step 2. If the Queue is empty, set the Front and Rear to point the first position. Otherwise move the Rear to point the next position.
    if (front == -1) {
        front = rear = 0;
    } else {
        rear++;
    }
    
    // Step 3. Insert the new element at Rear
    queue[rear] = element;
}

// Dequeue the element from Queue
int Queue::dequeue() {
    // Step 1. Return if the Queue is empty, proceed otherwise
    if (isEmpty()) {
        return -1;
    }
    
    // Step 2. Retrieve the element at Front
    int element = queue[front];

    // Step 3. If this is the last element, reset Front and Rear to -1. Otherwise move Front to next position
    if (front == rear) {
        front = -1;
        rear = -1;
    } else {
        front++;
    }
    
    return element;
}

// Returns the Front element without deleting it
int Queue::peek() {
    if (isEmpty()) {
        return -1;
    }
    return queue[front];
}

// Traverse and display the queue
void Queue::display(string msg) {
    cout << msg << endl;
    if (isEmpty()) {
        return;
    }
    
    if (front == rear) {
        cout << queue[front] << " <-- front, rear" << endl;
        return;
    }
    
    cout << queue[front] << " <-- front" << endl;
    for (int i=front+1; i < rear; i++) {
        cout << queue[i] << endl;
    }
    cout << queue[rear] << " <-- rear" << endl;
}

// Check if the Queue is full
bool Queue::isFull() {
    if (rear == (CAPACITY-1)) {
        cout << "Queue is Full" << endl;
        return true;
    }
    return false;
}

// Check if the Queue is empty
bool Queue::isEmpty() {
    if (front == -1) {
        cout << "Queue is Empty" << endl;
        return true;
    }
    return false;
}

// The main function to begin the execution
int main()
{
    // Create a Queue
    Queue queue;
    
    // Enqueue elements (10, 20, 30, 40, and 50)
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    queue.enqueue(40);
    queue.display("Queue after inserting 10 20 30 and 40");
    queue.enqueue(50);
    queue.display("Queue after inserting 50");
    
    // Get the peek element
    int element = queue.peek();
    cout << "Peek element returned " << element << endl;
    
    // Dequeue the elements from Queue
    element = queue.dequeue();
    cout << "Dequeue element returned " << element << endl;
    element = queue.dequeue();
    cout << "Dequeue element returned " << element << endl;
    queue.display("Queue after removing two elements");
}

Output

Queue after inserting 10 20 30 and 40
10 <-- front
20
30
40 <-- rear
Queue after inserting 50
10 <-- front
20
30
40
50 <-- rear
Peek element returned 10
Dequeue element returned 10
Dequeue element returned 20
Queue after removing two elements
30 <-- front
40
50 <-- rear

Operations of Queue

Here, we discuss the algorithm and step-by-step workflow for Enqueue and Dequeue.

Enqueue

Enqueue inserts the new element into the Queue at the Rear side. It can return failure when the Array is full and has no free space.

Algorithm for Enqueue

1. Return if the Queue is Full, proceed otherwise
2. Check if the Queue is empty. If so, set the Front and Rear to point to the first position. Otherwise, move the Rear to point to the next position.
3. Insert the new element at the Rear

Enqueue works in O(1) Time Complexity since it has direct access to the Rear side.

Enqueue examples

The queue is empty initially and the Front and Rear are pointing to -1. The following diagrams illustrate enqueuing the first element to an empty Queue.

The Front and Rear point to some valid position when the queue is not empty. Insert the new element on the rear side since it has free space. Then, change the Rear to point to the new element.

Dequeue

Dequeue removes the element from the queue on the Front side. It can return failure when the Queue is empty.

Algorithm for Deque

1. Return if the Queue is empty, proceed otherwise
2. Retrieve the element at the Front
3. If this is the last element, reset the Front and Rear to -1. Otherwise, move Front to the next position

Dequeue works in O(1) Time Complexity as it works on the Front side.

Dequeue Examples

The queue must be nonempty to perform the Dequeue operation. Retrieve the element present at the Front side and change the Front to point to the next position.

The procedure for Dequeuing the last element differs. The Front position can’t move further because the next element is unavailable. In such a case, reset the Front and Rear to -1 to indicate the queue is empty.

Frequently Asked Questions

When to implement Queue using Array

Array implementation can be the preferred choice when the data is limited in size. It works faster because an array is CPU-friendly for its better cache locality. However, it has the drawback of managing memory space. So, the Circular Queue is generally preferred over the Linear Queue for array-based implementation.

References

• For large and dynamic data, see Queue Implementation using Linked List
• Refer Coding Ninjas for C Program