数据结构chapter_04
2019-06-19 14:55:28 16 举报AI智能生成
数据结构java
作者其他创作
大纲/内容
栈
定义
特殊的线性表,其插入与删除操作只允许在线性表的一端进行,通常称允许插入与删除的一端为栈顶,不允许的一端为栈底,无元素时为空栈
S=(A+B+C+D+E) 中 A为栈底元素,E为栈顶元素,后进先出表
运算规则
出栈或弹出(POP) 入栈或压入(PUSH)
顺序栈基于数组基本运算
InitStack(S)构造空栈S
StackEmpty判断是否空栈
StackFull(S)判断是否为满栈
Push(S , x)入栈,若栈不满,x压入栈顶
Pop(S)出栈
seqStack
链式栈基于单链表的实现
基本
栈溢出
"上溢" 栈满时进栈
"下溢"栈空时退栈
栈的表示与实现
中缀转后缀表达式
'(' > '*' > '/' > '+' = '-'
如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
队列
定义
入队操作称为队列的插入
出队称为队列的删除
队列的数据元素与线性表的数据元素完全相同
接口
队列的存储分为链式存储与顺序存储
顺序循环队列
解决假溢出
操作`
假设数组空间是m , 只要在入 , 出 队列时,将队首和队尾的指针对m作求模运算即可,取值范围 0 - m-1
入队时 rear = (rear + 1) % maxSize
出队时 front = (front + 1) % maxSize
队空:front == rear
队满: (rear + 1)%maxSize == front
求队长:(rear-front + maxSize)%maxSize
链式队列
定义队列的存储结构基本和线性表的定义相同
特殊的线性表,只考虑对线性表的两端操作的情况,并且只能一端插入,另一端删除
线性表除此之外（不限定一端插入、一端删除），还需要考虑中间的结点的插入、删除、查询等操作。
一个链队由头指针和尾指针唯一确定
基本运算
队列的使用
运算规则
0 条评论
下一页
