Implementing Stack Using Queue

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Solution:

Oh, that is an amazing problem. I like it so much. This problem made me change my thinking.

In the first solution, I’m going to use additional memory.

static class MyStack {      
  private Queue<Integer> current;     
  private Queue<Integer> tmp;
      
  public MyStack() {         
    current = new ArrayDeque<>();         
    tmp = new ArrayDeque<>();     
  }   

We need the additional Queue for this solution. And let’s start with push. For push operation, we just add a new element to our current queue.

public void push(int x) {         
  current.add(x);     
}  

The main trick you will see is in the pop method. Here we put all elements except the last one in the tmp queue.

And the last element in the queue will be the first element that was pushed.

public int pop() {
  if (current.isEmpty()){
    return -1;
  }
  int size = current.size();
  for (int i = 0; i < size - 1; i ++){
    tmp.add(current.poll());
  }
  int ret = current.poll();
  current = tmp;
  return ret;
}

And what about top method? This method is kinda the same as pop

public int top() {
  if (current.isEmpty()){
    return -1;
  }
  int size = current.size();
  for (int i = 0; i < size - 1; i ++){
    tmp.add(current.poll());
  }
  int ret = current.peek();
  tmp.add(current.poll());
  current = tmp;
  return ret;
}

And for the last empty method, we should just check the current queue

public boolean empty() {
  return current.isEmpty();
}

The second variant is how we can solve this problem.

In this variant, we will not use additional memory.

static class MyStack {

  private Queue<Integer> current;

  public MyStack2() {
    current = new ArrayDeque<>();
  }
}

The main work for this idea will be in the push method. We add the current element and then move elements in front of the current to the end of the queue. Does it clear?

For example, if we have a queue with elements [2,1] and push 3 →

we have queue [3,2,1], then → [1,3,2] → [2,1,3] and… and that is it.

public void push(int x) {
  current.add(x);
  int size = current.size();

  for (int i = 0; i < size-1; i ++){
    current.add(current.poll());
  }
}

We already have the correct element and the start of the queue for all other methods.

public int pop() {
  return current.poll();
}

public int top() {
  return current.peek();
}

public boolean empty() {
  return current.isEmpty();
}

Hope these solutions were clear enough for you.

Leetcode Link: https://leetcode.com/problems/implement-stack-using-queues/