Java教程

剑指offer-JZ5 用两个栈实现队列

本文主要是介绍剑指offer-JZ5 用两个栈实现队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

难度:简单

知识点:栈

题目描述:

用两个栈来实现一个队列,分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。

 解题思路:

栈是先进后出,队列是先进先出。

所以,要想实现先进先出,则需要两个栈,从栈顶至栈底,依次把元素挪入另一个栈,此时原栈顶变为栈底,原栈底变为栈顶,再对第二个栈进行存取,也就相当于实现了队列的先进先出功能。

class Solution:
    def __init__(self):
        self.acceptStack = []
        self.outputStack = []
    def push(self, node):
        self.acceptStack.append(node)
        # write code here
    def pop(self):
        if not self.outputStack:  # A中包含元素,B中包含元素,此时需要逐个转移
            while self.acceptStack:
                self.outputStack.append(self.acceptStack.pop())
        if self.outputStack:  # 判断,不为空的时候,返回
            return self.outputStack.pop()
        else: # A、B中都不包含元素
            return None
        # return xx

时间复杂度和空间复杂度都是O(n)

这篇关于剑指offer-JZ5 用两个栈实现队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!