How Implement a Queue using two Stacks

Question

Aryan Kumar · Answer

A queue is a data structure that follows the first-in-first-out (FIFO) principle. This means that the first element added to the queue is the first element removed. Queues can be implemented using a variety of data structures, including arrays, linked lists, and stacks.

In this tutorial, we will implement a queue using two stacks. This is a simple and efficient way to implement a queue, and it can be easily adapted to any programming language.

To implement a queue using two stacks, we will use the following two stacks:

in: This stack will hold the elements that are being added to the queue.
out: This stack will hold the elements that are being removed from the queue.

To add an element to the queue, we simply push the element onto the in stack. To remove an element from the queue, we simply pop the element off the out stack.

The following code shows how to implement a queue using two stacks:

Code snippet

class Queue {

  private Stack<Integer> in = new Stack<>();
  private Stack<Integer> out = new Stack<>();

  public void enqueue(int value) {
    in.push(value);
  }

  public int dequeue() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) {
        out.push(in.pop());
      }
    }
    return out.pop();
  }

  public boolean isEmpty() {
    return in.isEmpty() && out.isEmpty();
  }
}

This code implements all of the basic operations of a queue, including enqueue, dequeue, and isEmpty.

The enqueue operation simply pushes the element onto the in stack. The dequeue operation first checks if the out stack is empty. If it is, then the code pops all of the elements from the in stack and pushes them onto the out stack. Once the out stack is not empty, the code pops the element off the top of the out stack and returns it. The isEmpty operation simply checks if both of the stacks are empty.

This implementation of a queue is simple and efficient. It can be easily adapted to any programming language.

Krishnapriya Rajeev · Answer

We can construct a queue using two stacks and no other temporary variables as such: Construct a queue structure consisting of two stacks.While enqueuing, push the items to the first stack; they get stored in the reverse order.While dequeuing, pop elements from the first stack and push them to the second stack, so that the order is corrected. We can then pop the topmost element from the second stack. The space complexity of this algorithm is O(1), as there are no temporary variables. The time complexity for enqueue operation is O(1), however, the worst-case time complexity for the dequeue operation is O(n), since it requires us to move all elements from one stack to the other. The code is implemented as follows:

forum

How Implement a Queue using two Stacks

Can you answer this question?

2 Answers