Back to: Data Structures and Algorithms Tutorials

How to Implement Queue using Array in C Language:

In this article, I will discuss how to Implement a Queue using an Array in C Language with Examples. Please read our previous article on how to Implement a Queue using Two-Pointers.

Implementing Queue using Array in C:

For implementing a queue using an array, we require the following things:

• A fixed-size array
• The size of that array
• Two pointers, which are front and rear.

We will combine all these things under a structure because they are all related to a queue. So, let’s define a queue structure.

struct Queue {
    int size;
    int front;
    int rear;
    int *Q;
}

In the Queue structure, we have defined four members: the size of the array, front and rear pointers, and an int type pointer Q that will create an array of the given size at runtime (dynamically from the heap) of the program. Now, let’s see how to create a variable of type Queue structure and how to initialize it. Assume that the following code is being written in the main function.

struct Queue q;

Here, q is an object of type Queue structure. Once we create this object, we will get the following members: size, front, rear, and Q (pointer to an array).

Front and rear are not memory address pointers; they are simply index pointers. They will point to the elements, which is why we refer to them as pointers. Once the object is created, i.e., q, let’s initialize its members. The first member is the size, which we will take from the user at runtime.

printf ("Enter the size of the queue: ");
scanf("%d", &q.size);

We print a message to the user, “Enter the size of the queue,” and then store the size in the q.size variable, which is a data member of the Queue structure. Suppose the size is 5; then, an array of size 5 will be created dynamically.

q.Q = (int *) malloc (q.size * sizeof(int));

Here, we have dynamically allocated memory from the heap for array Q using the malloc function. For shorter statements, you can allocate memory with the new keyword. Now, we have to initialize the front and rear index pointers. Initially, they will both point to -1.

q.front = -1;
q.rear = -1;

You can also initialize them together in a single statement. These are the steps required to initialize a queue. Now, let’s look at the functions or operations that we can perform on a queue. We can mainly perform enqueue and dequeue operations on a queue. We can perform other operations as well, but for now, let’s focus on how to implement these two operations.

Enqueue Function:

void enqueue (Queue *q, int x);

This is the prototype of the enqueue function. It takes two parameters: *q, a pointer to an object of type Queue, and x, an integer that we want to insert into the queue. In the enqueue or insertion operation, first, we have to check whether the queue has space. If there is no space, it means the queue is full, and we cannot insert more elements. Assume that all the following code is written in the enqueue function.

if (q->rear == q->size-1)

Here, we use the condition to check if the queue is full. If this condition is true, then we print a message to the user saying, “Queue is Full.”

printf (“Queue is Full”);

If the queue is not full, then

else {
    q->rear++;
    q->Q[q->rear] = x;
}

To insert an element, we increment the rear pointer by one and then insert the element. So, we first increment the rear pointer, q->rear++, and then insert the element at the rear pointer location, q->Q[q->rear] = x. That’s all about enqueue, which is the insertion of an element in a queue. If you look at the steps, they are very simple. So, the time taken by the enqueue function is constant, i.e., O(1).

Complete Enqueue Function:

void enqueue(struct Queue * q, int x) {
    if (q -> rear == q -> size - 1)
        printf("Queue is Full");
    else {
        q -> rear++;
        q ->Q[q -> rear] = x;
    }
}

Now, let us look at the dequeue operation.

Dequeue Function:

void dequeue (Queue *q);

This is the prototype of the dequeue function. It takes only one parameter, a pointer, to an object in the Queue structure.

int x = -1;

Here, we initialized a variable x to -1. Before deleting the element, we check whether there are any elements in the queue. If there are no elements (i.e. if the front and rear are equal), the queue is empty, and we cannot delete any elements.

if (q->front == q->rear){
    printf("Queue is Empty");
}

Here, we first check if the front is equal to the rear. If this condition is true, we print a message to the user: “Queue is Empty.” However, if elements are present, then we proceed with the deletion process.

else {
    q->front++;;
    x=q->Q[q->front];
}

For deleting an element, we move the front pointer to the next location, i.e., q->front++, and then delete the element by storing it in a variable, x = q->Q[q->front].

return x;

At the end of the function, we return the value of x, which holds the deleted element.

Note: If the queue is empty, x retains the value -1, indicating that no element was dequeued. Therefore, when the function returns -1, it signifies that the queue is empty.

Also, in dequeue, the steps are very simple. So, the time taken by this function will be constant, i.e., O (1).

Complete Dequeue Function:

int dequeue(struct Queue * q) {
    int x = -1;
    if (q -> front == q -> rear)
        printf("Queue is Empty\n");
    else {
        q -> front++;
        x = q -> Q[q -> front];
    }
    return x;
}

Let’s look at the complete program of enqueue and dequeue in C language.

Program to Insert and Delete (Enqueue / Dequeue) in a Queue using C Language:

#include <stdio.h>
#include <stdlib.h>

struct Queue {
    int size;
    int front;
    int rear;
    int * Q;
};

void create(struct Queue * q, int size) {
    q -> front = q -> rear = -1;
    q -> Q = (int * ) malloc(q -> size * sizeof(int));
}

void enqueue(struct Queue * q, int x) {
    if (q -> rear == q -> size - 1)
        printf("Queue is Full");
    else {
        q -> rear++;
        q ->Q[q -> rear] = x;
    }
}

int dequeue(struct Queue * q) {
    int x = -1;

    if (q -> front == q -> rear)
        printf("Queue is Empty\n");
    else {
        q -> front++;
        x = q -> Q[q -> front];
    }
    return x;
}

void Display(struct Queue q) {
    int i;

    for (i = q.front + 1; i <= q.rear; i++)
        printf("%d ", q.Q[i]);
    printf("\n\n");
}

int main() {
    struct Queue q;
    int x = 0,s;
    
    printf("Enter the size of the queue: ");
    scanf("%d", &q.size);
    
    create( &q, q.size);
    
    printf("Enter the no. of elements: ");
    scanf("%d", &s);
    
    printf("Enter the elements:\n");
    for(int i = 0; i < s; i++){
        scanf("%d", &x);
        enqueue( &q, x);
    }
    printf("\n");
    
    enqueue(&q, 12);
    printf("Enqueue Operation has been performed: \n");
    Display(q);
    
    x = dequeue(&q);
    printf("Dequeue Operation has been performed: %d\n", x);
    Display(q);
    
    return 0;
}

Output:

Program to Insert and Delete (Enqueue / Dequeue) in a Queue using C++ Language:

#include <iostream>
using namespace std;

class Queue {
    private: 
        
        int front;
        int rear;
        int size;
        int * Q;
    
    public: 
        
        Queue() {
            front = rear = -1;
            size = 10;
            Q = new int[size];
        }
        
        Queue(int size) {
            front = rear = -1;
            this -> size = size;
            Q = new int[this -> size];
        }
    
        void enqueue(int x);
        int dequeue();
        void Display();
    
        bool isEmpty();
        bool isFull();
};

void Queue::enqueue(int x) {
    if (Queue::isFull())
        cout << "Queue Full" << endl;
    else {
        rear++;
        Q[rear] = x;
    }
}

int Queue::dequeue() {
    int x = -1;
    if (Queue::isEmpty())
        cout << "Queue is Empty" << endl;
    else {
        x = Q[++front];
    }
    return x;
}

void Queue::Display() {
    if (Queue::isEmpty()) {
        cout << "Queue is Empty" << endl;
        return;
    }
    for (int i = front + 1; i <= rear; i++)
        cout << Q[i] << " ";
    cout << endl;
}

bool Queue::isEmpty() {
    return front == rear;
}

bool Queue::isFull() {
    return rear == size - 1;
}

int main() {
    int x = 0, s,size;

    cout << "Enter the size of the queue: ";
    cin >> size;

    Queue q(size);

    cout << "Enter the no. of elements: ";
    cin >> s;

    cout << "Enter the elements:" << endl;
    for (int i = 0; i < s; i++) {
        cin >> x;
        q.enqueue(x);
    }
    cout << endl;

    q.enqueue(12);
    cout << "Enqueue Operation has been performed: " << endl;
    q.Display();

    x = q.dequeue();
    cout << "Dequeue Operation has been performed: " << x << endl;
    q.Display();

    return 0;
}

Output:

In the next article, I will discuss the Drawbacks of Queues using an array. In this article, I explain How to Implement a Queue using an Array in C Language with Examples. I hope you enjoy this How to Implement Queue using Array in C Language article.