python数据结构之栈

"关于python栈的那些事”

节目单

节目1----- 栈的定义及特点

节目2----- 栈的实现

节目3----- 栈的实际运用

节目4----- 栈的拓展应用

1

栈的基本定义及特点

线性结构

你知道线性结构吗?

在讲解栈的之前，我们先了解一下线性结构和非线性结构，线性结构是数据结构按照逻辑分类的一部分。线性结构是一个有序元素的集合。数据元素之间是一对一的的关系，除了首尾元素外，其它元素都是首尾相接的。常用的线性结构有：线性表，栈，队列，双端队列，数组（一维）和字符串。而非线性结构中各个元素不再保持在一个线性序列中，每个元素可能与零个或者多个数据元素发生联系。对应的非线性结构有：二维数组，多维数组，树，图，广义表。同时还有一种集合结构，其数据元素之间无逻辑关系。

栈就是一种线性结构，栈的模型如上图，它的特点是数据元素的添加和删除是在同一端完成的，通常我们称之为栈顶，与之对应的是栈底。这个特点我们一般总结为"LIFO（last in first out）"，新元素总是靠近栈顶，旧元素则靠近栈底。在图中对应的就是新的书本总是放在最上面。

2

栈基于python的实现

Stack

你会用python实现栈么?

Stack() 创建一个新的空栈，不接收参数，返回一个空栈

push(item) 添加一个新元素到栈顶，接收参数，没有返回值

pop() 删除栈顶元素，不接受参数，返回栈顶元素，栈被修改

peek() 返回栈顶元素，栈没有影响

is_empty() 判断栈是否为空，返回值为布尔值

size() 返回栈中元素的个数

注:self 指代实例本身

实现栈这种抽象数据结构(ADT),我们使用了python的内置数据类型列表(list)，我们用了两种实现方式，这两种实现方式有何差别呢？

在第一种实现方式中push()和pop()操作的时间复杂度均为O(1),是一个常量时间，在第二种方式中push()和pop()操作的时间复杂度均为O(n),是一个线性时间。

3

栈的实际应用

括号匹配

你知道编程语言中的括号匹配机制么?

括号匹配是显示计算机科学中的一个问题，我们在各种编程语言中写长表达式的时候，不可避免要用到括号，如果表达式中括号不匹配，编译器(python中叫解释器)就会报错，那究竟该如何实现括号匹配呢？我们可以观察以下括号表达式(我们只把其中的括号提取出来)。

（（（）））

（（（（））（）））

4

栈的拓展应用

符号匹配

你知道怎么符号匹配吗?

在前面我们知道如何进行括号匹配，相比括号匹配，符号匹配就是括号匹配的升级版，在符号匹配中，我们运用了三种符号:括号，中括号，大括号。列举一下几个例子

[ [ { { ( ( ) ) } } ] ]

[ ] [ ] [ ] ( ) { }

在已知如何实现括号匹配的情况下，如何进行符号匹配呢？其实问题的思路还是利用栈，只是其中代码片段做部分修改

"Laughter is the shortest distance between two people"

by Victor Borge