Queue implementation in C++

Queue is a FIFO data structure. It is used in all situations where the values returned must be in the same order as values entered.

We have discussed the terminologies, function needed and also implemented a queue in C language earlier.

We can implement a queue by using an array or a linked list for storing values.

Let us look at array implementation of a queue in C++

Data members

We will need the array, front, rear and size of the array. We can use a static array or a dynamic array. 

class Queue
{
   static int size;
   int arr[40];
   int front,rear;   
public:
   Queue();
   void enqueue(int num);
   int dequeue();
   bool is_empty();
   bool is_full();
   void display();
   static int ERR_EMPTY;
}; 
int Queue::ERR_EMPTY=-9999;
int Queue::size=40;

Why are we using two static members in this class. size is the array size. And ERR_EMPTY is a constant which can be returned from dequeue function when the queue is empty.

Constructor

In the constructor we should initialize front and rear indices. Our methods depend on these initial values. 

We will front and rear as 0. So that front==rear indicates queue is empty. And enqueue will add a value to queue then increment rear. And dequeue will remove a value and then increment front.

Methods

Queue ADT has the following operations - 

1. enqueue which adds a value to rear end of queue, 
2. dequeue which removes a value from the front of the queue
3. is_empty which checks if the queue is empty
4. is_full. Well you know this.

Note that all these operations must have a time complexity of O(1).

We should write these as member methods of Queue class. We can also write display which shows all values in the queue.

Enqueue

To add a value to rear of the queue, we just copy the value to arr[rear]. Then we increment rear.

bool Queue::is_full()
{
       return rear==size;
}
void Queue::enqueue(int num)
{
    if(!is_full())
    {
        arr[rear++]=num;
    }
    else
 cout<<"Queue is full";
}

But before adding the value, we have to confirm that queue is not full. Which is done using the statement rear==size.

Dequeue

For popping a value from front of queue, we just return arr[front] and then increment front. But before that we are confirming that queue is not empty. If it is empty we are returning an error code.

int Queue::dequeue()
{
     if(!is_empty())
     {
        return arr[front++];
     }
     else
        return ERR_EMPTY;
}
bool Queue::is_empty()
{
    return rear==front;
}

Here is the complete class and test program. You can download the program from here.

#include<iostream>
using namespace std;
class Queue
{
   static int size;
   int arr[40];
   int front,rear;   
public:
   Queue();
   void enqueue(int num);
   int dequeue();
   bool is_empty();
   bool is_full();
   void display();
   static int ERR_EMPTY;
}; 
int Queue::ERR_EMPTY=-9999;
int Queue::size=40;

Queue::Queue()
{
    front = 0;
    rear = 0;
}

void Queue::enqueue(int num)
{
    if(!is_full())
    {
        arr[rear++]=num;
    }
    else
 cout<<"Queue is full";
}
int Queue::dequeue()
{
     if(!is_empty())
     {
        return arr[front++];
     }
     else
        return ERR_EMPTY;
}
bool Queue::is_empty()
{
    return rear==front;
}

bool Queue::is_full()
{
       return rear==size;
}
void Queue::display()
{
     for(int i=front;i<rear;i++)
         cout<<arr[i]<<"  ";
     cout<<"\n";
}
int main()
{
    Queue q1;
    while(true)
    {
      int n;
      cout<<"Enter an option (1 - enqueue 2 - dequeue 3 - display 4 - quit";
      cin>>n;
      if(n==4)
        break;
      if (n==1)
      {
          int m;
          cout<<"Number to add to queue";
          cin>>m;
   q1.enqueue(m);
      }
      else if(n==2)
      {
           int m = q1.dequeue();
           if(m!=q1.ERR_EMPTY)
              cout<<"Value popped from queue is "<<m;
           else
              cout<<"Queue is empty";
      }
      else if(n==3)
          q1.display();
      else
         cout<<"Wrong option";
     }
}