目录
对比
栈是先进后出的，队列是先进先出的
两者都可以用数组和链表两种形式。
1.数组结构实现较容易
2.用链表结构较复杂
栈结构的基本操作：
1.pop操作
2.top或peek操作
3.push操作
4.size操作
栈结构的基本操作：
与栈操作不同的是，push操作为在对头加入元素
而pop操作是从队列尾部弹出一个元素。
栈和队列的基本操作，时间复杂度都为0(1)
双端队列结构为首尾部都可以压入和弹出
优先级队列为根据元素的优先级值，决定元素的弹出顺序
优先级队列的结构为堆结构，并不是线性结构
DFS 和 BFS
DFS可以用栈来实现，BFS可以用队列来实现。
Notice
平时使用的递归的函数实际上用到了提供的函数系统栈，递归的过程可以看做递归函数依次进入函数栈的处理过程，所以用递归函数可以做的过程都一定可以用非递归的方式实现。
可查询最值的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.cmp = []
def push(self, node):
self.stack.append(node)
if not self.cmp:
self.cmp.append(node)
else:
if node < self.cmp[-1]:
self.cmp.append(node)
else:
self.cmp.append(self.cmp[-1])
def pop(self):
self.stack.pop()
return self.cmp.pop()
def top(self):
return self.stack[-1]
def min(self):
return self.cmp[-1]
双栈队列
编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。
给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。
测试样例：
[1,2,3,0,4,0],6
返回：[1,2]
# -*- coding:utf-8 -*-
class TwoStack:
def __init__(self):
self.stackpop = []
self.stackpush = []
def twoStack(self, ope, n):
result = []
for x in ope:
if x > 0:
self.stackpush.append(x)
else:
if len(self.stackpop):
result.append(self.stackpop.pop())
else:
while len(self.stackpush):
self.stackpop.append(self.stackpush.pop())
result.append(self.stackpop.pop())
return result
if __name__ == '__main__':
sol = TwoStack()
ope = [2, 1, 1, 0, 3, 0]
n = 6
print sol.twoStack(ope, n)
栈的反转
实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。
给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。
测试样例：
[4,3,2,1],4
返回：[1,2,3,4]
# -*- coding:utf-8 -*-
class StackReverse:
def reverseStack(self, A, n):
x=[]
for i in range(n):
x.append(A.pop())
return x
双栈排序
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector
测试样例：
[1,2,3,4,5]
返回：[5,4,3,2,1]
# -*- coding:utf-8 -*-
class TwoStacks:
def twoStacksSort(self, numbers):
return sorted(numbers , reverse=True)
滑动窗口
有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，第二个窗口[3,5,4]的最大值为5，第三个窗口[5,4,3]的最大值为5。第四个窗口[4,3,3]的最大值为4。第五个窗口[3,3,6]的最大值为6。第六个窗口[3,6,7]的最大值为7。所以最终返回[5,5,5,4,6,7]。
给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。
测试样例：
[4,3,5,4,3,3,6,7],8,3
返回：[5,5,5,4,6,7]
# -*- coding:utf-8 -*-
class SlideWindow:
def slide(self, arr, n, w):
if w > n:
return False
list = []
for i in xrange(0,n-w+1):
list.append(max(arr[i:i+w]))
return list
数组变树
对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法。
给定一个无重复元素的数组A和它的大小n，请返回一个数组，其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为-1。
测试样例：
[3,1,4,2],4
返回：[2,0,-1,2]
todo
