3.栈和队列
3.1 栈
3.1.1 栈的基本概念
逻辑结构:线性表(操作受限)
存储结构:1.顺序栈 2.链栈
数据运算:先进后出(LIFO)
3.1.2 栈的顺序存储结构
1.顺序存储结构代码描述:
#define Maxsize 50
typedef struct{
Elemtype data[Maxsize];
int top;
}SqStack;
栈顶指针:S.top,初始时设置S.top=-1;栈顶元素:S.data[S.top];
进栈操作:1.判断栈满(S.top==MaxSize-1) 2.top++ 3. S.data[S.top]=x
出栈操作:1.判断栈空(S.top==-1) 2.x=S.data[S.top] 3.top--
栈长:S.top+1
2.共享栈
栈顶指针(初始):top0=-1,top1=Maxsize
进栈操作:1.判断栈满(top1-top0=1) ; top0++ ; 赋值
2.**判断栈满(top1-top0=1)** ; **top1--** ; 赋值
出栈操作:1.判断栈空(top0==-1) ; 赋值 ; top0--
2.判断栈空(top1==Maxsize) ; 赋值 ; top1++
3.1.3 链栈
采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。
多个栈一般采用链栈的方式。
3.1.4 考点
卡特兰数(出栈数量):若X_i已经出栈,则前面尚未出栈的元素一定逆置有序的出栈。
3.2 队列
3.2.1 队列的基本概念
队列也是一种操作受限的线性表,先进先出(FIFO)。
3.2.2 队列的顺序存储结构
1.顺序队列
队头指针(front):指向队头元素
队尾指针(rear):指向队尾元素的下一个位置
初始状态(队空条件):Q.front=Q.rear=0
进队操作:判断队满,赋值,rear++
出队操作:判断队空,赋值,front++
当front 和rear都在结尾时,再次入队会出现溢出,这是假溢出,由此引出循环队列来解决这个问题。
2.循环队列(重点)
初始状态(非队空条件):Q.front=Q.rear=0
进队操作:判断队满,赋值,Q.rear=(Q.rear+1)%Maxsize
出队操作:判断队空,赋值,Q.front=(Q.front+1)%Maxsize
队列长度:(Q.rear+Maxsize-Q.front)%Maxsize
判断队空,队满:
1.牺牲一个单元
队满条件:(Q.rear+1)%Maxsize==Q.front
队空条件:Q.front==Q.rear
2.增加表示元素个数的数据成员
队满条件:Q.front==Q.rear&&Q.size==Maxsize
队空条件:Q.front==Q.rear&&Q.size==0
3.类型中增加标志tag
队满条件:Q.front==Q.rear&&Q.tag==1
入队操作同时将tag置为1
队空条件:Q.front==Q.rear&&Q.tag==0
出队操作同时将tag置为0
3.2.3 队列的链式存储结构
1.不带头节点的链式队列
队头指针:队头节点
队尾指针:队尾节点(不同于顺序存储)
初始状态:Q.front=Q.rear=NULL
入队操作:建立新节点s,rear->next=s,rear=rear->next(若为第一个节点,则front=rear)
出队操作:判断队空,取出队头元素,front=front->next(若最后一个元素的删除则置front=rear=NULL)
判断队空:Q.front**==Q.rear==NULL**(仅等于无法判断,只有一个元素也是等于)
2.带头结点的链式队列
队头指针:头结点
队尾指针:队尾节点
初始状态:Q.front=Q.rear=head
入队操作:建立新节点s,rear->next=s,rear=rear->next(不用判断第一个节点)
出队操作:判断队空,取出队头元素,front=front->next(若最后一个元素的删除则置front=rear(非NULL))
判断队空:Q.front**==**Q.rear(不用判断NULL,只有一个元素,front=head,rear不是)
3.2.4 双端队列
输出受限的双端队列:允许在一端进行插入和删除,另一端只允许插入
输入受限的双端队列:允许在一端进行插入和删除,另一端只允许删除
不能得到的 | 相同 | 不同 |
---|---|---|
输入受限 | 4231 | 4213 |
输出受限 | 4231 | 4132 |
双端队列的可能序列判断,在中间画竖线,两边方向依次递增。
列:b|acde,db|ace,ecb|ad
3.3 栈的应用
3.3.1.括号匹配
(1)遇到左括号入栈
(2)遇到右括号出栈一个与它对比,不同则失败
(3)扫描完时栈为空则匹配
3.3.2表达式求值
转化 | 后缀表达式 | 前缀表达式 |
---|---|---|
中缀表达式 | 1.按优先级对所有运算单位加括号 2.运算符移到括号后面 3.去括号 |
1.按优先级对所有运算单位加括号 2.运算符移到括号前面 3.去括号 |
注意不管哪种表达式,变量的顺序不变。
后缀表示式=表达式树的后序遍历
(1)后缀表达式计算值
依次扫描(从左到右):
字母->入栈
符号->从栈中退出两个并计算,将计算结果入栈
栈顶为最后结果
(2)前缀表达式计算值
依次扫描(从右到左):
字母->入栈
符号->从栈中退出两个并计算,将计算结果入栈(注意计算次序,基本原则是字母顺序不变)
栈顶为最后结果
练习:前缀表达式转中缀表达式:+-*^ABCD/E/F+GH
3.3.3栈在递归中的应用
递归:在一个函数,过程或数据结构的定义中又应用了它本身。
递归条件: 递归表达式(递归体)
边界条件(递归出口)
递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。
任何一个递归算法都可以用栈转换,但是不一定要用栈转换。