Sunday, July 13, 2008

What is a queue? How to implement queues using C++?

This article explains the queue data structure and demonstrates sample implementation using C++.
  • Queue is a first-in, first-out (FIFO) data structure. i.e. the element added first to the queue will be the one to be removed first.

  • Elements are always added to the back of the queue and removed from the front of the queue.

  • Typical use cases of queues include:- (1) In Inter-Process Communication (IPC) message queues is a common mechanism for communication between processes.

  • Some of the common terminology associated with queues inlcude ADD/ PUSH and DELETE/ POP of elements to the queue.

  • ADD/ PUSH refers to adding an element to the queue.

  • DELETE/ POP refers to removing an element from the queue.

  • Diagram below explains the queue.

Demonstrate the implementation of a simple queue using arrays

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAX_SIZE = 100;

class QueueOverFlowException
{
public:
   QueueOverFlowException()
   {
       cout << "Queue overflow" << endl;
   }
};

class QueueEmptyException
{
public:
   QueueEmptyException()
   {
       cout << "Queue empty" << endl;
   }
};

class ArrayQueue
{  
private:
   int data[MAX_SIZE];
   int front;
   int rear;
public:
   ArrayQueue()
   {
       front = -1;
       rear = -1;
   }      
 
   void Enqueue(int element)
   {
       // Don't allow the queue to grow more
       // than MAX_SIZE - 1
       if ( Size() == MAX_SIZE - 1 )                 
           throw new QueueOverFlowException();

       data[rear] = element;

       // MOD is used so that rear indicator
       // can wrap around
       rear = ++rear % MAX_SIZE;
   }      

   int Dequeue()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       int ret = data[front];

       // MOD is used so that front indicator
       // can wrap around
       front = ++front % MAX_SIZE;

       return ret;   
   }      
 
   int Front()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       return data[front];
   }
 
   int Size()
   {
       return abs(rear - front);
   }
 
   bool isEmpty()
   {
       return ( front == rear ) ? true : false;
   }
};

int main()
{  
   ArrayQueue q;
   try {
       if ( q.isEmpty() )
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);

       // Size of queue
       cout << "Size of queue = " << q.Size() << endl;

       // Front element
       cout << q.Front() << endl;

       // Dequeue elements
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
   }
   catch (...) {
       cout << "Some exception occured" << endl;
   }
}

OUTPUT:-
Queue is empty
Size of queue = 3
100
100
200
300

Demonstrate the implementation of a simple queue using linked lists

#include <iostream>
using namespace std;

class QueueEmptyException
{
public:
   QueueEmptyException()
   {
       cout << "Queue empty" << endl;
   }
};

class Node
{
public:
   int data;
   Node* next;
};

class ListQueue
{  
private:
   Node* front;
   Node* rear;
   int count;

public:
   ListQueue()
   {
       front = NULL;
       rear = NULL;
       count = 0;
   }      
 
   void Enqueue(int element)
   {
       // Create a new node
       Node* tmp = new Node();
       tmp->data = element;
       tmp->next = NULL;

       if ( isEmpty() ) {
           // Add the first element
           front = rear = tmp;
       }
       else {
           // Append to the list
           rear->next = tmp;
           rear = tmp;
       }

       count++;
   }      

   int Dequeue()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       int ret = front->data;
       Node* tmp = front;

       // Move the front pointer to next node
       front = front->next;

       count--;
       delete tmp;
       return ret;   
   }      
 
   int Front()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       return front->data;
   }
 
   int Size()
   {
       return count;
   }

   bool isEmpty()
   {
       return count == 0 ? true : false;
   }
};

int main()
{  
   ListQueue q;
   try {
       if ( q.isEmpty() )
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);

       // Size of queue
       cout << "Size of queue = " << q.Size() << endl;

       // Front element
       cout << q.Front() << endl;

       // Dequeue elements
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
   }
   catch (...) {
       cout << "Some exception occured" << endl;
   }
}

OUTPUT:-
Queue is empty
Size of queue = 3
100
100
200
300

Demonstrate the queue library usage in standard template library (STL)

#include <iostream>
#include <queue>
using namespace std;

int main()
{
   queue<int> q;
   q.push(100);
   q.push(200);
   q.push(300);
   q.push(400);

   cout << "Size of the queue: " << q.size() << endl;

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   if ( q.empty() ) {
   cout << "Queue is empty" << endl;
   }
}

OUTPUT:-
Size of the queue: 4
100
200
300
400
Queue is empty

12 comments :

  1. I took all this stuff a few years ago...thanks for the refresh.

    ReplyDelete
  2. nice tutorial, thanks really needed this

    ReplyDelete
  3. Seems like a bug to me in the first piece of code,
    if you add 80 integers to queue, then delete 50 of them,
    the queue is left with 30 integers.
    Assuming queue size is 100, the user should be able to add 70 more integers into the queue, but the program does not support this.

    ReplyDelete
    Replies
    1. there is need slight modification in code. The size function has not been currently Implemented.
      So here is the modified code:
      #include
      #include
      using namespace std;

      const int MAX_SIZE = 3;

      class QueueOverFlowException
      {
      public:
      QueueOverFlowException()
      {
      cout << "Queue overflow" << endl;
      }
      };

      class QueueEmptyException
      {
      public:
      QueueEmptyException()
      {
      cout << "Queue empty" << endl;
      }
      };

      class ArrayQueue
      {
      private:
      int data[MAX_SIZE];
      int front;
      int rear;
      public:
      ArrayQueue()
      {
      front = 0;
      rear = 0;
      }

      void Enqueue(int element)
      {
      // Don't allow the queue to grow more
      // than MAX_SIZE - 1
      if ( Size() == MAX_SIZE - 1 )
      throw new QueueOverFlowException();
      //cout<<rear<<" "<<front<<endl;
      data[rear] = element;

      // MOD is used so that rear indicator
      // can wrap around
      rear = ++rear % MAX_SIZE;
      }

      int Dequeue()
      {
      if ( isEmpty() )
      throw new QueueEmptyException();

      int ret = data[front];

      // MOD is used so that front indicator
      // can wrap around
      front = ++front % MAX_SIZE;

      return ret;
      }

      int Front()
      {
      if ( isEmpty() )
      throw new QueueEmptyException();

      return data[front];
      }

      int Size()
      {
      if(front<rear) return (rear-front);
      return(rear-front+MAX_SIZE);
      }

      bool isEmpty()
      {
      return ( front == rear ) ? true : false;
      }
      };

      int main()
      {
      ArrayQueue q;
      try {
      if ( q.isEmpty() )
      {
      cout << "Queue is empty" << endl;
      }

      // Enqueue elements
      q.Enqueue(100);
      cout << q.Dequeue() << endl;
      q.Enqueue(200);
      cout << q.Dequeue() << endl;
      cout << q.Dequeue() << endl;
      q.Enqueue(300);
      q.Enqueue(200);
      //cout << q.Size() << endl;

      // Size of queue
      cout << "Size of queue = " << q.Size() << endl;
      q.Enqueue(200);

      // Front element
      //cout << q.Front() << endl;

      // Dequeue elements
      //cout << q.Dequeue() << endl;
      }
      catch (...) {
      cout << "Some exception occured" << endl;
      }
      }

      Delete
  4. I know people freak out when you remind them about C++ standards/conventions (apparently "forum guys" are more intelligent than C++ standard committee members! -sarcasm) but in C++ all upper case names are -conventionally- reserved for macros. You are using a global variable (which I can't see why you are using it! You could EASILY avoid using that global variable) and you named it in upper case letters.

    These are the things that confuses people who are new to C++.

    ReplyDelete
  5. Ok this time I put it simple and clear, may be you publish my comment or change your code! There is absolutely no need for that global constant variable (with all capitol letters!). This variable is used inside ArrayQueue class, it is used only and only inside this class, therefore it should be an attribute of this class.

    C++ coding standards are not just bells and whistles! if you can't follow them I suggest you move to C

    ReplyDelete
  6. Hi coders! I found a bug in the array implementation :-( When rear wraps around (front has not) the Size() value is wrong e g abs(0 - 99) = 99. The size is really 1 not 99 ...

    Cheers!
    Sven

    ReplyDelete
  7. aoa. i want a simple push pop,full,empty implementation through stacks without using classes... plzzzzzz help me guys..
    another favour i required.. i want to learn what is queue.i don't know even its basics

    ReplyDelete
  8. Regarding Array implementation:
    Yeah you cant initialize rear and front as -1 if you do not increment them BEFORE the item insertion in enqueue or dequeue. You can initialize them as -1 if you increment before the item insertion. But it is best to simply initialize them as 0 and 0.

    Say you enqueue the first item. You would be putting the first item into data[-1] , which isn't ok.

    Another thing, when you dequeue, you should increment before you insert the data for good practice. For this code, the rear index doesnt actually point to the rear, it points to the array index after the rear, which can be confusing.

    ReplyDelete
  9. This comment has been removed by a blog administrator.

    ReplyDelete
  10. This comment has been removed by a blog administrator.

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top