目录
使用栈来模拟队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入，不然会导致顺序变乱），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。
class MyQueue(object):
def __init__(self):
# 这里必须要用self，不然后面不能传递值
self.stack_in = []
self.stack_out = []
# time:O(1);space:O(1)
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack_in.append(x)
# time:O(N);space:O(N)
def pop(self):
"""
:rtype: int
"""
if self.empty():
return None
elif self.stack_out:
return self.stack_out.pop()
else:
# 这里也可以用while(self.stack_in)
for i in range (len(self.stack_in)):
element = self.stack_in.pop()
self.stack_out.append(element)
return self.stack_out.pop()
# time:O(N);space:O(N)
def peek(self):
"""
:rtype: int
"""
# if self.empty():
# return None
result = self.pop()
self.stack_out.append(result)
return result
# time:O(1);space:O(1)
def empty(self):
"""
:rtype: bool
"""
return not(self.stack_in or self.stack_out)
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
入队self.push（）
时间复杂度O(1)，直接把元素append到stack_in栈中的最后就行；
空间复杂度O(1)，stack_in 栈多储存一个元素；
出队self.pop（）
时间复杂度O(N)，需要把所有元素全部压入stack_out栈中，再出栈一个元素；
空间复杂度O(N）需要额外的N个内存来储存队列中的元素；
取队首元素self.peek()
因为需要调用self.pop(),然后再push,时间复杂度O(N)；空间复杂度O(N)；
判断空self.empty()
只需要判断两个栈是否为空即可，时间复杂度O(1)，空间复杂度O(1）
可以看出peek()的实现，直接复用了pop()。
这样的项目代码会越来越乱，一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！（踩过坑的人自然懂）
因为一旦代码需要因为业务需求去修改某些地方，如果你是抽象出来的，就只用改抽象的子函数即可，如果你是到处复制粘贴的话，你会忘记你在哪些地方粘贴了，就是项目中的一个定时炸弹；
工作中如果发现某一个功能自己要经常用，同事们可能也会用到，自己就花点时间把这个功能抽象成一个好用的函数或者工具类，不仅自己方便，也方面了同事们。同事们就会逐渐认可你的工作态度和工作能力，自己的口碑都是这么一点一点积累起来的！在同事圈里口碑起来了之后，你就发现自己走上了一个正循环，以后的升职加薪才少不了你！哈哈哈
再多说一些代码开发上的习惯问题，在工业级别代码开发中，最忌讳的就是 实现一个类似的函数，直接把代码粘过来改一改就完事了。
在初始化定义的时候，一定要写self.stack_in 以及self.stack_out,这样这个栈才能在后序定义的函数里操作；
本题不涉及什么高深的算法知识，就是用两个栈模拟队列的行为；
本题只用考虑用户的合法操作，不合法操作，比如在队列为空的时候还弹出队列中的元素可以暂不考虑。
用栈实现队列 - 用栈实现队列 - 力扣（LeetCode）
本题学习时间：80分钟。
刚刚做过 用栈实现队列 的题目，所以做这道题，也想着用一个输入队列，一个输出队列，就可以模拟栈的功能，但是这里的情况不一样了！队列模拟栈，其实一个队列就够了。
那么我们先说一说两个队列来实现栈的思路。
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！
如下面所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1，这就是两个队列实现栈的思路。
那么一个队列其实也可以实现栈了！思路类似！
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。不需要另一个队列来备份，可以直接把要弹出元素之前的所有元素依次弹出并压入一遍即可。
具体的Python实现注意事项：
push（）：直接在queue后面append即可；
pop（）：1. 首先确认不空；2. 先把queue中的所有元素（除了最后一个），依次出列再入列；3. 把queue中的pop出来，即是原队列的最后一个；
top（）：1. 首先确认不空；2. 直接用queue[ -1 ]即可；
empty（）：只用判断queue是否为空即可。
from collections import deque
class MyStack(object):
def __init__(self):
self.queue = deque()
# time:O(1);space:O(1)
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.queue.append(x)
# time:O(N);space:O(N)
def pop(self):
"""
:rtype: int
"""
# 这里用empty的时候，不能写成self.queue.empty()
# 这样就是调用deque自带的函数了（不一定有），我们想调用这里自己定义的
if self.empty():
return None
for i in range(len(self.queue)-1):
element = self.queue.popleft()
self.queue.append(element)
return self.queue.popleft()
# time:O(1)；space:O(1)
def top(self):
"""
:rtype: int
"""
if self.empty():
return None
return self.queue[-1]
# time:O(1)；space:O(1)
def empty(self):
"""
:rtype: bool
"""
if len(self.queue) == 0:
return True
return False
入栈self.push（）
时间复杂度O(1)，直接把元素append到queue中的最后就行；
空间复杂度O(1)，queue 栈多储存一个元素；
出栈self.pop（）
时间复杂度O(N)，需要把除最后一个元素之外的所有元素全部弹出再压入队列中
空间复杂度O(N）需要额外的N个内存来储存栈中的元素；
取栈首元素self.top()
直接用deque的-1下标，时间复杂度O(1)；空间复杂度O(1)；
判断空self.empty()
只需要判断队列是否为空即可，时间复杂度O(1)，空间复杂度O(1）
本题学习时间：45分钟。
没有考虑那么多不匹配的情况，想法是，直接遍历字符串，只有三种情况是匹配的，分别是：record = {"(":")","[":"]","{":"}"}记录在record字典中，取出一个字符串中元素，以及栈顶元素，看是否满足匹配，如果匹配，就消除，如果不匹配，就加入栈，最后看栈是否为空，则可以判断括号是否匹配。
# time：O(N);space:O(N)
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
record = {"(":")","[":"]","{":"}"}
for item in s:
# [] ！= None,这里不能写None
if stack == []:
stack.append(item)
elif stack[-1] in record and record[stack[-1]] == item:
stack.pop()
else:
stack.append(item)
if stack == []:
return True
return False
时间复杂度：O(N)
字符串长度为N，里面的元素需要都遍历一遍，因此时间复杂度为O(N）；
空间复杂度：O(N）
需要一个栈来储存元素，大小应该是O(N）级别的，然后字典的长度是固定的常数级别，总体来说的空间复杂度也为O(N）。
括号匹配是使用栈解决的经典问题，由于栈结构的特殊性，非常适合做对称匹配类的题目；首先要弄清楚，字符串里的括号不匹配有几种情况。一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。
建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。先来分析一下 这里有三种不匹配的情况：
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
第二种情况，括号没有多余，但是 括号的类型没有匹配上。
第三种情况，字符串里右方向的括号多余了，所以不匹配。
我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。
有同学可能会想：”)(”属于哪种情况，实际上属于右括号多余了的情况，因为右括号的时候会发现栈里的元素匹配不上。
大致思路如下：
遍历给定的字符串，碰到左括号：如果碰到（，把）压栈，碰到 [ ，把 ] 压栈，碰到 { ，把 } 压栈；碰到右括号的话，取栈顶元素，和当前遍历元素比较，相等，就pop掉。
第一种情况：已经遍历完了字符串，但是栈不为空，说明有左括号多余了，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符, 说明括号的类型没有匹配上，所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
分析完之后，代码其实就比较好写了，
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
# 方法一，仅使用栈，更省空间
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
if not s:
return True
for item in s:
if item == "(":
stack.append(")")
elif item == "[":
stack.append("]")
elif item == "{":
stack.append("}")
elif not stack or item!=stack[-1]:
return False
else:
stack.pop()
return not stack
时间复杂度：O(N)
字符串长度为N，里面的元素需要都遍历一遍，因此时间复杂度为O(N）；
空间复杂度：O(N）
需要一个栈来储存元素，大小是O(N）级别的，总体来说的空间复杂度也为O(N）。
栈在计算机领域中应用是非常广泛的，如果还记得编译原理的话，编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑，也是使用了栈这种数据结构。
再举个例子，linux系统中，cd这个进入目录的命令我们应该再熟悉不过了。
cd a/b/c/../../
这个命令最后进入a目录，系统是如何知道进入了a目录呢 ，这就是栈的应用
有的同学经常会想学的这些数据结构有什么用，也开发不了什么软件，大多数同学说的软件应该都是可视化的软件例如APP、网站之类的，那都是非常上层的应用了，底层很多功能的实现都是基础的数据结构和算法。
所以数据结构与算法的应用往往隐藏在我们看不到的地方！
Reference: 代码随想录 (programmercarl.com)
本题学习时间：80分钟。
链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
如果本题不是放在栈和队列章节中的题目，大家不容易想到用栈来解决这个问题的话，其实这个问题还挺复杂的，因为不仅要找相邻且相同的两个字母，而且在消除之后还涉及到连续消除的问题，暴力解法得要O(N^2)的复杂度了；
栈适合用来解决匹配的问题
本题要删除相邻相同的元素，相对于20.有效的括号来说其实也是匹配的问题，有效的括号是匹配左右括号，本题是匹配相邻的元素，最后都是做消除的操作，栈很适合用来解决匹配问题。
栈的作用是什么？
我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？
所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作。
具体步骤
以 ” a b b a c a”举例，遍历这个字符串，当栈为空或者栈顶元素和遍历元素不相等的话，则把遍历元素添加到栈中，如果栈顶元素=遍历元素，则pop掉栈顶元素。
“a’’ stack = [ “a”]
“b’’ stack = [ “a’’, “b”] # pop掉“b”
“b” stack = [ “a”]
“a” stack = [ ] # pop掉“a”
“c” stack = [”c”]
“a” stack= [”c”,”a”]
还能不能更优化？
从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以在对字符串进行反转一下，就得到了最终的结果。
如果想优化这种反转的步骤，可以考虑直接用字符串模拟栈的结构，所有操作只在字符串的尾部，push back & pop back，最后直接返回这个字符串就可以了。
# 还是用数组模拟的好
# time:O(N^2);space:O(N)
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
result = ""
for item in s:
if result == "" or result[-1] != item:
result += item # 这感觉需要O(N)
else:
result = result[:-1] # 感觉这需要O(N)
return result
因为Python中字符串的特殊性，用字符串模拟的话，复杂度会更高一些，但是用C++ 的话复杂度会仍然是O(N)，还省去了最后转换的消耗，懂这个意思就好
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
for item in s:
if stack == [] or stack[-1] != item:
stack.append(item) # O(1)
else:
stack.pop() # O(1)
return "".join(stack)
时间复杂度：O(N^2)
遍历外圈需要O(N)，内圈的条件判断之后的两个操作也都是O(N)的复杂度，总体来说是O(N^2)
空间复杂度：O(N)
额外需要一个字符串储存，长度数量级也为O(N)
时间复杂度：O(N)
遍历字符串中的每个元素，复杂度为O(N）内圈的条件判断之后的两个操作都是O(1)的复杂度，所以总体来说是O(N)的复杂度；
空间复杂度：O(N)
额外需要一个数组储存，最后需要变为字符串，都是O(N)的操作，总体O(N)。
这道题目就像是我们玩过的游戏对对碰，如果相同的元素放在挨在一起就要消除。可能我们在玩游戏的时候感觉理所当然应该消除，但程序又怎么知道该如果消除呢，特别是消除之后又有新的元素可能挨在一起。
此时游戏的后端逻辑就可以用一个栈来实现（我没有实际考察对对碰或者爱消除游戏的代码实现，仅从原理上进行推断）
编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈，但不是每种编程语言都支持递归，例如：
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
相信大家应该遇到过一种错误就是栈溢出，系统输出的异常是Segmentation fault（当然不是所有的Segmentation fault 都是栈溢出导致的） ，如果你使用了递归，就要想一想是不是无限递归了，那么系统调用栈就会溢出。
在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）
本题学习时间：50分钟。
ps: 一共花了四个多小时，最后一题是10.2周日补上的。首先做了栈和队列的相互实现，然后做了两道栈的经典应用，总体来说不难，思路要想清楚！~（求推荐）