Leetcode

Implement Stack using Queues

  • 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