Java教程

Offer 09. 用两个栈实现队列(简单)

本文主要是介绍Offer 09. 用两个栈实现队列(简单),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Offer 09. 用两个栈实现队列

一、 没有严格根据题目要求使用两个栈 仅仅是用列表模拟的

   各个函数的复杂度: 时间复杂度O(1)  空间复杂度O(n)

class CQueue(object):
    def __init__(self):
        self.queue = []
    def appendTail(self, value):
        self.queue.append(value)
        
    def deleteHead(self):
        if self.queue:
            return self.queue.pop(0)
        else:
            return -1

该方法简单但不符合要求  但是第一次击败这么多用户  还是写进来了hhh

二、使用两个栈实现队列

   复杂度:

            appendTail:时间复杂度O(1)  空间复杂度O(n)
            deleteHead:时间复杂度O(n)  空间复杂度O(n)

  思想:一个栈可以模拟入队功能   另外一个栈模拟出队功能

class CQueue2(object):

    def __init__(self):
        self.s1, self.s2= [], []

    def appendTail(self, value):
        self.s1.append(value)
    def deleteHead(self):
        if self.s2:
            return self.s2.pop()

        if self.s1:
            while self.s1:
                self.s2.append(self.s1.pop())
            return self.s2.pop()
        else:
            return -1

 

这篇关于Offer 09. 用两个栈实现队列(简单)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!