Queue in C++ Programming

- February 05, 2018
In programming, queue is a linear data structure in which new items are inserted from one end, whereas existing items are removed from other end. The end at which the items are inserted is called Tail or Back or Rear of the queue. The end from where items are removed is called Head or Front of the queue.
Example of queue in programming

The item that is added at first into the queue is removed first. Similarly, the item that is added at the end is removed at the end. For this reason, a queue is referred to as Ftrst In First-Out (FIFO) data structure The insert and remove operations are also known as enqueue and dequeue respectively. 
Example of programming queue with 9 items

The above image shows a queue with 9 items. The item 1 is the frst item, while 9 is the last item. A new Item can be added after 9. Similarly, the Items can be removed starting at the front of the queue, For example, the first item to be removed will be 1 and  to remove the item 9, all items in front of 9, such as 1, 2, 3, 4, 5, 6, 7 and 8 must be removed first. 

Applications of Queues in Computer

Queues have many applications in computer systems. Most computers have only a single processor, so the job of only one user can be performed at a time. The jobs of other users are placed in a queue and are performed one after the other. 

For example, if you want to print documents on the printer, the operating system (or a special print spooler) queues the documents by placing them in a special area called a print buffer or print queue. The document sent first is printed first and so on. Similarly, network operating system uses queue to process printing request. The documents are sent to the printer in network environment. (which may have single printer). The printer prints the document in the order in which they are received. 

In electronic data communication systems, queues are also used to receive and send information packets. The information packets wait in queues in computer network. 

Implementation of Queue

A queue can be implemented in computer programming languages using different ways. Normally, linear array and linked list are used to implement queues. The simplest and easiest way to implement a queue is by using a linear array. 

Suppose an array QU represents a queue and the variables F and B represent the front and back of the queue respectively. If the array has capacity of storing ‘N’ elements, then whenever a new data item is added into the array, the value of B is increased by 1. If the value of B is greater than or equal to N, then queue is overflowed. Similarly, when a data item is removed from the queue, the value of F is increased by 1. If the value of F and B are equal then queue has only one item. If the value of F is -1, then queue is empty. Following table illustrates these operations;
Queue Status Operation
Queue operation 1 only one value

Take a queue of capacity of 5 elements. Initially there is only one item such as "X" in the queue, therefore F and B both are at 0 position.
Queue operation 2 two values in queue

Add another item in the queue such as "Y". The value of B is increased by 1, i.e it becomes 1.
Queue operation 3

Queue operation 4

Add another item in the queue such as "Z". The value of B is increased by 1, i.e it becomes 2.
Queue operation 5

Delete the one item from the queue which is "X". The value of F is increased by 1, i.e it becomes 1.
Queue operation 6

Delete another item from the front of queue which is "Y". The value of F is increased by 1, i.e it becomes 2. Both the values of F and B are equal. It means that only one item exists in the queue.
Queue operation 7

Delete another item from the queue which is "X". The value of F is increased by 1, i.e it becomes 3. At this position, value of F is greater than B, so initialize value of F and B to -1.

C++ Queue Example Programs

Example program 1: The following source code insert and remove items from the queue. 

#include<iostream>
using namespace std;
class queue
{
   private:
   int B, F;
   int QU[10];
   public:
   // constructor that initializes variables B & F
   queue (void) {B = -1; F = -1;}
   void insert (int);
   void remove (void);
   void display (void);
};
void main (void)
{
   queue obj;
   int n, opt, loop = 1;
   while (loop)
   {
   cout<<"1- Insert value into queue"<<endl;
   cout<<"2- Remove value into queue"<<endl;
   cout<<"3- Display value into queue"<<endl;
   cout<<"4- Exist"<<endl;
   cout<<"Enter your option [1-4]?"<<endl;
   cin>>opt;
   switch (opt)
  {
    case 1:
            cout<<"Enter value to insert?"<<endl;
          cin>>n;
          obj .insert (n);
          break;
    case 2:
          obj .remove ();
          break;
    case 3:
          cout<<"Values in queue\n";
          obj .display ();
          break;
    case 4:
          loop = 0; break;
    default:
          cout<<"Invalid option";
    }
  }
}
// member function to insert value into queues
void queue :: insert (int x)
{
   if (B >= 9)
   {
    cout<<"Queue overflow";
    getch();
    return;
 }
else
{
   B = B + 1;
   QU [B] = x;
 }
if (F == -1)
   F = 0;
 }
// member function to remove value from queue
{
   if (F == -1)
   {
    cout<<"Queue is empty";
    getch();
    return;
 }
cout<<"value "<<QU[F]<<" is removed"<<endl;
return 0;
QU[F] = NULL;
F = F + 1;
if (F>B)
   F = B = -1;
}
// member function to display values of stack
{
   if (F == -1)
   {
     cout<<"Queue is empty";
      return 0;
    return;
   }
   for (int i = F; i <= B; i++)
      cout<<QU[i]<<endl;
       return 0;
}

What is Deques

The term deque stands for double-ended queue. It is a linear data structure in which items can be added or removed at either end (or side). It means that items can be added or removed at both ends of the deque. However, an item cannot be added or deleted in the middle of the deque. A deque-with values is shown in the following image. 
Example of C++ deque with values

Type of Deques

There are two types of deques, these are following:
  1. Input-Restricted Deque: This type of deque allows insertions only at one end but allows deletions at both ends. 
  2. Output-Restricted Deque: This type of deque allows deletions only at one end but allows insertions at both ends. 

Implementation of Deque

The deque can be implemented in computer languages in several ways. Usually, It is implemented in similar way as circular queue is implemented. Normally, deque is implemented by using linear array with two pointer variables pointing to its two ends. 

Suppose an array DQ represents a deque and the variable "F" and "B" represent the front and back of the deque respectively. The following points must be noted about the deque: 

  • When an item is added at the front of DQ, then F, is decreased by 1. 
  • When an item is removed at the front, then value of F is increased by 1
  • When an item is added at the back, then B is increased by 1
  • When an item is removed from back, then B is decreased by 1. 
  • If the values of F and B are equal, it indicates that the deque has only one item.

After deleting the last item in the deque, the values of both F and B are set to -1 (or NULL value). This indicates that the deque is empty. An image of deque is shown below having some items stored In it.
A deque having some items stored in it

The values of F and B for the above deque are 2 and 4 respectively, 

If two values 19 and 24 are removed from back of deque, then B decreases by 2. 
So the value of B becomes 2. The value of F and B are equal. It indicates that dequc has only one item which is 26. 
Deque has only one item
Example program 2: This program inserts and removes data items to and from the queue.
// program to insert and delete items in a circular duque
#include<iostream>
using namespace std;
class duque
{
   private:
   int F, B, DQ[5];
   Public:
   deque() // constructor to initialize F & B
   { F = -1; B = -1; }
   void insert_front (int);
   void insert_back (int);
   void del_front (void);
   void del_back (void);
   void print_deque (void);
 };
void main (void)
 {
   duque obj;
   int opt, val;
   while (opt! = 5)
 {
   cout<<"1 : Insert Item from Front\n";
   cout<<"2 : Insert Item from Front\n";
   cout<<"3 : Delete Item from Front\n";
   cout<<"4 : Delete Item from Front\n";
   cout<<"5 : Exist\n";
   cout<<"Enter your choice : [1-5]?";
   cin>>opt;
   switch (opt)
 {
   case 1:
      cout<<"\n Enter value to insert?";
      cin>>val;
      obj .insert_front (val);
      obj .print_deque ();
      break;
   case 2:
      cout<<"\n Enter value to insert?";
      cin>>val;
      obj .insert_front (val);
      obj .print_deque ();
      break;
   case 3:
      obj .del_front ();
      obj .del_deque ();
      break;
   case 4:
      obj .del_back ();
      }
   }
 }
// member function to insert item from front side of the deque
   void deque :: insert_front (int n)
 {
   if (F == 0 && B == 4)
   {
      cout<<"Deque is full";
      return;
      
   }
   if (F == -1 && B == -1)
   {
      B = F = 0;
      DQ [F] = n;
   }
   else if (F > 0)
   {
      F--;
      DQ[F] = n;
   }
   else
   {
      cout<<"No space from front side";
      return 0;
   }
 }

// member function to insert item from back side of the deque
   void deque :: insert_bqck (int n)
 {
   if (F == 0 && B == 4)
   {
      cout<<"Deque is full";
      return;
      
   }
   if (F == -1 && B == -1)
   {
      B = F = 0;
      DQ [B] = n;
   }
   else if (B > 0)
   {
      B!++;
      DQ[B] = n;
   }
   else
   {
      cout<<"No space from back side";
      return 0;
   }
 }

// member function to delete item from front side of the deque
   void deque :: del_front (int n)
 {
   if (F == -1 && B == -1)
   {
      cout<<"Deque is empty";
      return;
      
   }
   else
      DQ[F] = NULL;
      if (F == B) F = B = -1;
      else if (F == 4) F == -1;
      else
        F++;
   }
 //member function to delete item from back side of the deque
   void deque :: del_back (int n)
 {
   if (F == -1 && B == -1)
   {
      cout<<"Deque is empty";
      return;
      
   }
else
      DQ[B] = NULL;
      if (B == F) F = B = -1;
      else if (F == 4) F == -1;
      else
        B--;
   }

// member function to print data from deque
void deque :: print_deque ()
  {
    cout<<"\n Deque after operation \n";
    if (F == -1)
   {
      cout<<"Queue is empty";
      return;
      return 0;
   }
   for (int i = F; i <= B; i++)
      cout<<"DQ[i]<<"\t";
      return 0;
 }