Implement Stack using Queues LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

Implement Stack using Queues Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (pushtoppop, 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 backpeek/pop from frontsize 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

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to pushpoptop, and empty.
  • All the calls to pop and top are valid.

Implement Stack using Queues Solutions

Time: O(1)
Space: O(n)

C++

class MyStack {
 public:
  void push(int x) {
    q.push(x);
    for (int i = 0; i < q.size() - 1; ++i) {
      q.push(q.front());
      q.pop();
    }
  }

  int pop() {
    const int val = q.front();
    q.pop();
    return val;
  }

  int top() {
    return q.front();
  }

  bool empty() {
    return q.empty();
  }

 private:
  queue<int> q;
};

Java

 
 class MyStack {
  public void push(int x) {
    q.offer(x);
    for (int i = 0; i < q.size() - 1; ++i)
      q.offer(q.poll());
  }

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

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

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

  private Queue<Integer> q = new ArrayDeque<>();
}

Python


class MyStack:
  def __init__(self):
    self.q = deque()

  def push(self, x: int) -> None:
    self.q.append(x)
    for _ in range(len(self.q) - 1):
      self.q.append(self.q.popleft())

  def pop(self) -> int:
    return self.q.popleft()

  def top(self) -> int:
    return self.q[0]

  def empty(self) -> bool:
    return not self.q

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x