Queue Using Two Stacks Problem In C++

Today, we’ll learn to solve the queue using two problem stacks in C++. It is a classical implementation problem and has been asked about during many technical interviews. This problem is a must if you’re brushing up on your DSA concepts. Let’s quickly take a look at the basic differences between stacks and queues. Later we’ll move towards the implementation.

Also read: Stack Using Two Queues In C++

Difference Between Stacks And Queues

There can be many differences between a stack and a queue but let’s look at the most important difference between these data structures.

Stacks

LIFO(Last In First Out): It implies that the last element to enter the stack is the first to leave.

Unique Stack Functions

• pop(): Pops the element at the top of the stack.
• top(): Returns the topmost element of the stack.

Queues

FIFO(First In First Out): It implies that the first element to enter the queue is the first to leave.

Unique Queue Functions

• pop(): Pops the element at the front of the queue.
• front(): Returns the element at the front of the queue.

Problem Statement of Queue Using Two Stacks

Implement a queue using two stacks. Implement basic queue operations like push(), pop(), front(), etc.

Usually, we implement queue classes using vectors. But let’s implement a custom queue class using stacks.

Approach to Solve Queue Using Two Stacks

To implement this queue class we’ll proceed in the following manner.

• We’ll push() the data into the stacks in such a manner that whenever we call the pop() function, it’ll delete the element as if it was a queue.
• To implement the push() function. We’ll take the following steps.
  • After the N – 1 push() operation, the stacks will look like this,
    • s1: [(N – 1)th item, …….., 3rd, 2nd, 1st] –> TOP
    • s2: [] –> TOP
  • Now, transfer all the elements of s1 into s2. And push the N^th element into s2.
  • After this, transfer all the elements back into s1.
  • Now, the configuration of the stack becomes,
    • s1: [N^th item, (N – 1)^th item, …….., 3^rd, 2^nd, 1^st] –> TOP
    • s2: [] –> TOP
  • Note that push() has become an expensive operation with the time complexity O(N).
• Notice that, if we call pop() on the stack, it’ll remove the first item. This means that our data structure is functioning like a queue.
• To implement the front(), we’ll simply call the top() function on the active stack. And this would do the work for us.

Queue Using Two Stacks Problem In C++ Program

#include <iostream>
#include <stack>

using namespace std;

template <typename T>
class Queue
{
// private data members of the queue
private:
    // queues to hold the data
    stack <T> s1;
    stack <T> s2;

    // variable to store the size of the queue
    int size;

    // false denotes that s1 is active
    // true denotes that s2 is active
    // based on this member, will conduct the insertion
    // and deletion operations
    bool flag;

// public functions and data memebers of the class
public:
    // initialize the size of the queue with 0
    Queue(): size(0) {}

    // implementing the push function
    void push(T element)
    {
	    // increase the size of the queue
	    size++;

	    // first put all the elements of s1
	    // into s2
	    while(!s1.empty())
	    {
		    s2.push(s1.top());
		    s1.pop();
	    }

	    // now insert the new element into s2
	    s2.push(element);

	    // now transfer all the elements of s2
	    // into s1
	    while(!s2.empty())
	    {
		    s1.push(s2.top());
		    s2.pop();
	    }
    }

    // checking if the stack is empty
    bool is_empty()
    {
        return size == 0;
    }

    void pop()
    {
	// before popping check if the
	// stack is already empty or not
        if(!is_empty())
        {
            size --;
            s1.pop();
        }
        else
        {
            cout << "The queue is already Empty" << endl;
        }
    }

    T front()
    {
        return s1.top();
    }

    int get_size()
    {
        return size;
    }
};

template <typename T>
void print_queue(Queue <T> q)
{
    cout << "||*******************************************||" << endl;
    cout << "The queue is :" << endl;
    while(!q.is_empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
    cout << "||*******************************************||" << endl;
}

int main()
{
    Queue <string> q;

    cout << "Enter the number of elements" << endl;
    int n; 
    cin >> n;

    while(n--)
    {
        string str;
        cin >> str;

        q.push(str);
    }

    print_queue(q);

    return 0;
}

Output

Conclusion

In this article, we learned to implement a queue class using two stacks. We used the STL(Standard Template Library) to make use of the queue. We also implemented a C++ program to demonstrate the working of this custom queue class. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/56918/0-1-knapsack-using-cpp

https://www.journaldev.com/61662/intersection-point-of-two-linked-lists-cpp