蒙珣的博客

活好当下，做好今天该做的事情。

0%

栈

Posted on Edited on In
Symbols count in article: 4.3k Reading time ≈ 4 mins.

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。先进后出

栈允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

栈的演示

Visualgo这个网站，我们可以看到整个数据结构的变化过程。可以通过左下角的按钮调慢演示过程。可能也自己动手 code 实现了过程，那么再在网站上演示一下元素的各种操作过程，会带来一些更直观的印象。

复杂度分析

栈属于常见的一种线性结构，对于进栈和退栈而言，时间复杂度都为 O(1)

基本功能介绍

在接下来的内容里，我们将逐步介绍栈的具体功能是如何实现的。

1. 创建一个 Stack 的类

对栈进行初始化参数设计

具体实现代码如下：

1
2
3
4
class Stack(object):
    def __init__(self, limit=10):
        self.stack = []  # 存放元素
        self.limit = limit  # 栈容量极限

2. push 进栈

压入 push ：将新元素放在栈顶

当新元素入栈时，栈顶上移，新元素放在栈顶。

具体实现代码如下:

1
2
3
4
5
def push(self, data):
    # 判断栈是否溢出
    if len(self.stack) >= self.limit:
        raise IndexError('超出栈容量极限')
    self.stack.append(data)

3. pop 退栈

弹出 pop ：从栈顶移出一个数据

  • 栈顶元素拷贝出来
  • 栈顶下移
  • 拷贝出来的栈顶作为函数返回值

具体实现代码如下:

1
2
3
4
5
def pop(self):
    if self.stack:
        return self.stack.pop()
    else:
        raise IndexError('pop from an empty stack')  # 空栈不能被弹出

4. 添加其他函数

peek : 查看堆栈的最上面的元素

is_empty : 判断栈是否为空

size : 返回栈的大小

具体实现代码如下：

1
2
3
4
5
6
7
8
9
def peek(self):
    if self.stack:
        return self.stack[-1]

def is_empty(self):
    return not bool(self.stack)

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

完整代码如下：

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
class Stack(object):
    def __init__(self, limit=10):
        self.stack = []  # 存放元素
        self.limit = limit  # 栈容量极限

    def push(self, data):
        # 判断栈是否溢出
        if len(self.stack) >= self.limit:
            raise IndexError('超出栈容量极限')
        self.stack.append(data)

    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            # 空栈不能被弹出元素
            raise IndexError('pop from an empty stack')

    def peek(self):
        # 查看栈的栈顶元素（最上面的元素）
        if self.stack:
            return self.stack[-1]

    def is_empty(self):
        # 查看堆栈的最上面的元素
        return not bool(self.stack判断栈是否溢)

    def size(self):
        # 返回栈的大小
        return len(self.stack)

栈的应用

Stack（栈）在教科书中有一些非常经典的应用，例如：

  • 一些其他有趣的应用程序但没有用于教学目的
  • 括号匹配
  • 后缀计算器

作业

检查括号是否完全匹配

在这个实验中，我们要求使用一个堆栈检查括号字符串是否平衡

根据栈的结构特点，结合 stack 代码，完成以下功能的实现。

有效括号字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。

举例：

((())): True

((()): False

(())): False

目标：

  1. 使用一个堆栈作为数据结构
  2. 来检查括号字符串是否完全匹配

参考代码

注意：请务必自己独立思考解决问题之后再对照参考答案，一开始直接看参考答案收获不大。

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
class Stack(object):
    def __init__(self, limit=10):
        self.stack = []  # 存放元素
        self.limit = limit  # 栈容量极限

    def push(self, data):
        # 判断栈容量是否超出范围
        if len(self.stack) >= self.limit:
            raise IndexError('超出栈容量极限')
        self.stack.append(data)

    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            # 空栈不能弹出元素
            raise IndexError('pop from an empty stack')

    def peek(self):  # 查看栈顶元素
        if self.stack:
            return self.stack[-1]

    def is_empty(self):  #　判断栈是否为空
        return not bool(self.stack)

    def size(self):  # 返回栈的大小
        return len(self.stack)
    
    def show(self):  # 展示堆栈
        return self.stack

def balanced_parentheses(parentheses):
    stack = Stack(len(parentheses))
    for parenthesis in parentheses:
        if parenthesis == '(':
            stack.push(parenthesis)
            # print(stack.show()) 帮助理解
        elif parenthesis == ')':   
            if stack.is_empty():   
                return False
            stack.pop()
            # print(stack.show()) 帮助理解
    return stack.is_empty()

if __name__ == '__main__':
    examples = ['((()))', '((())', '(()))']
    print('Balanced parentheses demonstration:\n')
    for example in examples:
        print(example + ': ' + str(balanced_parentheses(example)))

打开 terminal 终端 运行以下命令即可验证结果。后续课程不再提醒如何运行程序，请大家根据个人需求自行安排。

1
python3 balanced_parentheses.py

解析

去除上面print(stack.show())代码的注释，将打印下面的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
['(']
['(', '(']
['(', '(', '(']
['(', '(']
['(']
[]
((())): True
['(']       
['(', '(']  
['(', '(', '(']
['(', '(']
['(']
((()): False
['(']
['(', '(']
['(']
[]
(())): False

可以看出

1
2
if parenthesis == '(':
            stack.push(parenthesis)

在循环中，如果遇到 ‘(‘ 就会被放入堆栈中

1
2
3
4
elif parenthesis == ')':   
            if stack.is_empty():   
                return False
            stack.pop()

如果遇到 ‘)’ 就会从堆栈中去除一个符号 ‘(‘ 。

所以，”((()))” 符号，入栈三个 ‘(‘ 符号，因’)’循环判断三次，即 ‘(‘ 入栈三次，出栈三次，结果为空

1
2
3
4
5
6
['(']
['(', '(']
['(', '(', '(']
['(', '(']
['(']
[]

“((())” 符号，入栈三个 ‘(‘ 符号，因’)’循环判断两次，即出栈两次，剩余一个’(‘ 。结束循环后判断栈是否为空 return stack.is_empty() ，该栈不为空，返回False

1
2
3
4
5
['(']       
['(', '(']  
['(', '(', '(']
['(', '(']
['(']

“(())” 符号，入栈两个 ‘(‘ 符号，因’)’循环判断三次，即出栈三次，程序中加入了if语句判断，是否为空，防止程序以外终止。

1
2
3
4
['(']
['(', '(']
['(']
[]

在第二次出栈的时候，该栈已为空栈，第三次出栈则会触发.pop()方法的提示，’pop from an empty stack’

1
2
3
elif parenthesis == ')':   
	if stack.is_empty():   
		return False

所以if stack.is_empty() 提前判断了该栈，直接返回False