栈和队列_计算机数据结构考研
2020-05-18 13:43:12 1 举报AI智能生成
栈和队列_计算机数据结构考研
作者其他创作
大纲/内容
栈和队列_计算机数据结构考研
版权∈ 本人所有 严禁擅自转载和商用 受法律保护
更新记录
2020.5.14 开坑
栈和队列
栈
定义【逻辑结构】
只允许在栈顶进行插入或删除的线性表 先进后出FILO
基本操作【运算】
存储结构
顺序栈
定义
基本操作O(1)
进栈
出栈
读栈
共享栈
两个栈共享一片空间
链栈
与头插单链表类似
基本操作
应用
括号匹配问题
依次扫描所有字符，左括号入栈，右括号弹出栈顶检查是否匹配
流程图
算法实现
表达式求值问题
三种表达式
中缀表达式
操作符放两个数中间 a+b-c
后缀表达式【逆波兰表达式】
操作符放两个数后面 ab+c- = abc-+
不唯一
前缀表达式【波兰表达式】
操作符放两个数前面 -+abc
后缀表达式相关考点
中缀转后缀
手算
先确定各个运算符运算顺序
左优先原则
再 [左操作数 右操作数 运算符] 形式排列
机算
从左往右 压入元素 若扫描到操作符，弹出栈顶两个元素运算并压入栈顶
栈实现
后缀表达式的计算
前缀表达式相关考点
中缀转前缀
右优先原则
再 [ 运算符 左操作数 右操作数] 形式排列
从右往左 压入元素 若扫描到操作符，弹出栈顶两个元素运算并压入栈顶
递归应用
函数调用特点
LIFO 最后被调用的函数最先执行
原始问题 → 属性相同 规模更小的问题
栈储存
调用返回地址
实参
局部变量
队列
只允许一端插入，在另一端删除的线性表 FIFO先进先出
储存结构
顺序队列/循环队列
入队
逻辑上看作一个循环队列
出队【只能队头元素出队】
判空满
方法一
牺牲一个储存单元
方法二
设置 size标记队伍元素
插入成功 size++
删除成功 size--
判空条件 size==0
判满条件 size==MaxSize
方法三
设置 bool型tag
每一插入成功 tag=1
每一删除成功 tag=0
初始 tag=0=rear=front
判空条件 front==rear && tag==0
判满条件 front==rear && tag==1
链式队列
带头结点
不带头结点
出队
判满
不会队满，除非内存不足
双端队列
队列应用
树的层次遍历
图的广度优先遍历
操作系统应用
FCFS 先来先服务
打印的数据缓冲区
章节技巧
栈题目 注意S.top栈顶的值为多少
队列题目 注意rear指向哪个元素 是队尾元素还是队列元素的后一个位置
指向队尾元素
入队Q.rear=[Q.rear+1]%MaxSize;Q.data[Q.rear]=x;
指向队列后一个元素
入队Q.data[Q.rear]=x;Q.rear=[Q.rear+1]%MaxSize;
0 条评论
回复 删除
下一页
