by Queue is a data structure used for storing collection of data where order in which data is arriving is important. In Queue, insertion and deletion both happened from the different end.
Data insertion are done at one end which is known as “rear end” while data deletion are done at other end known as “front end“. The data which is arrived first will be deleted first in Queue. This data ordering is called as First in First out or FIFO.
Before going ahead have a look into Queue basics.
Implementation using Simple array
Our aim here is to provide a generic implementation of Stacks which can be used for all primitive data types. Here we are going to talk about a simple implementation of Queue data structures in C++ using arrays along with some basic Queue operations implementation such as Enqueue/Dequeue etc.
Let’s have a look on basic C++ class definition for Generic Queue.
template <typename T>
class GenericQueue
{
private:
int m_front;
int m_rear;
int m_entries;
int m_max_size;
T* m_queue;
public:
GenericQueue (int max);
~GenericQueue ();
int size ();
int enqueue (int entry);
T dequeue ();
bool isEmpty ();
T atFront ();
};
Class Function Implementation
Let’s have a look into all the functions/operations definition of Queue Class.
Constructor/Destructor implementation
template <typename T>
GenericQueue<T>::GenericQueue (int max): m_front(0),
m_rear (0),
m_entries (0),
m_max_size (max)
{
m_queue = new T[max];
if (!m_queue)
{
cout << "Queue initialization failed" << endl;
return;
}
}
template <typename T>
GenericQueue<T>::~GenericQueue ()
{
if (!m_queue)
{
cout << "Queue is not initializaed" << endl;
return;
}
delete [] m_queue;
}
Enqueue operation implementation
This operation will add an entry into the Queue at the rear end of the Queue. In case Queue is full then error is returned. This condition is called Queue Overflow.
Let’s look into the sample code.
template <typename T>
int GenericQueue<T>::enqueue (int entry)
{
if (!m_queue)
{
cout << "Queue is not initializaed" << endl;
return -1;
}
if (m_entries == m_max_size)
{
cout << "Queue is full... can't take more entries!!" << endl;
return -1;
}
m_queue[m_front] = entry;
m_front = (m_front + 1) % m_max_size;
m_entries++;
return entry;
}
Dequeue operation implementation
This operation will remove the front entry from the Queue. In case Queue is empty then error is returned. This condition is called Queue Underflow.
Let’s look into the sample code.
template <typename T>
T GenericQueue<T>::dequeue ()
{
if (!m_queue)
{
cout << "Queue is not initializaed" << endl;
return -1;
}
if (m_entries == 0)
{
cout << "Queue is empty !!!" << endl;
return -1;
}
int temp = m_queue[m_rear];
--m_entries;
m_rear = (m_rear + 1) % m_max_size;
return temp;
}
IsEmpty operation implementation
This operation will check whether Queue is empty or not.
Let’s look into the sample code.
template <typename T>
bool GenericQueue<T>::isEmpty ()
{
return !m_entries;
}
Size/Entries operation implementation
This operation will return the number of entries present in Queue.
Let’s look into the sample code.
template <typename T>
int GenericQueue<T>::size ()
{
return m_entries;
}
AtFront operation implementation
This operation will return the front element from the Queue. This operation will not remove the front element from the Queue.
Let’s look into the sample code.
template <typename T>
T GenericQueue<T>::atFront ()
{
if (!m_queue)
{
cout << "Queue is not initializaed" << endl;
return -1;
}
if (m_entries == 0)
{
cout << "Queue is empty !!!" << endl;
return -1;
}
return m_queue[m_rear];
}
Let’s look into the sample main function which utilizes Generic Queue class definition and functions defined above.
int main ()
{
GenericQueue<int> q(6);
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (1) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (2) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (3) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (4) << " Total entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (5) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (6) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (7) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (8) << " Total entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (9) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (10) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (11) << " Total entries: " << q.size () << endl;
cout << "Enqueuing value: " << q.enqueue (12) << " Total entries: " << q.size () << endl;
cout << "Is Queue Empty: " << q.isEmpty () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Dequeuing value: " << q.dequeue () << " Remaining entries: " << q.size () << endl;
cout << "Is Queue Empty: " << q.isEmpty () << endl;
}
Let’s analyze the output of this main function.
Dequeuing value: Queue is empty !!!
-1 Remaining entries: 0
Enqueuing value: 1 Total entries: 1
Enqueuing value: 2 Total entries: 2
Enqueuing value: 3 Total entries: 3
Enqueuing value: 4 Total entries: 4
Dequeuing value: 1 Remaining entries: 3
Enqueuing value: 5 Total entries: 4
Enqueuing value: 6 Total entries: 5
Enqueuing value: 7 Total entries: 6
Enqueuing value: Queue is full... can't take more entries!!
-1 Total entries: 6
Dequeuing value: 2 Remaining entries: 5
Enqueuing value: 9 Total entries: 6
Enqueuing value: Queue is full... can't take more entries!!
-1 Total entries: 6
Enqueuing value: Queue is full... can't take more entries!!
-1 Total entries: 6
Enqueuing value: Queue is full... can't take more entries!!
-1 Total entries: 6
Is Queue Empty: 0
Dequeuing value: 3 Remaining entries: 5
Dequeuing value: 4 Remaining entries: 4
Dequeuing value: 5 Remaining entries: 3
Dequeuing value: 6 Remaining entries: 2
Dequeuing value: 7 Remaining entries: 1
Dequeuing value: 9 Remaining entries: 0
Dequeuing value: Queue is empty !!!
-1 Remaining entries: 0
Is Queue Empty: 1
