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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180220G0NJN400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券