数据结构与算法(3)--栈抽象数据类型及Python实现
数据结构与算法(3)–栈抽象数据类型及Python实现
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. 准则
括号的使用必须遵循 “平衡”规则首先，每个开括号要恰好对应一个闭括号；其次，每对开闭括号要正确的嵌套
正确的括号： (()()()())， (((())))，(()((())()))
错误的括号： ((((((())， ()))， (()()(()
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”的过程， 得到的余数是从低到高的次序， 而输出则是从高到低， 所以需要一个栈来反转次序。
如下图所示
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
参考
中国大学mooc - 数据结构与算法Python版
作者：安静到无声
