1, 题目

使用队列实现栈的下列操作：

  1. push(x) -- 元素 x 入栈
  2. pop() -- 移除栈顶元素
  3. top() -- 获取栈顶元素
  4. empty() -- 返回栈是否为空

注意:

  1. 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  2. 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
  3. 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. class MyStack() {
  3.     /** Initialize your data structure here. */
  4.     var main_queue = scala.collection.mutable.Queue[Int]()
  5.     var aux_queue = scala.collection.mutable.Queue[Int]()
  6.     var t: Int = 0
  9.     /** Push element x onto stack. */
  10.     def push(x: Int): Unit = {
  11.         main_queue.enqueue(x)
  12.         t = x
  13.     }
  15.     /** Removes the element on top of the stack and returns that element. */
  16.     def pop(): Int = {
  17.         while (main_queue.size > 1) {
  18.             if (main_queue.size == 2) {
  19.                 t = main_queue.front
  20.             }
  21.             aux_queue.enqueue(main_queue.dequeue())
  22.         }
  23.         val p = main_queue.dequeue()
  24.         val tmp = main_queue
  25.         main_queue = aux_queue
  26.         aux_queue = tmp
  27.         p
  28.     }
  30.     /** Get the top element. */
  31.     def top(): Int = {
  32.         t
  33.     }
  35.     /** Returns whether the stack is empty. */
  36.     def empty(): Boolean = {
  37.         main_queue.isEmpty
  38.     }
  40. }
  2. import queue
  4. class MyStack:
  6.     def __init__(self):
  7.         """
  8.         Initialize your data structure here.
  9.         """
  10.         self.t = 0
  11.         self.main_queue = queue.Queue()
  12.         self.aux_queue = queue.Queue()
  14.     def push(self, x: int) -> None:
  15.         """
  16.         Push element x onto stack.
  17.         """
  18.         self.t = x
  19.         self.main_queue.put(x)
  21.     def pop(self) -> int:
  22.         """
  23.         Removes the element on top of the stack and returns that element.
  24.         """
  25.         while self.main_queue.qsize() > 1:
  26.             if self.main_queue.qsize() == 2:
  27.                 self.t = self.main_queue.get()
  28.                 self.aux_queue.put(self.t)
  29.             else:
  30.                 self.aux_queue.put(self.main_queue.get())
  31.         tmp = self.main_queue.get()
  32.         self.main_queue, self.aux_queue = self.aux_queue, self.main_queue
  34.         return tmp
  36.     def top(self) -> int:
  37.         """
  38.         Get the top element.
  39.         """
  40.         return self.t
  42.     def empty(self) -> bool:
  43.         """
  44.         Returns whether the stack is empty.
  45.         """
  47.         if self.main_queue.qsize()!=0:
  48.             return False
  49.         else:
  50.             return True