数据结构与算法

D-2 栈+队列的概念

菠萝猫 · 5月12日 · 2020年 180次已读

栈的定义

限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top)。另一端称为栈底(bottom)

不含任何数据元素的栈称为空栈

栈又称为后进先出(Last In First Out)的线性表,LIFO结构

栈的插入操作,叫作进栈,也称压栈、入栈。

栈的删除操作,叫作出栈,也有的叫作弹栈。

栈的抽象数据类型

理论上线性表的操作特性它都具备,可由于它的特殊性,针对一些操作会有些改变。插入和删除操作,改名为push和pop。
file
由于栈本身就是一个线性表,线性表的顺序存储和链式存储,对于栈来说,也是同样适用的。

栈的顺序存储结构

简称顺序栈用数组实现
下标为0的一端作为栈底比较好,因为首元素都存在栈底,变化最小。
具体的代码实现见之前相关的文章,只说理论
定义一个top 变量来指示栈顶元素在数组中的位置,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize,当栈存在一一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1。
栈普通情况、空栈和栈满的情况示意图
file
栈的顺序存储结构一进栈操作
file
出栈操作反过来。
两者没有涉及到任何循环语句,因此时间复杂度均是O(1)。

栈的链式存储结构

简称链栈用链表实现,不需要头结点了
不存在栈满的情况,除非内存没有空间。
进栈出栈没有涉及到任何循环语句,因此时间复杂度均是O(1)。
如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

栈的应用——递归

迭代使用的是循环结构,递归使用的是选择结构。
递归会消耗大量的时间和内存。
在前行阶段,对于每层递归, 函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

栈的应用一四则运算表达式求值

后缀(逆波兰)表示法定义
后缀的原因在于所有的符号都是在要运算数字的后面出现。
后缀表达式计算结果:9 3 1 – 3 * + 10 2 / +
规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符
号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,直到最终获得结果
中缀表达式:标准的四则运算,如:9+ (3-1) x3+10/2
中缀表达式转后缀表达式
规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后
缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,直到最终输出后缀表达式为止。

队列

队列的定义

是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
是一种先进先出(First In First Out) 的线性表,简称FIFO
允许插入的一端称为队尾,允许删除的一端称为队头
file

队列的抽象数据类型

file

顺序存储——数组实现

普通队列的入队复杂度1,出队时间复杂度n
循环队列
定义:头尾相接的顺序存储结构
代码实现见之间的文章。

链式存储——线性表的单链表

尾进头出——链队列
循环队列与链队列基本操作时间复杂度都为1


版权声明:本站采用 “知识共享署名 – 非商业性使用 – 相同方式共享 4.0 中国大陆许可协议” 进行许可,您可以转载本站文章,转载时请以超链接形式标明文章原始出处,Thanks.


0 条回应