Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Queues
2.1.
Operations supported by Queues
3.
Inserting elements in a queue
4.
Deleting elements in a queue
5.
Displaying the whole queue
6.
Displaying only the front element of the queue
7.
Code for implementation of queues using array
8.
Frequently Asked Questions
8.1.
What is a Dequeue?
8.2.
Name some applications of queue Data Structure.
8.3.
Name some operations that can be performed on queues
8.4.
What is the time complexity of push and pop functions of queues? 
8.5.
What are Priority Queues?
9.
Conclusion
Last Updated: Mar 27, 2024

Implementation of Queue using Arrays in C++

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

A data structure is a method of managing data in a computer that can be used effectively. For example, we have linked lists, stacks, trees, and queues as some of the data structures that can organize data. Similarly, we can store a list of items having a similar data type using the array data structure.

Queues

A Queue is a linear data structure that follows the FIFO principle i.e., the First-In-First-Out method. The 2 ends of a queue are called Front and Rear. At the start, both Front and Rear are equal to -1 so the queue is empty. Insertion takes place at the Rear end, and the elements are removed or accessed from the Front.

Some applications of queues are :

  1. Scheduling: Job Scheduling, CPU Scheduling.
  2. Buffers: I/O Buffers.

 

Operations supported by Queues

Some operations performed on a queue are:

  1. enqueue(): Inserting a new element in the queue.
  2. dequeue(): Remove an element from the front of the queue.
  3. showfront(): To show the element at the front.
  4. isempty(): To check if queue is empty.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Inserting elements in a queue

Let us take an example of a queue of size= 5.

To insert (enqueue) the element (suppose here 8) in the Queue, we will have to increment the Rear by one and insert 8 at the Rear.

 

When inserting we have to take care of two special cases:

  • When the Queue is empty, the initial value of Front and Rear will be -1, so we will make Front = 0 and increment Rear and insert the element at the Rear. 
  • When the Queue is full, here, we cannot insert any elements in the Queue.

 

Code for Insertion:

void enqueue(int element) {
    // to check if queue is full or not
    if (size == rear) {
        cout << "Queue is full" << endl;
        return;
    }
    // to insert an element at the rear of the queue
    else {
        cout << "Element inserted" << endl;
        queue[rear] = element;
        rear++;
    }
    return;
}

 

If the rear is equal to the size-1 then we will print the queue is full; else we will increment the rear index and store the new element at the rear index.


Deleting elements in a queue

If we have to remove the first element from the Queue, we will increment Front by one.

 

While removing (dequeue) elements from the Queue, we also have two exceptional cases:

  1. The queue is empty - in that case, the Front and Rear will be equal to -1, and as there are no elements in the Queue, we cannot perform the dequeue operation.
  2. The queue has only one element - in that case, the Front will be equal to the Rear, and we will make both equal to -1.

 

Code for Deletion:

void dequeue() {
    // to check if the queue is empty
    if (front == rear) {
        cout << "Queue is empty" << endl;
        return;
    } else {
        for (int i = 0; i < rear - 1; i++) {
            queue[i] = queue[i + 1];
        }
        cout << "Element deleted" << endl;
        // decrement the rear
        rear--;
    }
    return;
}

 

First, we will check if the queue is empty or not. If the queue is empty then we will print that the queue is empty. Else, we will shift all the elements from the start to end to the left by 1. Here we will ignore the element's value at index 0 because we have to remove the element at index 0.

Displaying the whole queue

void printQueue() {
    // to check if queue is empty
    if (front == rear) {
        cout << "Queue is Empty" << endl;
        return;
    }

    //traversing from front to rear to print the elements
    cout << "The queue is: ";
    for (int i = front; i < rear - 1; i++) {
        cout << queue[i] << " <-- ";
    }
    cout << queue[rear - 1] << endl;
    return;
}

 

First, we will check if the queue is empty or not. If the queue is empty then we will print that the queue is empty else we will simply print all the elements of the queue.

Displaying only the front element of the queue

void getFront() {
    // to check if the queue is empty
    if (front == rear) {
        cout << "Queue is Empty" << endl;
        return;
    }

    cout << "Front element is: " << queue[front] << endl;
    return;
}

 

We will first check if the queue is empty or not. If the queue is empty then we will print that the queue is empty else we will just print the front element by using the front variable which is keeping the index of the front variable.

Code for implementation of queues using array

#include <bits/stdc++.h>
using namespace std;

struct Queue {
    int front, rear, size;
    int* queue;
    Queue(int c)
    {
        front = rear = 0;
        size = c;
        queue = new int;
    }

    ~Queue() { delete[] queue; }

    // to insert an element in the queue
    void enqueue(int element)
    {
        if (size == rear) {
            cout<<"Queue is full"<<endl;
            return;
        }

        else {
            cout<<"Element inserted"<<endl;
            queue[rear] = element;
            rear++;
        }
        return;
    }

    // function to delete an element from the queue
    void dequeue()
    {
        // to check if the queue is empty
        if (front == rear) {
            cout<<"Queue is empty"<<endl;
            return;
        }

        // shift all the elements from index 1 till the last element to the left by 1
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }
            cout<<"Element deleted"<<endl;
            // decrement the rear
            rear--;
        }
        return;
    }

    // function to print the elements of the queue
    void printQueue()
    {
        // to check if queue is empty
        if (front == rear) {
            cout<<"Queue is Empty"<<endl;
            return;
        }

        // traverse front to rear and print elements
        cout<<"The queue is: ";
        for (int i = front; i < rear-1; i++) {
            cout<<queue[i]<<" <-- ";
        }
        cout<<queue[rear-1]<<endl;
        return;
    }

    // print the front of the queue
    void getFront()
    {
        // to check if the queue is empty
        if (front == rear) {
            cout<<"The Queue is Empty"<<endl;
            return;
        }

        cout<<"Front element is: "<< queue[front]<<endl;
        return;
    }
};

// Driver code
int main()
{
    // To create a queue of size 5
    Queue queue(5);
    // print the queue elements
    queue.printQueue();
    // inserting elements in the queue
    queue.enqueue(7);
    queue.enqueue(4);
    queue.enqueue(9);
    queue.enqueue(6);
    // printing the queue elements
    queue.printQueue();
    // inserting the element in the queue
    queue.enqueue(1);
    // printing the queue elements
    queue.printQueue();
    // deleting the front element from the queue
    queue.dequeue();
    // printing the queue elements
    queue.printQueue();
    // deleting the front element from the queue
    queue.dequeue();
    // print Queue elements
    queue.printQueue();
    // print the front element of the queue
    queue.getFront();
    return 0;
}

 

Output:

The Queue is Empty
Element inserted
Element inserted
Element inserted
Element inserted
The queue is: 7 <-- 4 <-- 9 <-- 6
Element inserted
The queue is: 7 <-- 4 <-- 9 <-- 6 <-- 1
Element deleted
The queue is: 4 <-- 9 <-- 6 <-- 1
Element deleted
The queue is: 9 <-- 6 <-- 1
Front element is: 9

Read about Application of Queue in Data Structure here.

Frequently Asked Questions

What is a Dequeue?

Dequeue a double-ended queue, or a data structure, where the elements can be deleted or inserted at both ends (FRONT and REAR).

Name some applications of queue Data Structure.

  1. To keep the playlist in media players (to add or remove the songs)
  2. To reverse strings
  3. To verify if delimiters (parenthesis, brackets etc.) are balanced in a computer program
  4. To search the vertices of a graph.

Name some operations that can be performed on queues

  1. enqueue() : Inserting a new element in queue.
  2. dequeue() : Removing an element from the front of the queue.
  3. showfront() : To show the element in the front.
  4. isempty() : To check if queue is empty.

What is the time complexity of push and pop functions of queues? 

The time complexity of enqueue is O(1) and the time complexity of Dequeue is O(n).

What are Priority Queues?

A priority queue is a specialized queue in which the items are associated with a "priority" so that the highest key is always on the Front. So when you get an item from a priority queue, you always get the highest value.

Conclusion

This article demonstrated the implementation of queues using arrays in C++. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

We hope that this blog has helped you increase your knowledge regarding queue data structure, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Previous article
Interleave the first half of the queue with second half
Next article
Generate Binary numbers from 1 to n using queue in Java
Live masterclass