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

problem

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

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

solution

方法一

思路过程

明白栈和队列两种数据结构，栈先进后出，队列先进先出每一次添加元素，直接放在一个栈的后面每一次删除元素，把栈的元素pop放到另外一个栈中append，删除中转的栈的栈顶元素，再放回原来的栈中也可以每次添加元素，用另外一个栈配合放到栈底，每次删除元素就直接出栈，就是看你在来回换的时候放到什么函数中去实现

代码

python

class CQueue: def __init__(self): # temp作为临时调用的栈 self.temp = [] self.queue = [] def appendTail(self, value: int) -> None: self.queue.append(value) def deleteHead(self) -> int: # 这里真的是傻了，for在in i 循环里面是变化的，就没了 if self.queue: length = len(self.queue) for i in range(length): self.temp.append(self.queue.pop()) res = self.temp.pop() for i in range(length - 1): self.queue.append(self.temp.pop()) return res return -1

优化:

class CQueue: def __init__(self): # temp作为临时调用的栈 self.temp = [] self.queue = [] def appendTail(self, value: int) -> None: self.queue.append(value) def deleteHead(self) -> int: if self.queue: while self.queue: self.temp.append(self.queue.pop()) res = self.temp.pop() while self.temp: self.queue.append(self.temp.pop()) return res return -1

方法二

思路过程

参考这篇文章☞[双栈，一个负责入，一个负责出]，写得很好(https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/xiong-mao-shua-ti-python3-shuang-zhan-yi-ge-fu-ze-/) 两个栈instack 和 outstack，一个用来添加元素，一个用来删除元素调用添加元素的函数时，直接放到instack 栈顶调用减少元素的函数时，查看outstack 是否有元素，如果有，就直接pop，没有就查看instackinstack有的话，把元素放入outstack，否则返回-1， 这样就避免了每次增加或是删除元素的时候，都要把元素来回倒腾一次，做到了较好的优化，跑起来果然有很大的提升

代码

python

class CQueue: def __init__(self): self.instack=[] self.outstack=[] def appendTail(self, value: int) -> None: self.instack.append(value) def deleteHead(self) -> int: if self.outstack: return self.outstack.pop() if self.instack: while self.instack: self.outstack.append(self.instack.pop()) return self.outstack.pop() return -1