剑指Offer（Python） 两个栈来实现队列

Created2017-10-11Updated2021-03-21

推荐在线编程平台

牛客网在线编程

题目描述

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

分析

题目要求我们用两个栈实现队列的效果，在python里面没有栈，但是我们可以用List模拟。list.append(obj)和list.pop()可以表示栈进和出操作。所以我们只需要想办法实现队列的队首删除的效果：我们可以用一个栈1来记录插入，用栈2将记录的数据进行颠倒顺序，这样获取栈1的第一个元素就是等同于获取栈2的最后一个元素。

基本概念

  • 栈 栈是一种特殊的线性表，限定在表头进行插入和删除操作。
  • 队列 队列是一种特殊的线性表，限定在表尾插入，表头删除。

相关方法

append()

list.append(obj)
  • obj -- 添加到列表末尾的对象。

pop()

list.pop(obj=list[-1])
  • obj -- 可选参数，要移除列表元素的对象，默认最后一个

代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if self.stack2 == []:
            while self.stack1:
                p = self.stack1.pop()
                self.stack2.append(p)
        return self.stack2.pop()