Stack Implementation in C++ Using Two Queues

In this article, we will learn stack implementation using two queues. Stacks are very crucial data structures and are used everywhere in our day-to-day life. We will start by understanding the concept of stacks and queues and then move towards the implementation in the end.

Also read: Stack Class Implementation In C++ [Easy]

What Is A Stack?

Okay let’s come straight to the point, what does a stack represent? As the name suggests, a stack is simply a stack. A stack follows the LIFO(Last In First Out) property i.e. the object that enters the stack, in the end, is the first to come out.

What Is A Queue?

A queue represents a FIFO(First In First Out) data structure, which means that the first element to enter the queue is the first one to exit it. You have many encounters with queues in your day-to-day life. Be it the process manager of your computer or movie ticket counter, yes I know that there are not many who buy tickets from the ticket counter. But queues have always been an indispensable part of our lives.

Stack Using Two Queues

Let’s quickly jump to developing a stack using two queues. Below are the steps that we will follow while writing the code.

At a time only one queue will store the data and the other will remain empty
To implement the push function, we follow the steps given below
- Add the new element in the empty queue
- Move all the elements of the other queue into this queue
Just remove the element at the front of the queue having the data.
We can obtain the top most element of the stack by using the front() function on the queue having the data.

The following example will help you grab the concept better.

1. Let’s start with an empty stack

2. Push “Vaibhav” into the stack

Stack : |Vaibhav| <-- Top
Queue1 : |Vaibhav| --> Head
Queue2 : |Empty|

3. Push “Hardik” into the stack

Stack : |Vaibhav| <-- |Hardik| <-- Top
Queue1 : |Vaibhav| --> Head
Queue2 : |Hardik| --> Head

Now we move the elements of Queue1 to Queue2

Queue1 : |Empty|
Queue2 : |Vaibhav| --> |Hardik| --> Head

4. Push “Malik” into the stack

Stack : |Vaibhav| <-- |Hardik| <-- |Malik| <-- Top
Queue1 : |Malik| --> Head
Queue2 : |Vaibhav| --> |Hardik| --> Head

Now we move the elements of Queue2 to Queue1
Queue1 : |Vaibhav| --> |Hardik| --> |Malik| --> Head
Queue2 : |Empty|

5. Popping an element out of the stack

Stack : |Vaibhav| <-- |Hardik| <-- Top
Queue1 : |Vaibhav| --> |Hardik| --> Head
Queue2 : |Empty|

This is very simple, we just need to remove the front element of the Queue having the elements

Stack Implementation Using Two Queues In C++

#include <iostream>
#include <queue>

using namespace std;

template <typename T>
class Stack
{
private:

    // all the data members are private to avoid foreign access
    queue <T> q1;
    queue <T> q2;
    int stack_size;
    bool active;

public:
    // constructor
    Stack(): stack_size(0), active(true) {}

    // push function
    void push(T element)
    {
	// increment the size
        stack_size ++;
        if(active)
        {
	    // push logic
            q1.push(element);

            while(!q2.empty())
            {
                q1.push(q2.front());
                q2.pop();
            }
            active = false;
        }
        else
        {
            q2.push(element);
            
            while(!q1.empty())
            {
                q2.push(q1.front());
                q1.pop();
            }
            active = true;
        }    
    }

    bool is_empty()
    {
        return stack_size == 0;
    }

    void pop()
    {
	// before call the pop function
	// check if the stack is empty or not
        if(!is_empty())
        {
            stack_size --;
            if(active)
                q2.pop();
            else
                q1.pop();
        }
        else
            cout << "Already Empty !!!" << endl;
    }

    T top()
    {
	// returning the topmost element from
	// the queue currently storing the data
        if(active)
            return q2.front();
        
        return q1.front();
    }

    int get_size()
    {
        return stack_size;
    }
};

template <typename T>
void print_stack(Stack <T> s)
{
    cout << "|*****************|" << endl;
    cout << "The stack is :" << endl;

    while(!s.is_empty())
    {
        cout << s.top() << endl;
        s.pop();
    }

    cout << "|*****************|" << endl;
    cout << endl ;
}

int main()
{
    Stack <string> s;

    cout << "Enter the elements and press |done| to stop" << endl;
    while(true)
    {
        string str;
        cin >> str;

	if(str == "done")
	    break;

        s.push(str);
    }

    print_stack(s);

    cout << "Let's remove the last two elements from the stack" << endl;
    s.pop();
    print_stack(s);
    s.pop();
    print_stack(s);

    return 0;
}

Stack Using 2 Queues Code — Stack Using Two Queues Code

Output

Conclusion

Let’s recall what we learned today, we started by looking at what are stacks and queues. Then we moved to the structure of the stack class using two queues. In the end, we wrote a C++ program to demonstrate the working of our template stack class. That’s all for now, thanks for reading.

References

To read more about stacks and queues, you can refer to the following websites.

Queue Class Implementation In C++

Stack Class Implementation In C++ [Easy]

https://en.cppreference.com/w/cpp/container/stack