栈和队列
两个栈实现一个队列
求解思路，使用两个栈来回倒—此处已经是优化后的
我们设一个栈A和一个栈B
- 如果是进队操作——-对进A栈
- 如果是退队操作——-检查B栈，如果B中有元素，则B出栈，如果B中没有元素，则将A中元素倒入B中
判断队列为空==两个栈都为空，返回-1
class CQueue(object):
def __init__(self):
self.stack1=[]
self.stack2=[]
def appendTail(self, value):
"""
:type value: int
:rtype: None
"""
self.stack1.append(value)
def deleteHead(self):
"""
:rtype: int
"""
if self.stack2!=[]:
return self.stack2.pop()
else:
if self.stack1==[]:
return -1
else:
while (self.stack1 !=[]):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
实现O1的操作对一个栈实现取min操作
这里的top的操作就是取栈顶的元素输出，而pop的工作就是出栈，但是不用输出元素
在这里我们需要使用一个辅助栈保存绝对降序的保存，如：
因此入栈操作和出栈操作我们需要维护两个栈。
- 因此 push操作： 我们需要对A入栈，然后判断B是否是空，为空则入B栈，非空则需要入比B栈顶元素小的元素，这里需要考虑小于等于，不然在pop操作的时候，会多删了一个相等的数。
- pop操作： 我们先对A出栈，然后判断A出栈的元素是不是在B的栈顶，如果是则出栈
- top：直接返回A的栈顶
- min：直接返回B的栈顶，因为B的栈顶保存了当前绝对降序的数字
代码：
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.Stack1=[]
self.Stack2=[]
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.Stack1.append(x)
if self.Stack2==[]:
self.Stack2.append(x)
else:
if x<=self.Stack2[-1]:
self.Stack2.append(x)
def pop(self):
"""
:rtype: None
"""
a=self.Stack1.pop()
if a==self.Stack2[-1]:
self.Stack2.pop()
def top(self):
"""
:rtype: int
"""
return self.Stack1[-1]
def min(self):
"""
:rtype: int
"""
return self.Stack2[-1]
