剑指Offer[09]-用两个栈实现队列

题目

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

python代码

class CQueue(object):

    def __init__(self):
        self.clistin = []
        self.clistout = []

    def appendTail(self, value):
        self.clistin.append(value)

    def deleteHead(self):
        if len(self.clistout)!=0:
            return self.clistout.pop()
        if len(self.clistin)==0:
            return -1
        while len(self.clistin)>0:
            self.clistout.append(self.clistin.pop())
        return self.clistout.pop()

这道题目主要考察数据结构中队列和栈的基本特征,队列是先进先出,而栈是先进后出,也就是说,用栈模拟队列的难点在于,在弹出元素时,怎么能弹出栈底元素呢?题目中让我们用两个栈来模拟队列,意思就很明确了,我们需要另外一个栈来帮助我们把栈底的元素调整上来,更具体一点,栈A储存的数据为[1,2,3],当需要弹出元素1时,我们可以用栈B储存[3,2,1],然后使用pop操作弹出1。

在python中,我们限定只能使用append()和pop()操作时,list就可以当做是栈

    def appendTail(self, value):
        self.clistin.append(value)

这是插入元素,我们使用append来完成入队操作,存储在clistin中

    def deleteHead(self):
        if len(self.clistout)!=0:
            return self.clistout.pop()
        if len(self.clistin)==0:
            return -1
        while len(self.clistin)>0:
            self.clistout.append(self.clistin.pop())
        return self.clistout.pop()

我们通过例子来解释上述代码的含义:

内部状态(栈):
    clistin:[ ]
    clistout:[ ]
入队 :
    clistin:[1,]
    clistout:[ ]
入队 :
    clistin:[1,2,]
    clistout:[ ]
入队 :
    clistin:[1,2,3,]
    clistout:[ ]
出队:
    将clistin反转存入clistout:
    clistin:[ ]
    clistout:[3,2,1,]
    再pop:
    clistin:[ ]
    clistout:[3,2,]
入队 :
    clistin:[4]
    clistout:[ 3,2,]

数据结构还是变成的基础,里面的思想会出现在各种业务场景中。

发表评论

电子邮件地址不会被公开。