学不完的数据结构(二)栈和队列

692 阅读4分钟

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已经出栈,则前面尚未出栈的元素一定逆置有序的出栈。

\frac{1}{n+1} C ^{n} _{2n}=\frac{1}{n+1} \frac{(2n)!}{n!*n!}

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栈在递归中的应用

递归:在一个函数,过程或数据结构的定义中又应用了它本身。

递归条件递归表达式(递归体)

边界条件(递归出口)

​ 递归的精髓在于能否将原始问题转换属性相同规模较小的问题。

任何一个递归算法都可以栈转换,但是不一定要用栈转换