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.
Queue implementation using Simple array
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 Queue.
class Queue
{
private:
int m_front;
int m_rear;
int m_entries;
int m_max_size;
int* m_queue;
public:
Queue (int max);
~Queue ();
int size ();
int enqueue (int entry);
int dequeue ();
bool isEmpty ();
int atFront ();
};
Queue Class Function Implementation
Let’s have a look into all the functions/operations definition of Queue Class.
Constructor/Destructor implementation
Queue::Queue (int max): m_front(0),
m_rear (0),
m_entries (0),
m_max_size (max)
{
m_queue = new int[max];
if (!m_queue)
{
cout << "Queue initialization failed" << endl;
return;
}
}
Queue::~Queue ()
{
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.
int Queue::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.
int Queue::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.
bool Queue::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.
int Queue::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.
int Queue::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 Queue class definition and functions defined above.
int main ()
{
Queue 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
