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/

Implement Stack using Queues

Finding Product of Array Except Self

2021 - HackerNoon Contributor of the Year - INNOVATION

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

Implementing Stack Using Queue

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps