题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

思路

栈：先进后出
队列：先进先出

一个队列负责进队列，一个队列负责出队列。

代码

  1. # 两个栈模拟队列的进、出
  2. class Queue:
  3.     def __init__(self):
  4.         self.stack1 = []
  5.         self.stack2 = []
  7.     def append_Tail(self, element):
  8.         self.stack1.append(element)
  10.     def delete_Head(self):
  11.         # 如果stack2不为空，直接弹出栈顶元素
  12.         if len(stack2) != 0:
  13.             self.stack2.pop()
  14.         elif len(stack2) == 0 and len(stack1) != 0:
  15.             while len(stack1):
  16.                 # stack1元素全部压入stack2
  17.                 data = stack1.pop()
  18.                 stack2.append(data)
  19.             stack2.pop()
  20.         else:
  21.             raise ValueError('queue is empty!'_

相关题目：两个队列实现一个栈，也是类似的方法。

栈实现队列

  1. class MyQueue:
  3.     def __init__(self):
  4.         """
  5.         Initialize your data structure here.
  6.         """
  7.         self._enqueue = []
  8.         self._dequeue = []
  11.     def push(self, x: int) -> None:
  12.         """
  13.         Push element x to the back of queue.
  14.         """
  15.         self._enqueue.append(x)
  18.     def pop(self) -> int:
  19.         """
  20.         Removes the element from in front of queue and returns that element.
  21.         """
  22.         if self.empty():
  23.             return
  25.         if len(self._dequeue) == 0:
  26.             # 出队的栈是空，将入队的元素push到出队栈
  27.             while len(self._enqueue) != 0:
  28.                 self._dequeue.append(self._enqueue.pop())
  29.         #     self._dequeue.pop()
  30.         # else:
  31.         #     # 出队的栈有元素
  32.         #     self._dequeue.pop()
  33.         return self._dequeue.pop()
  37.     def peek(self) -> int:
  38.         """
  39.         Get the front element.
  40.         """
  41.         if self.empty():
  42.             return
  44.         if len(self._dequeue) == 0:
  45.             while len(self._enqueue) != 0:
  46.                 self._dequeue.append(self._enqueue.pop())
  47.         return self._dequeue[-1]
  50.     def empty(self) -> bool:
  51.         """
  52.         Returns whether the queue is empty.
  53.         """
  54.         if len(self._enqueue) == 0 and len(self._dequeue) == 0:
  55.             return True
  56.         else:
  57.             return False
  59. # Your MyQueue object will be instantiated and called as such:
  60. # obj = MyQueue()
  61. # obj.push(x)
  62. # param_2 = obj.pop()
  63. # param_3 = obj.peek()
  64. # param_4 = obj.empty()