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