1. 什么是栈？
是一种有次序的数据项集合，在栈中数据项的加入和移除都发生在同一端。一端叫做栈顶，另一端叫做栈底。
1.1. 特点
- 距离在栈底比较近的数据项，待的时间就比较长。
- 抽象数据类型“栈”是一个有次序的数据集， 每个数据项仅从“栈顶”一端加入到数据集中、 从数据集中移除， 栈具有后进先出LIFO的特性。
1.2. 抽象数据类型“栈”定义为如下的操作
Stack()：创建一个空栈，不包含任何数据项
push(item)：将item加入栈顶，无返回值
pop()：将栈顶数据项移除，并返回，栈被修改
peek()： “窥视”栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
isEmpty()：返回栈是否为空栈
size()：返回栈中有多少个数据项
1.3. 用Python实现ADT Stack
将ADT Stack实现为Python的一个Class，将ADT Stack的操作实现为Class的方法，由于Stack是一个数据集，所以可以采用Python，的原生数据集来实现，我们选用最常用的数据集List来实现。
class Stack: def __init__(self): self.item = [] def isEmpty(self): if self.item == []: return True else: return False def push(self,item): self.item.append(item) def pop(self): return self.item.pop() def peek(self): return self.item[-1] def size(self): return len(self.item)
2. 栈的应用：简单的括号匹配
2.1. 准则
括号的使用必须遵循 “平衡”规则首先，每个开括号要恰好对应一个闭括号；其次，每对开闭括号要正确的嵌套
正确的括号：(()()()())， (((())))，(()((())()))
错误的括号：((((((())， ()))， (()()(()
2.2. Python程序
def perChecker(symbolString): stack = Stack() balaced = True index = 0 while index < len(symbolString) and balaced: symbol = symbolString[index] if symbol=="(": stack.push(symbol) else: if stack.isEmpty(): balaced = False else: stack.pop() index = index + 1 if balaced == True and stack.isEmpty(): return True else: return False if __name__ == "__main__": a = perChecker("(()") print(a) b = perChecker("()()") print(b)
结果显示
False True
2.3. 更多种的括号的匹配
在实际的应用里， 我们会碰到更多种括号
如python中列表所用的方括号“[]”
字典所用的花括号“{}”
元组和表达式所用的圆括号“()”
这些不同的括号有可能混合在一起使用，因此就下面这些是匹配的
{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }
下面这些是不匹配的
( [ ) ] ( ( ( ) ] ) )
[ { ( ) ]
python程序
def perChecker(symbolString): stack = Stack() balaced = True index = 0 while index < len(symbolString) and balaced: symbol = symbolString[index] if symbol in "([{": stack.push(symbol) else: if stack.isEmpty(): balaced = False else: a = stack.pop() if not matches(a,symbol): balaced = False index = index + 1 if balaced == True and stack.isEmpty(): return True else: return False def matches(open,close): opens = "({[" closer = ")}]" return opens.index(open) == closer.index(close) if __name__ == "__main__": a = perChecker("([})") print(a) b = perChecker("()()") print(b)
结果
False True
3. 栈的应用：十进制转换为二进制
3.1. 特点
“除以2”的过程， 得到的余数是从低到高的次序， 而输出则是从高到低， 所以需要一个栈来反转次序。
如下图所示
3.2. python程序实现
def dividBy2(decNumber): divstack = Stack() while decNumber > 0: remainder = decNumber % 2 divstack.push(remainder) decNumber = decNumber // 2 #取整 str1 = "" while not divstack.isEmpty(): str1 = str1 + str(divstack.pop()) return str1 if __name__ == "__main__": str_ = dividBy2(35) print(str_)
结果
100011 • 1
