Welcome to Subscribe On Youtube

225. Implement Stack using Queues

Description

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

 

Constraints:

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

 

Follow-up: Can you implement the stack using only one queue?

Solutions

Solution 1: Two Queues

We use two queues $q_1$ and $q_2$, where $q_1$ is used to store the elements in the stack, and $q_2$ is used to assist in implementing the stack operations.

• push operation: Push the element into $q_2$, then pop the elements in $q_1$ one by one and push them into $q_2$, finally swap the references of $q_1$ and $q_2$. The time complexity is $O(n)$.
• pop operation: Directly pop the front element of $q_1$. The time complexity is $O(1)$.
• top operation: Directly return the front element of $q_1$. The time complexity is $O(1)$.
• empty operation: Check whether $q_1$ is empty. The time complexity is $O(1)$.

The space complexity is $O(n)$, where $n$ is the number of elements in the stack.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• import java.util.Deque;
  
  class MyStack {
      private Deque<Integer> q1 = new ArrayDeque<>();
      private Deque<Integer> q2 = new ArrayDeque<>();
  
      public MyStack() {
      }
  
      public void push(int x) {
          q2.offer(x);
          while (!q1.isEmpty()) {
              q2.offer(q1.poll());
          }
          Deque<Integer> q = q1;
          q1 = q2;
          q2 = q;
      }
  
      public int pop() {
          return q1.poll();
      }
  
      public int top() {
          return q1.peek();
      }
  
      public boolean empty() {
          return q1.isEmpty();
      }
  }
  
  /**
   * Your MyStack object will be instantiated and called as such:
   * MyStack obj = new MyStack();
   * obj.push(x);
   * int param_2 = obj.pop();
   * int param_3 = obj.top();
   * boolean param_4 = obj.empty();
   */
  

• class MyStack {
  public:
      MyStack() {
      }
  
      void push(int x) {
          q2.push(x);
          while (!q1.empty()) {
              q2.push(q1.front());
              q1.pop();
          }
          swap(q1, q2);
      }
  
      int pop() {
          int x = q1.front();
          q1.pop();
          return x;
      }
  
      int top() {
          return q1.front();
      }
  
      bool empty() {
          return q1.empty();
      }
  
  private:
      queue<int> q1;
      queue<int> q2;
  };
  
  /**
   * Your MyStack object will be instantiated and called as such:
   * MyStack* obj = new MyStack();
   * obj->push(x);
   * int param_2 = obj->pop();
   * int param_3 = obj->top();
   * bool param_4 = obj->empty();
   */
  

• # one queue
  
  '''
  push(1), [1]
  push(2), [1,2] => [2,1]
  push(3), [2,1,3] => [1,3,2] => [3,2,1]
  push(4), [3,2,1,4] => switch 3 time to get [4,3,2,1]
  push(5), [4,3,2,1,5] => switch 4 time to get [5,4,3,2,1]
  '''
  class Stack:
  
      def __init__(self):
          self._queue = collections.deque()
  
      def push(self, x):
          q = self._queue
          q.append(x)
          for _ in range(len(q) - 1):
              q.append(q.popleft())
          
      def pop(self):
          return self._queue.popleft()
  
      def top(self):
          return self._queue[0]
      
      def empty(self):
          return not len(self._queue)
  
  # Your MyStack object will be instantiated and called as such:
  # obj = MyStack()
  # obj.push(x)
  # param_2 = obj.pop()
  # param_3 = obj.top()
  # param_4 = obj.empty()
  
  ############
  
  from collections import deque
  
  # two queues
  class MyStack:
  
  	def __init__(self):
  		self.q1 = deque()
  		self.q2 = deque()
  
  	def push(self, x: int) -> None:
  		self.q1.append(x)
  
  	def pop(self) -> int:
  		while len(self.q1) != 1:
  			self.q2.append(self.q1.popleft())
  
  		val = self.q1.popleft()
  		self.q1, self.q2 = self.q2, self.q1
  		return val
  
  	def top(self) -> int:
  		while len(self.q1) != 1:
  			self.q2.append(self.q1.popleft())
  
          # tried to re-use while part, but seems not achievable, since val is retrieved in-between 
  		val = self.q1[0]
  		self.q2.append(self.q1.popleft())  # note: add back to q2, so q1 will always be empty
  
  		self.q1, self.q2 = self.q2, self.q1
  		return val
  
  
  	def empty(self) -> bool:
  		return not self.q1
  
  # Your MyStack object will be instantiated and called as such:
  # obj = MyStack()
  # obj.push(x)
  # param_2 = obj.pop()
  # param_3 = obj.top()
  # param_4 = obj.empty()
  
  

• type MyStack struct {
  	q1 []int
  	q2 []int
  }
  
  func Constructor() MyStack {
  	return MyStack{}
  }
  
  func (this *MyStack) Push(x int) {
  	this.q2 = append(this.q2, x)
  	for len(this.q1) > 0 {
  		this.q2 = append(this.q2, this.q1[0])
  		this.q1 = this.q1[1:]
  	}
  	this.q1, this.q2 = this.q2, this.q1
  }
  
  func (this *MyStack) Pop() int {
  	x := this.q1[0]
  	this.q1 = this.q1[1:]
  	return x
  }
  
  func (this *MyStack) Top() int {
  	return this.q1[0]
  }
  
  func (this *MyStack) Empty() bool {
  	return len(this.q1) == 0
  }
  
  /**
   * Your MyStack object will be instantiated and called as such:
   * obj := Constructor();
   * obj.Push(x);
   * param_2 := obj.Pop();
   * param_3 := obj.Top();
   * param_4 := obj.Empty();
   */
  

• class MyStack {
      q1: number[] = [];
      q2: number[] = [];
  
      constructor() {}
  
      push(x: number): void {
          this.q2.push(x);
          while (this.q1.length) {
              this.q2.push(this.q1.shift()!);
          }
          [this.q1, this.q2] = [this.q2, this.q1];
      }
  
      pop(): number {
          return this.q1.shift()!;
      }
  
      top(): number {
          return this.q1[0];
      }
  
      empty(): boolean {
          return this.q1.length === 0;
      }
  }
  
  /**
   * Your MyStack object will be instantiated and called as such:
   * var obj = new MyStack()
   * obj.push(x)
   * var param_2 = obj.pop()
   * var param_3 = obj.top()
   * var param_4 = obj.empty()
   */
  
  

• use std::collections::VecDeque;
  
  struct MyStack {
      /// There could only be two status at all time
      /// 1. One contains N elements, the other is empty
      /// 2. One contains N - 1 elements, the other contains exactly 1 element
      q_1: VecDeque<i32>,
      q_2: VecDeque<i32>,
      // Either 1 or 2, originally begins from 1
      index: i32,
  }
  
  impl MyStack {
      fn new() -> Self {
          Self {
              q_1: VecDeque::new(),
              q_2: VecDeque::new(),
              index: 1,
          }
      }
  
      fn move_data(&mut self) {
          // Always move from q1 to q2
          assert!(self.q_2.len() == 1);
          while !self.q_1.is_empty() {
              self.q_2.push_back(self.q_1.pop_front().unwrap());
          }
          let tmp = self.q_1.clone();
          self.q_1 = self.q_2.clone();
          self.q_2 = tmp;
      }
  
      fn push(&mut self, x: i32) {
          self.q_2.push_back(x);
          self.move_data();
      }
  
      fn pop(&mut self) -> i32 {
          self.q_1.pop_front().unwrap()
      }
  
      fn top(&mut self) -> i32 {
          *self.q_1.front().unwrap()
      }
  
      fn empty(&self) -> bool {
          self.q_1.is_empty()
      }
  }
  
  

All Problems

All Solutions