Implementation of stacks using queues

Approach 2 -By making pop() operation costly

Algorithm 

• Push Operation – To push an element to the stack, simply enqueue the element into the first queue q1.
   

Time Complexity – It is O(1) as the enqueue operation in a queue is O(1).
 

• Pop Operation –  Since we enqueue all the elements into the first queue, the last entered element lies at the rear end of the first queue. So, to ensure the Last In First out property of stack, the element at the rear end should be removed.
   

We do this by moving all the elements from the first queue,q1, to the second queue,q2, except the last element. Finally, remove this last element from q1 and move the elements back from q2 to q1. 

Time Complexity –  It is O(n) as for every pop operation, we move the elements of the first queue twice between the first and second queue.
 

Space Complexity –  It is O(n) as we use two additional queues for the implementation of stack functions.

Let’s take an example to understand the implementation of stacks using queues by following approach 2 – 

Consider we are given the following series of operations - 

5,3,1,P

Initially, we have two empty queues Q1 and Q2.

Step 1: Enqueue 5 to the first queue i.e., Q1.

Step 2: Enqueue 3 into the queue Q1.

Step 3:  Enqueue 1 into the queue Q1.

Step 4: Next, we need to do a pop operation.

Move all the elements except 1 from Q1 to Q2.

Pop 1 from Q1. 

Finally, move  5 and 3 back to Q1.

Must Read Stack Operations

C++ Implementation 

• C++

C++

/*
C++ code for implementation of stacks using queues - Push- O(1) and Pop - O(n)
*/


#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;


// Define and implement a stack class using two queues
class Stack
{
    queue<int> q1, q2;


public:
    // Insert a new element into the stack
    void push(int data)
    {
        // Push the new element into q1
        q1.push(data);
        cout << "Pushed: " << data << endl;
    }


    // Remove the top element from the stack
    void pop()
    {
        // if the first queue is empty
        if (q1.empty())
        {
            cout << "Stack Underflow\n";
            return;
        }


        /*Move all elements except the last from q1 to q2*/
        int front;
        while (!q1.empty())
        {
            if (q1.size() == 1)
            {
                front = q1.front();
            }
            else
            {
                q2.push(q1.front());
            }


            q1.pop();
        }


        /* moving all elements back to q1 from q2*/
        while (!q2.empty())
        {
            q1.push(q2.front());
            q2.pop();
        }


        /* `swap(q1, q2)` can also be done instead of the above loop*/


        cout << "Popped: " << front << endl;
    }
};


int main()
{
    vector<int> data = {5, 7, 31, 4, 2};


    // insert the elements into the stack


    Stack s;
    for (int key : data)
    {
        s.push(key);
    }
    cout << endl;
    for (int i = 0; i <= data.size(); i++)
    {
        s.pop();
    }


    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Pushed: 5
Pushed: 7
Pushed: 31
Pushed: 4
Pushed: 2


Popped: 2
Popped: 4
Popped: 31
Popped: 7
Popped: 5
Stack Underflow

Read about Application of Queue in Data Structure here.

Approach 3- Making Queue act like a Stack

This approach uses a single queue to mimic the behavior of a stack. The key idea lies in manipulating the order elements are added and removed from the queue. 

Algorithm

Here's how it works:

1. Pushing: When adding an element to the "stack," we perform two steps:
   • Add the element to the back of the queue (normal queue behavior).
   • Loop: Starting from the front of the queue, we repeatedly dequeue an element, enqueue it back at the end, and continue until we reach the newly added element.

This loop essentially "reverses" the order of elements in the queue, placing the new element at the front, mimicking a push operation in a stack.

2. Popping: Popping an element is straightforward. We simply dequeue and remove the element from the front of the queue, just like a standard queue operation.

C++ Implementation 

• C++

C++

#include <queue>
#include<iostream>
using namespace std;

class Stack {
private:
  std::queue<int> data;

public:
  // Push operation
  void push(int value) {
    data.push(value);
    // Reverse the queue order to place the new element at the front
    int size = data.size();
    for (int i = 0; i < size - 1; i++) {
      int temp = data.front();
      data.pop();
      data.push(temp);
    }
  }

  // Pop operation
  int pop() {
    if (data.empty()) {
      throw std::runtime_error("Stack underflow");
    }
    int top = data.front();
    data.pop();
    return top;
  }
};

int main() {
  Stack myStack;
  myStack.push(10);
  myStack.push(20);
  myStack.push(30);

  std::cout << myStack.pop() << std::endl; // Output: 30
  std::cout << myStack.pop() << std::endl; // Output: 20
  
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

30
20

Important Note:

This approach achieves stack-like behavior using a queue, but it comes with a trade-off. The "push" operation becomes more complex due to the queue reversal, leading to a higher time complexity (O(n) for push compared to O(1) for a real stack). However, it demonstrates a clever way to utilize existing data structures for different purposes.

Frequently Asked Questions

How can we dynamically implement stack and queue?

To dynamically implement a stack or queue, we can use linked lists. For a stack, we can use the linked list's head for push and pop operations. For a queue, we can use the head for dequeue and the tail for enqueue, allowing dynamic resizing.

Is it possible to implement a stack using a queue?

Yes, it is possible to implement a stack using two queues. By cleverly managing enqueue and dequeue operations across the queues, we can use the Last-In-First-Out (LIFO) behavior of a stack.

Is it possible to implement multiple stacks in a queue?

Yes, multiple stacks can be implemented within a single queue by tagging each element with an identifier indicating its corresponding stack. Operations are managed by dequeuing and re-enqueuing non-target elements, maintaining the integrity of each stack's order.

Conclusion

In this article, we learnt the implementation of stacks using queues. We saw different approaches with a detailed explanation and implementation and compared them based on their time and space complexities. 

Implementation based questions help you have a clear understanding of the data structures used and are also asked in technical interviews.

You can also see the implementation of stacks using arrays and linked lists here.

Check out this problem - Queue Implementation

Don’t stop here. Learn more about stacks, queues and various other concepts from Code360 blogs. T