Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack ( , , , and ). push top pop empty Implement the class: MyStack Pushes element x to the top of the stack. void push(int x) Removes the element on the top of the stack and returns it. int pop() Returns the element on the top of the stack. int top() Returns if the stack is empty, otherwise. boolean empty() true false Notes: You must use standard operations of a queue, which means that only , , and operations are valid. only push to back peek/pop from front size is empty 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 in the . put all elements except the last one 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 method? This method is kinda the same as top 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 method, we should just check the current queue empty 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/

2021 - HackerNoon Contributor of the Year - INNOVATION

2022 - HackerNoon Contributor of the Year - Design

2022 - HackerNoon Contributor of the Year - Software Architecture

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

2021 - Rick Sanchez of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Design

Nominated for 2022 - HackerNoon Contributor of the Year - Software Architecture

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

Implementing Stack Using Queue

Too Long; Didn't Read

Sergey Golitsyn

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Implementing Stack Using Queue

Too Long; Didn't Read

Sergey Golitsyn

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES