栈和队列的算法
1.设计一个栈，在实现栈的基本功能的基础上，再实现返回栈中的最小元素的操作
'''
设计一个栈，在实现栈的基本功能的基础上，再实现返回栈中的最小元素的操作
1. 要求pop、push、getMin操作的时间复杂度都是O(1)
2. 设计的栈类型可以使用现成的栈结构
'''
from collections import deque
import random
class getMinStack:
def __init__(self):
self.mydeque=deque()
self.mixdeque=deque()
def push(self,element):
if(len(self.mydeque)==0):
self.mydeque.append(element)
self.mixdeque.append(element)
elif not element>mixdeque[-1]:
self.mixdeque.append(element)
self.mydeque.append(element)
def pop(self):
element=self.mydeque.pop()
if not element>self.mixdeque[-1]:
self.mixdeque.pop()
return element
def getMix(self):
return self.mixdeque[-1]
if __main__=="__name__":
test=getMinStack()
a=range(1,100,2)
for i in random.sample(a, 9):
test.push(i)
2.用两个栈组成队列
from collections import deque
class TwoStackQueue:
'''
初始化两个空栈
'''
def __init__(self):
self.stackPush=deque()
self.stackPop=deque()
'''
向栈中添加元素,直接将元素加到push栈里面
'''
def add(self,number):
self.stackPush.append(number)
'''
pop需要先将push的一次倒出装到pop里面，然后从pop栈里面pop出一个元素
'''
def pop(self):
if len(self.stackPop)>0:
return self.stackPop.pop()
elif len(self.stackPush)>0:
while len(self.stackPush)>0:
self.stackPush.add(self.stackPush.pop())
return self.stackPop.pop()
else:
raise Exception("empty queue")
'''
'''
def peak(self):
if len(self.stackPop)==0&&len(self.stackPush)==0:
raise Exception("empty queue")
elif len(self.stackPush)==0:
while len(self.stackPush)==0:
self.stackPush.append(self.stackPush.pop())
return self.stackPop[-1]
3.使用仅用递归函数和栈逆序一个栈
递归的基本思想，是把规模较大的一个问题，分解成规模较小的多个子问题去解决，而每一个子问题又可以继续拆分成多个更小的子问题。或者说，必须先解决子问题，再基于子问题来解决当前问题。既然我们要逆序一个栈，就要将栈的最底部拿出来，先这样考虑，极限的情况下，栈只有一个元素，那么直接就弹出这个元素，不需要逆序，如果是两个的元素，先取出一个如果栈不是空的，就继续取，将最低的元素取出返回，再压栈。那么第一个函数 是:
这个时候的函数为:
def getAndRemoveLast(mylist):
result=mylist.pop()
if len(mylist)==0:
return result
else:
last=getAndRemoveLast(mylist)
mylist.push(result)
return last
def revers(mylist):
if len(mylist)==0:
return
temp=getAndRemoveLast(mylist)
revers(mylist)
mylist.push(temp)
4.用一个栈实现另一个栈的排序
from collections import deque
def sortBystack(mylist):
helpstack=deque()
'''
只要栈不为空，就取出当前栈的最顶点的，然后和辅助栈的最上面进行比较，如果辅助栈比较大，就弹出来装到当前栈，这样的话，就会将辅助栈所有比当前栈顶大的全部放到当前栈
'''
while len(mylist)>0:
temp=mylist.pop()
while len(helpstack)>0&&(helpstack[-1]>temp):
mylist.append(helpstack.pop())
helpstack.append(temp)
while len(helpstack)>0:
mylist.append(helpstack.pop())
5.正常的汉贝塔问题
A，B，C三个圆柱，分别为初始位，过渡位，目标位，设A柱为初始位，C位为最终目标位。
（1）将最上面的n-1个圆盘从初始位移动到过渡位
（2）将初始位的最底下的一个圆盘移动到目标位
（3）将过渡位的n-1个圆盘移动到目标位
def hanbei(n,a,b,c):
if n==1:
print('{0}-->{1}'.format(a,c))
else:
hanbei(n-1,a,c,b)
print('{0}-->{1}'.format(a,c))
hanbei(n-1,b,a,c)
hanbei(3,'a','b','c')
6.用栈来求解有限制的汉贝塔问题
不能从最右边的塔直接移动道最左侧，也不能从最左侧搬到最右侧，必须经过中间。
7.滑动窗口
有一个整数数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次都向右边滑一个位置，输入:整形数组arr，窗口大小为w
输出：一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值
def slide_windows(arr,w_size):
max_arr=[]
for i in range(len(arr)-w_size+1):
new_arr=arr[i:i+w_size]
max_arr.append(max(new_arr))
return max_arr
max_arr=slide_windows([4,3,5,4,3,3,6,7],3)
print(max_arr)
