Stack Using Two Queues In C++

Filed Under: C++
Stack Using Two Queues In C

Today, we’ll learn to implement a stack using two queues in C++. It is a popular implementation problem and has been asked about during many technical interviews. Not just interviews, but if you are polishing your DSA concepts, then also this problem is a must. We’ll first go through the basic features of stacks and queues and then move towards the implementation.

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.

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

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

Problem Statement of Stack Using Two Queues

Implement a stack using two queues. Implement basic stack operations like push(), pop(), top(), etc.

Usually, we implement stack classes using vectors. Let’s move towards the concept and develop a solution to this problem.

Concept of Stack Using Two Queues

The approach is easy to implement but has its limitations. We’ll use two queues to implement our stack class. At a time, only one of the two queues will store the data and the other will remain empty. Everything comes at a cost, to implement a stack using two queues, we’ll need to invest in more storage to provide the same functionality. Below are the steps that we’ll follow to code our custom stack class.

  • The pop() function is similar in both data structures. Pushing will be different.
  • To implement the push() function. We’ll proceed as follows.
    • Push the new element into the empty queue.
    • The new element configuration will become,
      • filled_queue: [1st, 2nd, 3rd, …….. , (N – 1)th element]
      • empty_queue: [Nth element]
    • Push the elements from the filled_queue to empty_queue.
    • Note that push() has become an expensive operation with the time complexity O(N).
  • Implementation of the top() is similar to the pop() function. Just check for the currently active queue, and based on this, extract out the front() element from that queue.

Stack Using Two Queues In C++ Program

#include <iostream>
#include <queue>

using namespace std;

template <typename T>
class Stack
{
// public functions and data memebers of the class
public:
    Stack()
    {
        size = 0;
        flag = true;
    }

    // implementing the push function
    void push(T element)
    {
	// as soon as you push an element
	// increase the size of the stack
        size ++;

	// check which queue is currently
	// storing the data
        if(flag)
        {
	    // push the element into the
	    // queue that is currently
	    // empty
            q1.push(element);

	    // now move all the elements
	    // from the other queue, into
	    // this queue
            while(!q2.empty())
            {
                q1.push(q2.front());
                q2.pop();
            }

	    // toggle the flag for future
	    // operations
            flag = false;
        }
        else
        {
            q2.push(element);
            
            while(!q1.empty())
            {
                q2.push(q1.front());
                q1.pop();
            }
            flag = true;
        }    
    }

    // 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 --;
            if(flag)
                q2.pop();
            else
                q1.pop();
        }
        else
        {
            cout << "The stack is already Empty" << endl;
        }
    }

    T top()
    {
        if(flag)
            return q2.front();
        return q1.front();
    }

    int get_size()
    {
        return size;
    }

// private data members of the stack
private:
    // queues to hold the data
    queue <T> q1;
    queue <T> q2;

    // size variable will store the size of the stack
    int size;

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

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;
}

int main()
{
    Stack <string> s;

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

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

        s.push(str);
    }

    print_stack(s);

    return 0;
}
Stack Using Two Queues Code
Code 1
Stack Using Two Queues Code 2
Code 2

Output

Stack Using Two Queues Output
Stack Using Two Queues Output

Conclusion

In this article, we learned to implement a stack class using two queues. We used the STL(Standard Template Library) queue data structure directly as our queue. We also implemented a C++ program to demonstrate the working of this stacked class. That’s all for today, thanks for reading.

Further Readings

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

https://www.journaldev.com/56852/binary-trees-bfs-traversal-cpp

https://www.journaldev.com/61251/generic-programming-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors