数据结构与算法(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. 准则

括号的使用必须遵循 “平衡”规则首先，每个开括号要恰好对应一个闭括号；其次，每对开闭括号要正确的嵌套
正确的括号： (()()()())， (((())))，(()((())()))错误的括号： ((((((())， ()))， (()()(()

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. 更多种的括号的匹配

在实际的应用里， 我们会碰到更多种括号

1. 如python中列表所用的方括号“[]”
2. 字典所用的花括号“{}”
3. 元组和表达式所用的圆括号“()”

这些不同的括号有可能混合在一起使用，因此就下面这些是匹配的
{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }
下面这些是不匹配的
( [ ) ] ( ( ( ) ] ) )
[ { ( ) ]
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

参考

中国大学mooc - 数据结构与算法Python版