04 栈

2018-10-11 约 1507 字预计阅读 4 分钟

后进者先出，先进者后出，这就是典型的“栈”结构。

1. 特性

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。

2. 实现

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。如果要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

2.1 顺序栈

顺序栈依赖一个能自动扩缩容的数组容器，我们可以像数组章节一样，自己实现一个数组容器，也可以直接使用 Python 内置的 list。list 的接口已经包含并大大超过了栈的可操作范围，这里我们采用一种称为"适配器模式"的通用方法，将栈操作委托给一个内部的 list 实例，来实现一个顺序栈。

这个实现起来很简单，就不写的过于复杂了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class ArrayStack(object):
    def __init__(self):
        self._buf = []

    def __len__(self):
        return len(self._buf)

    def pop(self):
        if len(self._buf) < 1:
            raise ValueError('stack is empty')
        return self._buf.pop()

    def push(self, value):
        self._buf.append(value)

2.2 链式栈

在链表的头部插入和删除一个节点的时间复杂度都是 O(1)，因此我们很容易的就可以将链表的头部作为栈顶实现一个链式栈，并且我们的都不管链表的尾，链表只要维护一个指向头节点指针和自身大小的计数即可。

注意不要将链表的尾作为栈顶，虽然可以实现 O(1) 向链尾插入节点，但是删除尾节点需要遍历整个链表。在链表章节，我们已经实现了一个"超纲的"链式栈，这里就不再累述了。

3. 相关算法

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。这种栈被称为函数调用栈。除此之外诸如表达式求值，括号匹配以及实现浏览器的前进后退功能都与栈有关。

3.1 表达式求值

对一个类似于 3-(1/4+7)*3 中缀表达式进行求值分成两步:

将中缀表达式转换为后缀表达式
对后缀表达式进行求值

这两步都用到了栈。为了简单起见，我们只处理+ - * / () 四种运算

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


from stack import ArrayStack
from operator import add, div, mul, sub

op_priority = {
    '(': 1,
    '+': 2,
    '-': 2,
    '*': 3,
    '/': 3,
    ')': 4
}

op_func = {
    '+': add,
    '-': sub,
    '*': mul,
    '/': div
}


def infix_to_postfix(expression):
    s = ArrayStack()
    r = []
    expression = expression.split(' ')
    for e in expression:
        if e not in op_priority:
            r.append(e)
        elif e == '(':
            s.push(e)
        elif e == ')':
            if s.top() != '(':
                r.append(s.pop())
            s.pop()
        else:
            while len(s) > 0:
                t = s.top()
                if op_priority[t] >= op_priority[e]:
                    r.append(s.pop())
                else:
                    break
            s.push(e)
    while len(s) > 0:
        r.append(s.pop())
    return ''.join(r)


def calculate_postfix(expression):
    s = ArrayStack()
    expression = expression.split(' ')
    for e in expression:
        if e not in op_priority:
            s.push(e)
        else:
            right = float(s.pop())
            left = float(s.pop())
            # print left, right
            value = op_func[e](left, right)
            s.push(value)
    return s.pop()


def main():
    print infix_to_postfix('( A + B ) * ( C + D )')
    print infix_to_postfix('A + B * C')
    print calculate_postfix('7 8 + 3 2 + /')
    print infix_to_postfix('6 / 3')
    print calculate_postfix('15 3 /')

3.2 括号匹配

括号匹配有两个类似的问题，一个是类似于对形如 (1 + 2) + (10) 表达式检测括号是否成对出现；另一个更加常用的是检测 HTML 标签是否完整匹配。

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


from stack import ArrayStack

# 括号匹配
def per_check(expression):
    left = '({['
    right = ')}]'
    s = ArrayStack()
    expression = expression.replace(' ', '')
    for e in expression:
        if e in left:
            s.push(left.index(e))
        elif e in right:
            i = right.index(e)
            if len(s) <=0:
                return False
            elif i != s.pop():
                return False
    if len(s) > 0:
        return False
    return True

# html 标签匹配
def html_match(html_string):
    start = 0
    s = ArrayStack()
    while start != -1:
        start = html_string.find('<', start)
        if start == -1:
            break
        end = html_string.find('>', start + 1)
        tag = html_string[start + 1: end]
        print tag
        if tag.startswith('/'):
            if len(s) <= 0:
                return False
            else:
                top = s.pop()
                # print top, tag[1:]
                if top != tag[1:]:
                    return False
        else:
            s.push(tag)
        start = end

    if len(s) > 0:
        return False
    return True


def main():
    # print per_check('{{([][])}()}')
    # print per_check('()]')
    print html_match('<a></a>')

if __name__ == "__main__":
    main()

3.3 浏览器的前进后退功能

 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
27
28


from stack import ArrayStack


class Browser(object):
    def __init__(self):
        self._back = ArrayStack()
        self._forward = ArrayStack()

    def back(self):
        """
        :return: 后退
        """
        if len(self._back) > 0:
            self._forward.push(self._back.pop())

    def forward(self):
        """
        :return: 前进
        """
        if len(self._forward) > 0:
            self._back.push(self._forward.pop())

    def new_click(self):
        """
        :return: 打开新连接
        """
        while len(self._forward) > 0:
            self._forward.pop()

4. linkcode 习题

参考:

目录