C++ Queue

This post was written and published to explain how queues are implemented in the C++ programming language. However, I defined the "queue" data structure in a separate post; thus, this post only covers the queue data structure's implementation in C++. So, without further ado, let us begin with a brief description.

A queue is a FIFO (first-in, first-out) structure that can be physically implemented as an array or as a linked list. In any queue implementation, insertions occur at the "back" end and deletions occur at the "front" end.

C++: Array Queue

Before processing, the number of elements in a queue that is created as an array is declared. The beginning of the array becomes its "front" end, and the end of the array becomes its "rear" end. The terms "front" and "rear" are used in describing a linear list only when it is implemented as a queue.

"front" stores the index of the queue's first element, and "rear" stores the index of the queue's last element. The number of elements in a queue at any given time can be calculated using the "front" and "rear" values. For example, if "front = 0," then the number of elements is 0, otherwise the number of elements is equal to "front - rear + 1."

Example of insertion into an array-queue in C++

#include <iostream>
using namespace std;

int insert_in_queue(int[], int);
void display(int[], int, int);

const int SIZE = 50;

int queue[SIZE];
int front = -1;
int rear = -1;

int main()
{
   int item, check;
   char ch = 'y';

   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter item for insertion: ";
      cin >> item;
      check = insert_in_queue(queue, item);
      if (check == -1)
      {
         cout << "\nAborting because of overflow\n";
         return 0;
      }
      cout << "Item successfully inserted!\n";
      cout << "\nThe queue is now (from front...to...rear):\n";
      display(queue, front, rear);
      cout << "\nDo you want to add more? (y/n): ";
      cin >> ch;
   }
   return 0;
}

int insert_in_queue(int queue[], int elem)
{
   if (rear == SIZE - 1)
   {
      return -1;
   }
   else if (rear == -1)
   {
      front = rear = 0;
      queue[rear] = elem;
   }
   else
   {
      rear++;
      queue[rear] = elem;
   }
   return 0;
}

void display(int queue[], int front, int rear)
{
   if (front == -1)
   {
      return;
   }
   for (int i = front; i < rear; i++)
   {
      cout << queue[i] << " <- ";
   }
   cout << queue[rear] << "\n";
}

The following snapshot shows the initial output produced by the above example program, illustrating the insertion into the array queue.

Now, as an item, type a number, say 10, and press the ENTER key. This is the result you will see.

To insert more items, type "y" or "Y" and hit the ENTER key, then type an item, say 20, and hit the ENTER key again. The following snapshot shows the sample run with some inputs.

An example of deletion from an array queue in C++

#include <iostream>
using namespace std;

int delete_from_queue(int[]);
int insert_in_queue(int[], int);
void display(int[], int, int);

const int SIZE = 50;
int queue[SIZE];
int front = -1;
int rear = -1;

int main()
{
   int item, check;
   char ch = 'y';
   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter item for insertion: ";
      cin >> item;
      check = insert_in_queue(queue, item);
      if (check == -1)
      {
         cout << "\nAborting because of overflow\n";
         return 0;
      }
      cout << "Item successfully inserted!\n";
      cout << "\nThe queue is now (from front...to...rear):\n";
      display(queue, front, rear);
      cout << "\nDo you want to add more? (y/n): ";
      cin >> ch;
   }
   cout << "Now the deletion of elements starts.\n";
   ch = 'y';
   while (ch == 'y' || ch == 'Y')
   {
      check = delete_from_queue(queue);
      if (check == -1)
      {
         cout << "\nAborting because of underflow\n";
         return 0;
      }
      else
      {
         cout << "\nThe element deleted is: " << check << "\n";
         cout << "The queue is now (from front...to...rear):\n";
         display(queue, front, rear);
      }
      cout << "\nDo you want to delete more? (y/n): ";
      cin >> ch;
   }
   return 0;
}

int insert_in_queue(int queue[], int elem)
{
   if (rear == SIZE - 1)
      return -1;
   else if (rear == -1)
   {
      front = rear = 0;
      queue[rear] = elem;
   }
   else
   {
      rear++;
      queue[rear] = elem;
   }
   return 0;
}
int delete_from_queue(int queue[])
{
   int retn;
   if (front == -1)
      return -1;
   else
   {
      retn = queue[front];
      if (front == rear)
         front = rear = -1;
      else
         front++;
   }
   return retn;
}
void display(int queue[], int front, int rear)
{
   if (front == -1)
      return;
   for (int i = front; i < rear; i++)
      cout << queue[i] << " <- ";
   cout << queue[rear] << "\n";
}

The following box depicts a sample run of the preceding program, demonstrating deletion in an array queue. In this test, I inserted three items, "1," "2," and "3," then deleted them one by one until the "underflow" occurred.

Enter item for insertion: 1
Item successfully inserted!

The queue is now (from front...to...rear):
1

Do you want to add more? (y/n): y
Enter item for insertion: 2
Item successfully inserted!

The queue is now (from front...to...rear):
1 <- 2

Do you want to add more? (y/n): y
Enter item for insertion: 3
Item successfully inserted!

The queue is now (from front...to...rear):
1 <- 2 <- 3

Do you want to add more? (y/n): n
Now the deletion of elements starts.

The element deleted is: 1
The queue is now (from front...to...rear):
2 <- 3

Do you want to delete more? (y/n): y

The element deleted is: 2
The queue is now (from front...to...rear):
3

Do you want to delete more? (y/n): y

The element deleted is: 3
The queue is now (from front...to...rear):

Do you want to delete more? (y/n): y

Aborting because of underflow

Process returned 0 (0x0)   execution time : 14.977 s

C++: Linked Queue

A linked queue is one with links between its elements. Two pointers are kept to store the "front" and "rear" positions.

Example of insertion in a linked queue in C++

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *front, *newptr, *save, *ptr, *rear;

node *create_new_node(int);
void insert(node *);
void display(node *);

int main()
{
   front = rear = NULL;
   int inf;
   int count = 0;
   char ch = 'y';

   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      newptr = create_new_node(inf);
      if (newptr == NULL)
      {
         cout << "\nSorry..!!..Can't create a new node...!!..Aborting...!! \n";
         return 0;
      }
      insert(newptr);
      cout << "\nNow the queue (from front...to...rear) is:\n";
      display(front);
      cout << "\nDo you want to enter more? (y/n): ";
      cin >> ch;
   }
   return 0;
}

node *create_new_node(int x)
{
   ptr = new node;
   ptr->info = x;
   ptr->next = NULL;
   return ptr;
}
void insert(node *n)
{
   if (front == NULL)
      front = rear = n;
   else
   {
      rear->next = n;
      rear = n;
   }
}
void display(node *n)
{
   while (n != NULL)
   {
      cout << n->info << " -> ";
      n = n->next;
   }
   cout << "!!\n";
}

The sample run with user inputs "11," "22," and "45" as three insertion items is shown in the box below:

Enter information for the new node: 11

Now the queue (from front...to...rear) is:
11 -> !!

Do you want to enter more? (y/n): y
Enter information for the new node: 22

Now the queue (from front...to...rear) is:
11 -> 22 -> !!

Do you want to enter more? (y/n): y
Enter information for the new node: 45

Now the queue (from front...to...rear) is:
11 -> 22 -> 45 -> !!

Do you want to enter more? (y/n): n

Process returned 0 (0x0)   execution time : 9.293 s

An example of deletion from a linked queue in C++

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *front, *newptr, *save, *ptr, *rear;

node *create_new_node(int);
void insert(node *);
void delete_node_queue();
void display(node *);

int main()
{
   front = rear = NULL;
   int inf;
   int count = 0;
   char ch = 'y';
   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      newptr = create_new_node(inf);
      if (newptr == NULL)
      {
         cout << "\nSorry..!!..Can't create a new node...!!..Aborting...!! \n";
         return 0;
      }
      insert(newptr);
      cout << "\nNow the queue (from front...to...rear) is:\n";
      display(front);
      cout << "\nDo you want to enter more? (y/n): ";
      cin >> ch;
   }
   do
   {
      cout << "The linked queue now is (front...to...rear):\n";
      display(front);
      if (count == 0)
      {
         cout << "\nDo you want to delete? (y/n): ";
         count++;
      }
      else
         cout << "\nDo you want to delete more? (y/n): ";
      cin >> ch;
      if (ch == 'y' || ch == 'Y')
         delete_node_queue();
      cout << "\n";
   } while (ch == 'y' || ch == 'Y');
   return 0;
}

node *create_new_node(int x)
{
   ptr = new node;
   ptr->info = x;
   ptr->next = NULL;
   return ptr;
}

void insert(node *n)
{
   if (front == NULL)
      front = rear = n;
   else
   {
      rear->next = n;
      rear = n;
   }
}
void delete_node_queue()
{
   if (front == NULL)
   {
      cout << "\nAborting because of overflow\n";
      exit(0);
   }
   else
   {
      ptr = front;
      front = front->next;
      delete ptr;
   }
}
void display(node *n)
{
   while (n != NULL)
   {
      cout << n->info << " -> ";
      n = n->next;
   }
   cout << "!!\n";
}

The sample run of this example program is shown in the following box:

Enter information for the new node: 112

Now the queue (from front...to...rear) is:
112 -> !!

Do you want to enter more? (y/n): y
Enter information for the new node: 4

Now the queue (from front...to...rear) is:
112 -> 4 -> !!

Do you want to enter more? (y/n): y
Enter information for the new node: 65

Now the queue (from front...to...rear) is:
112 -> 4 -> 65 -> !!

Do you want to enter more? (y/n): y
Enter information for the new node: 657

Now the queue (from front...to...rear) is:
112 -> 4 -> 65 -> 657 -> !!

Do you want to enter more? (y/n): n
The linked queue now is (front...to...rear):
112 -> 4 -> 65 -> 657 -> !!

Do you want to delete? (y/n): y

The linked queue now is (front...to...rear):
4 -> 65 -> 657 -> !!

Do you want to delete more? (y/n): y

The linked queue now is (front...to...rear):
65 -> 657 -> !!

Do you want to delete more? (y/n): y

The linked queue now is (front...to...rear):
657 -> !!

Do you want to delete more? (y/n): y

The linked queue now is (front...to...rear):
!!

Do you want to delete more? (y/n): y

Aborting because of overflow

Process returned 0 (0x0)   execution time : 15.578 s

C++ Quiz

« Previous Tutorial Next Tutorial »