2、栈与栈的应用

发表于 更新于 分类于 ， 本文字数： 4.3k 阅读时长 ≈ 4 分钟

摘要：跟随b站陈斌老师学习数据结构与算法第二课。

线性结构Linear Structure

所谓线性结构，就是一种有序数据项的集合，其中每个数据项都有唯一的前驱与后继（第一个与最后一个除外）。其实从名称上就可以看出，线性结构就是将数据串成串的一种数据结构，与之对应的就是树与图。

根据数据增项增减的方式不同，就有了不同的线性结构，有的结构只允许从数据项一端添加，而有的数据项允许从两端删除。

python中常用的四个线性结构分别是：栈Stack、队列Queue、双端队列Deque和列表List。

线性结构数据是为了解决各种各样的问题而产生的，后面的结构应用会阐明这句话。

栈Satck

栈介绍

栈是一种有次序的数据项集合，它的数据项添加和删除仅能发生在栈的固定某一端，即栈顶，另一端叫栈底。

日常生活中，书堆、盘子堆等都是栈。

距离栈顶最近的数据，总是最后被加入并且最先被移除；距离栈底最近的数据，总是最先加入并且留存时间最长。

栈的特性是：后进先出（LIFO），这是一种基于数据项保存时间的次序，时间越短离栈顶越近，反之离栈底越近。

这种特性我们称之为反转次序，进栈与出栈的顺序正好相反。

栈抽象数据类型定义

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

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

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

  • peek()：“窥视”栈顶数据项，返回栈顶数据项但不做任何操作，栈不被修改

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

  • size()：返回栈中数据项个数

栈的操作范例如下：

栈的实现

使用List对象实现栈，这里需要注意Stack的两端对应list设置，如果将List的末端作为栈顶，将使push()/pop()的复杂度为$O(1)$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:
    def __init__(self):
        self.items = []

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

    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1]
    
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)

如果要将List首端作为栈顶，只需要修改push() pop() peek()这三个方法。

栈的应用——多种括号匹配

任务：扫描输入的括号串（包含“[]、{}、()”），判断括号串是否都对应封闭。

从左到右扫描括号串，最新打开的左括号必须匹配最后一个右括号，这种次序反转识别，符合栈的特性。

算法实现思路为：遍历括号串，如果是左括号则加载进栈，如果是右括号则先判断是否还有左括号，没有则不匹配，有就判断是否匹配，匹配就删除栈顶最后一个元素（类似于消去）。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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:
                if isMatch(s.peek(), symbol):
                    s.pop()
                else:
                    balanced = False
        index += 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

def isMatch(right, left):
    a = '{[('
    b = '}])'
    return a.index(right) == b.index(left)

其实用上面这个例子来说明栈的应用并不十分好理解，但是可以初步体会到栈存在的意义：反向使用保存的数据，即反转次序。

栈的应用——进制转换

十进制转换为二进制往往采用辗转相除法，即将十进制数一直除以2直到商为0位置，所得到的余数就是对应二进制数从低位到高位的排序。而我们写的数一般都是从高位到低位的，所以就可以用到栈的后进先出特性。

转换算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def baseConverter(decNumber, base):
    digits = "0123456789ABCDEF"
    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % base
        remstack.push(rem)
        decNumber = decNumber // base
    
    binString = ""
    while not remstack.isEmpty():
        binString = binString + digits[remstack.pop()]
    
    return binString

栈的应用——表达式转换

中缀表达式

通常人们写的表达式形式都是“操作数 操作符 操作数”样式的中缀表达式，这类表达式往往因为操作符的优先级之分产生二义性，例如 $A+B*C$ 与 $(A+B)*C$。

所以在复杂表达式中，常常使用括号进行优先级的划分，使用括号能避免表达式的歧义。

如果将操作符放在两个操作数最前面或者最后面，这样可以避免以上问题，例子如下：

中缀表达式 前缀表达式 后缀表达式
$A + B * C + D$ $++A*BCD$ $ABC*+D+$
$(A+B)*(C+D)$ $*+AB+CD$ $AB+CD+*$
$A* B+C *D$ $+* AB*CD$ $AB* CD*+$
$A+B+C+D$ $+++ABCD$ $AB+C+D$

可以看到，距离操作数最近的两个数优先运算，稍远的后面运算，这样可以省去括号且不用考虑操作符的优先级。

表达式的中缀与后缀相互转换，可以使用栈实现。

转换思路

为了分解算法复杂度，可以从“全括号”中缀表达式入手。

全括号中缀表达式

我们看 $(A+(B* C))$ 这个表达式，每一对括号包含一个完整的表达式，其转为后缀表达式为 $ABC * +$ 可以发现，算法实现只需要遍历表达式，遇到相应的符号做相应的事即可：

遇到操作数直接存入目标表达式，遇到操作符或者“(”存入栈，遇到右括号将栈顶的操作符取出放入目标表达式到栈顶为“(”为止。

通用算法

同样考虑 $(A+(BC))$ 这个表达式，对应的后缀表达式为 $ABC+$。

在中缀转后缀的过程中，操作符比操作数晚输出，这就需要有地方暂存操作符，此外操作符可能因为优先级规则需要反转输出，所以考虑使用栈保存未处理的操作符。

在考虑表达式 $(A+B)C$，这里 $+$ 比 $$ 输出早，因为括号让 $+$ 的优先级提升了，所以遇到左括号需要先标记，其后出现的操作符优先级提升了。

考察 $A+B-C+D-E$，转为后缀：$AB+C-D+E-$，若为 $A+B-(C+D)-E$，则转为后缀：$AB+CD+-E-$。

所以算法思路就是：扫描表达式，遇到操作数存入目标表达式；遇到“(”直接入栈；遇到操作符先查看栈是否为空，为空则存入栈，不为空则比较优先级，若优先级更高则清空栈将操作符反向输出，否则清空栈并存入操作符；若为右括号则输出栈顶的操作符，直到栈顶为“(”。

可以采用字典形式记录操作符优先级。算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def infix2postfix(infixexpr):
    prec = {'+':1, '-':1, '*':2, '/':2}
    postfixlist = []
    opStack = Stack()
    tokenList = infixexpr.split()

    for token in tokenList:
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890':
            postfixlist.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixlist.append(topToken)
                topToken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and prec[opStack.peek()] >= prec[token]:
                opStack.push(token)
    while not opStack.isEmpty():
        postfixlist.append(opStack.pop())
    return ' '.join(postfixlist)

栈的应用——后缀表达式求值

后缀表达式求值问题，与中缀表达式转后缀表达式相反，是将操作数存入栈。

扫描表达式，遇到操作数存入栈，遇到操作符取出栈顶两个操作数进行运算，将结果入栈即可。

需要注意像减法与除法这种不满足交换律的操作符，需要记住栈先弹出的是右操作数，后弹出的是左操作数。

算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def value(str):
    numStack = Stack()
    tokenList = str.split()

    for token in tokenList:
        if token in "0123456789":
            numStack.push(token)
        else:
            num2 = numStack.pop()
            num1 = numStack.pop()
            result = doMath(token, num1, num2)
            numStack.push(result)
        return numStack.pop()
    
def doMath(token, num1, num2):
    if token == '*':
        return num1 * num2
    elif token =='+':
        return num1 + num2
    elif token == '/':
        return num1 / num2
    elif token == '-':
        return num1 - num2