剑指offer 09. 用两个栈实现队列

题目链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

目录

题目：

方法1：交替倒水法（一个栈用来出，一个栈用来入）

方法2：交替倒水法优化

---

题目：

方法1：交替倒水法（一个栈用来出，一个栈用来入）

这是自己首先想到的一个较为简单的思路，假设有两个栈分别为stack1，stack2。

每当需要进行尾插的时候，入栈进入stack2。

每当需要头pop的时候，①把stack2中的元素全倒入stack1；②清空stack2；③取stack1栈顶进行pop操作；④把stack1倒回stack2；⑤清空stack1

另注：这种直接倒置[::-1]的使用不知道算不算偷鸡，理论上是个循环的pop形式

class CQueue(object):
    #用两个栈实现一个队列，并实现两个函数作为appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能
    #在面试的过程中似乎真的遇到过这类型的题目
    def __init__(self):
        self.stack1 = [] # 是一个栈，只能first-in-last-out
        self.stack2 = [] # 是一个栈，只能first-in-last-out

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stack2.append(value)

    def deleteHead(self):
        """
        :rtype: int
        """
        self.stack1 = self.stack2[::-1]
        self.stack2 = []
        if len(self.stack1):
            returnInt = self.stack1[-1]
            self.stack1 = self.stack1[0:-1]
            self.stack2 = self.stack1[::-1]
            self.stack1 = []
        else:
            returnInt = -1

        return returnInt

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

 

方法2：交替倒水法优化

方法1中提到：

每当需要进行尾插的时候，入栈进入stack2。

每当需要头pop的时候，①把stack2中的元素全倒入stack1；②清空stack2；③取stack1栈顶进行pop操作；④把stack1倒回stack2；⑤清空stack1

可以在最后的几步发现，不必再把stack1倒回stack2，因为stack1专门用来除出就行了，节省了一定的时间

class CQueue(object):
    #此方法可能有所作弊，因为直接使用了倒置的[::-1]？但实际上这只是一个循环过程的简单改写
    def __init__(self):
        self.stack1 = [] # 是一个栈，只能first-in-last-out
        self.stack2 = [] # 是一个栈，只能first-in-last-out

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stack2.append(value)


    def deleteHead(self):
        """
        :rtype: int
        """
        if len(self.stack1):
            returnInt = self.stack1[-1]
            self.stack1 = self.stack1[0:-1]
        else:
            if len(self.stack2):
                self.stack1 = self.stack2[::-1]
                self.stack2 = []
                returnInt = self.stack1[-1]
                self.stack1 = self.stack1[0:-1]
            else:
                returnInt = -1

        return returnInt