算法就是设计，而设计无处不在，故算法无处不在，但这是废话，关键还是，要把握设计的套路，如果能发明套路就更不得了。设计套路中，有一个套路，是定制一个数据结构，就相当于定制出一个专用的厉害武器，然后用于解决特定的问题。
为了解决不同的问题，你可以定制出不同的数据结构。什么是数据结构？就是数据的组织结构，有特点的结构。在诸多数据结构中，有一些是通用的，也就是可以用于很多问题场景，因此它也是常用的。
常用的数据结构中，有一个结构，叫作“栈”。栈，能独立作为一个数据结构，在于它有自己的特点--由此可见，有特点才能自立门派。
栈的特点，是操作都在同一个地方进行，这个地方叫栈顶。入栈、出栈，都在栈顶进行，最先被处理的是最后进栈的元素，“来得早不如来得巧”，这可不是排队。
注意，数据结构的栈，跟c语言内存管理中的“栈”不是一个概念。
befunny
栈的封装实现，哪一门语言可以做到。
为了简化语言的细节与难度，这里选择python，只因为它的易用性。而简化语言的难度，是为了把精力放在算法或数据结构的设计上，而不是纠结于“内存怎么释放”、“怎么自动检测类型”之类的节外生枝的问题上，专注很重要！
（一）栈的实现
python实现栈，很简单，用list（列表）即可。
入栈：s.append('hello stack')
出栈：s.pop()
栈是否为空：not s
偷看一下栈顶：s[-1]
栈的长度：len(s)
比如：
s=[]
s.append(8)
len(s) #1
s.pop() #返回8
not s #True，为空
s.append('hello')
s.append(False)
s.append(8.9)
len(s) #3
s[-1] #8.9
len(s) #3
s.pop() #8.9
len(s) #2
not s #False
pop或append后，栈顶的位置都在变化。
（二）栈的应用
任何一个数据结构，都是因为有应用的场景才存在，也就是时势造英雄。但基于这个数据结构，是可以创造出新的算法的，英雄也可造时势。
栈也不例外。
下面举例说说它的应用场景。
（1）判断左右符号是否配对
左符号：([{，右符号：)]}，配对的情况如：'([]){()}'，不配对的情况如：'[{]}]'。
用栈来理解就是：
遍历所有字符。
遇左符号则入栈；遇右符号则出栈（如果为空则直接返回False），出栈返回的字符如果与右符号不配对则返回False，如果配对则继续下一个字符。
所有字符遍历完后，栈非空则返回False，否则返回True。
def sybol_match(str):
L=['(','{','['];
R=[')','}',']'];
s=[]
for c in str:
if c in L:
s.append(c)
else:
if not s:
return False
a=s.pop()
lp = L.index(a)
rp = R.index(c)
if lp!=rp:
return False
return not s
（2）计算后缀表达式
计算一个表达式时，表达式可以以中缀或后缀的方式录入，而后缀表达式由于不使用括号而简化处理，所以是一个普遍的选择。
补充一下知识点，中缀表达式是我们常用的表达方式，也就是把符号放在数字中间，比如3+4，而前缀或后缀是计算机喜欢的表达方式，因为它更易于解析。前缀就是把符号放在数字前面，比如+ 3 4，而后缀就是符号在数字后面，比如3 4 +。
再比如：
中缀：12*(2/2) 后缀：12 2 2 / *
中缀：10-(2*3) 后缀：10 2 3 * -
中缀：(3-2)*(9/3)+5 后缀：3 2 - 9 3 / * 5 +
用栈来理解就是：
遍历所有分割项（以空格切分）。
遇到数字则入栈；遇到操作符出栈两次（这里简化为都是二元操作，第一次出栈的为参数2，第二次为参数1），并进行运算，再把结果入栈。
遍历完所有分割项后，返回栈中内容（只有一个值）。
operators = {
'+' : lambda p1, p2: p1+p2,
'-' : lambda p1, p2: p1-p2,
'*' : lambda p1, p2: p1*p2,
'/' : lambda p1, p2: p1/p2,
}
def calc_postfix(str):
expr = str.split()
s = []
for e in expr:
if e.isdigit():
s.append(int(e))
else:
f = operators[e]
p2 = s.pop()
p1 = s.pop()
s.append(f(p1, p2))
return s.pop()
（3）背包问题
有若干个物品，每一个物品都有重量。背包有最大容量限制，求刚好装满背包最大容量的所有解。
比如：
物品名称 重量
物品0 1kg
物品1 8kg
物品2 4kg
物品3 3kg
物品4 5kg
物品5 2kg
背包最大可以装10kg，那可能的解是：[0,2,3,5]、[1,5]等。
用栈来理解就是：
尽情地装（按物品顺序，只要能装得下就装），如果剩余容量刚好为0或者之后的各个物品都装不下了，则出栈，即拿掉最后的一个物品k，再继续从k+1个物品开始装。
栈为空而且填装的物品的索引已经超出范围，则结束循环。
由于，总会一直出栈到一个物品都没有，再从下一个物品开始填装，所以一定会出现栈为空且没有物品可装的情况。
def knapsack(w, ws):
"""
w --背包容量
ws --物品重量列表 [1, 3, ..]
"""
ret = []
s = []
i = 0
cnt = len(ws)
rest = w
while s or i < cnt: # 栈为空或者还有得装
while i < cnt and rest > 0: # 还有得装且还有容量
if rest >= ws[i]: # 装得下就装
s.append(i)
rest -= ws[i]
i += 1 # 不管当前的是否装得下，都要尝试下一个
if rest == 0:
ret.append(s[:]) # one solution
i = s.pop()
rest += ws[i]
i += 1
return ret
if __name__ == '__main__':
# print(sybol_match('[{()}]{}[()]()'))
# print(sybol_match('[({}])'))
# print(calc_postfix('12 2 2 / *'))
# print(calc_postfix('3 2 - 9 3 / * 5 +'))
ret = knapsack(10, [1, 8, 4, 3, 5, 2])
print(ret)
（三）总结
工具的价值在于恰当的使用。栈，一个简单的工具，可用于某类问题的解决。
但是，这里的重点不是怎么设计栈这个数据结构，而是，你要有一个意识，就是对于特定的问题，有可能要设计一个专用的数据结构并使用它，当然，通用的数据结构也是一个办法。
mine
网友评论