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, Stack basics and Stack Implementation.
Queue implementation using Stack
Here we are going to talk about a simple implementation of Queue data structures in C++ using Two Stacks.
In this case, one Stack will act as enqueue stack and other will be act as dequeue stack.
- If we have to add any element into queue (enqueue) then all elements from Dequeue Stack should first move into Enqueue Stack and then new element will be added into Enqueue Stack.
- Similarly, If we have to dequeue element from queue then all elements from Enqueue Stack should first move into Dequeue Stack and then top element will be POPPED from Dequeue Stack.
Few of the functions used below are explained in Stack Implementation. Refer those before going ahead.
Let’s have a look on basic C++ class definition for Queue using Stacks.
class QueueUsingStack
{
private:
Stack* m_enqueue_stack;
Stack* m_dequeue_stack;
public:
QueueUsingStack (int max);
~QueueUsingStack ();
int size ();
int maxSize ();
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
In constructor, we are going to allocate both Stacks with max size values.
QueueUsingStack::QueueUsingStack (int max)
{
m_enqueue_stack = new Stack(max);
m_dequeue_stack = new Stack(max);
}
QueueUsingStack::~QueueUsingStack ()
{
delete m_dequeue_stack;
delete m_enqueue_stack;
}
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.
Algorithm
- For all items in Dequeue Stack.
- POP item from Dequeue Stack.
- PUSH item into Enqueue Stack.
- PUSH new item into Enqueue Stack.
Let’s look into the sample code.
int QueueUsingStack::enqueue (int entry)
{
while (!m_dequeue_stack -> isEmpty ())
{
int data = m_dequeue_stack -> pop ();
m_enqueue_stack -> push (data);
}
m_enqueue_stack -> push (entry);
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.
Algorithm
- For all items in Enqueue Stack.
- POP item from Enqueue Stack.
- PUSH item into Dequeue Stack.
- POP top element from Dequeue Stack.
Let’s look into the sample code.
int QueueUsingStack::dequeue ()
{
while (!m_enqueue_stack -> isEmpty ())
{
int data = m_enqueue_stack -> pop ();
m_dequeue_stack -> push (data);
}
if (m_dequeue_stack -> isEmpty ())
{
return -1;
}
return m_dequeue_stack -> pop ();
}
IsEmpty operation implementation
This operation will check whether Queue is empty or not. In this case, If both stack are empty then Queue is empty.
Let’s look into the sample code.
bool QueueUsingStack::isEmpty ()
{
return m_enqueue_stack -> isEmpty () || m_dequeue_stack -> isEmpty ();
}
Size/Entries operation implementation
This operation will return the number of entries present in Queue. At any point of time, one of the Stacks will always remain empty. Hence, whichever Stack is filled return that stacks elements count.
Let’s look into the sample code.
int QueueUsingStack::size ()
{
if (m_enqueue_stack -> entries ())
{
return m_enqueue_stack -> entries ();
}
else if (m_dequeue_stack -> entries ())
{
return m_dequeue_stack -> entries ();
}
return 0;
}
AtFront operation implementation
This operation will return the front element from the Queue. This operation will not remove the front element from the Queue.
Algorithm
- For all items in Enqueue Stack.
- POP item from Enqueue Stack.
- PUSH item into Dequeue Stack.
- Return top element from Dequeue Stack.
Let’s look into the sample code.
int QueueUsingStack::atFront ()
{
while (!m_enqueue_stack -> isEmpty ())
{
int data = m_enqueue_stack -> pop ();
m_dequeue_stack -> push (data);
}
if (m_dequeue_stack -> isEmpty ())
{
return -1;
}
return m_dequeue_stack -> atTop ();
}
Let’s look into the sample main function which utilizes Stack class definition and functions defined above.
int main ()
{
QueueUsingStack q(10);
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 << "Front element: " << q.atFront () << 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: -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: 8 Total entries: 7
Dequeuing value: 2 Remaining entries: 6
Enqueuing value: 9 Total entries: 7
Enqueuing value: 10 Total entries: 8
Enqueuing value: 11 Total entries: 9
Enqueuing value: 12 Total entries: 10
Is Queue Empty: 1
Front element: 3
Dequeuing value: 3 Remaining entries: 9
Dequeuing value: 4 Remaining entries: 8
Dequeuing value: 5 Remaining entries: 7
Dequeuing value: 6 Remaining entries: 6
Dequeuing value: 7 Remaining entries: 5
Dequeuing value: 8 Remaining entries: 4
Dequeuing value: 9 Remaining entries: 3
Is Queue Empty: 1
