数据结构与算法学习笔记：栈Stack

李sir的信息技术课堂 2021-10-06

220

什么是栈？

线性结构的一种，在栈中，数据项的加入和移除都仅发生在同一端。这一端叫栈“顶top”，另一端叫栈“底base”

距离栈底越近的数据项，留在栈中的时间就越长，而最新加入栈的数据项会被最先移除。这种次序通常称为“后进先出LIFO”：Last in First out

栈的特性：反转次序

次序反转的应用：如各个应用中的Undo功能，撤销的是最近的操作。

Stack的ADT（抽象数据类型）实现：

Stack()：创建一个空栈，不包含任何数据项

push(item)：将item加入栈顶，无返回值

pop()：将栈顶数据项移除，并返回，栈被修改

peek()：“窥视”栈顶数据项，返回栈顶的数据项但不移除，栈不被修改

isEmpty()：返回栈是否为空栈

size()：返回栈中有多少个数据项

python实现：

class Stack:
    def __init__(self):
        self.items=[]


    def isEmpty(self):
        return self.items==[]


    def push(self,item):
        self.items.append(item)


    def pop(self):
        return self.items.pop()


    def peek(self):
        return self.items[len(self.items)-1]


    def size(self):
        return len(self.items)

栈的应用：简单括号匹配：

比如(5+6)∗(7+8)/(4+3) 这里的括号是用来指定表达式项的计算优先级。

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

对括号是否正确匹配的识别，是很多语言编译器的基础算法。

算法构造：

从左到右扫描括号串，最新打开的左括号，应该匹配最先遇到的右括号，第一个左括号（最早打开），就应该匹配最后一个右括号（最后遇到）。这种次序反转的识别，正好符合栈的特性！

python代码：

class Stack:
    def __init__(self):
        self.items=[]


    def isEmpty(self):
        return self.items==[]


    def push(self,item):
        self.items.append(item)


    def pop(self):
        return self.items.pop()


    def peek(self):
        return self.items[len(self.items)-1]


    def size(self):
        return len(self.items)


def parChecker(symbolString):
    s=Stack()
    balanced=True
    index=0
    while index<len(symbolString) and balanced:
        symbol=symbolString[index]
        if symbol in '([{':
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced=False
            else:
                top=s.pop()
                if not matches(top,symbol):
                    balanced=False
        index+=1
    if balanced and s.isEmpty():
        return True
    else:
        return False


def matches(open,close):
    opens='([{'
    closes=')]}'
    return opens.index(open)==closes.index(close)


def main():
    symbols=input()
    print(parChecker(symbols))


main()

数据库

文章转载自李sir的信息技术课堂，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构与算法学习笔记：栈Stack

评论