题目

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。

题目地址：https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

相关题目：两个队列实现栈

思路

使用两个栈（stack1、stack2）来实现一个队列，主要的思路是做数据的迁移，具体如下：
用stack1 来保存压入的数据，当要弹出时，将stack1 依次弹出放入 stack2 中，stack2 中栈顶的元素就是要弹出的元素

  • 压入操作
    • 当 stack2 为空时或者只有一个元素时，元素直接压入 stack1。原因是 stack2 只有一个元素时可以让下次的队列的弹出操作更方便
    • 当stack2中的元素个数大于1时，将stack2中的元素依次弹出到stack1中，然后再执行压入操作
  • 弹出操作
    • 当 stack1 和 stack2 都为空时，此时不能弹出
    • 当 stack2 为空时，将 stack1中的元素依次弹出压入到stack2中，然后弹出 stack2 中栈顶的元素

代码

  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def __init__(self):
  4.         self._stack1 = []
  5.         self._stack2 = []
  6.     def push(self, node):
  7.         # write code here
  8.         # stack1 用来保存压入的数据
  9.         if len(self._stack2) == 1 or not self._stack2: # 当 stack2 为空或者长度为 1 时，压入的元素直接保存在 stack1 中
  10.             self._stack1.append(node)
  11.         else:
  12.             while len(self._stack2):
  13.                 self._stack1.append(self._stack2.pop(-1))
  16.     def pop(self):
  18.         # return xx
  19.         if not self._stack1 and not self._stack2:
  20.             return None
  21.         if not self._stack2: # 当 stack2 为空时，将 stack1 弹出压入 stack2
  22.             while self._stack1: 
  23.                 self._stack2.append(self._stack1.pop(-1))
  24.         return self._stack2.pop(-1)