数据结构第三章栈与队列

2023-03-06

字数统计: 2.7k | 阅读时长≈ 10 分钟

系列链接
第一章概述	第二章线性表	第三章栈与队列	第四章串
第五章树与二叉树	第六章图	第七章查找	第八章排序

🔥栈

✍基本概念

栈只允许在一端进行数据操作，不能在中间进行插入（进栈）和删除（出栈）操作，没有元素的栈即空栈，栈内元素先进后出（LIFO）
栈底：不允许操作的一端
栈顶：允许操作的一端

✍基本操作

InitStack(&S)：初始化栈，构造空栈S，分配内存
DestroyStack(&L)：销毁栈，销毁释放S占用空间
Push(&S,x)：进栈，若S未满，则将x加入使之成为新的栈顶
Pop(&S,&x)：出栈，若S非空，则弹处栈顶元素，用x返回
GetTop(S,&x)：读栈顶元素，若栈S非空，则用x返回栈顶元素（不删除）
StackEmpty(S)：判断栈S是否为空，返回bool

✍顺序栈

按顺序空间存储的栈（类似顺序表）

1、顺序栈初始化

#define MaxSize 10    //元素最大个数
typedef struct{
  ElemType data[MaxSize];   //静态数组存放栈中元素
  int top;            //栈顶指针
} SqStack;
void InitStack(SqStack &S){
  S.top=-1;           //初始化栈
}

top指针指向-1即为空

2、顺序栈进栈

bool Push(SqStack &S,ElemType x){
  if(S.top==MaxSize-1)      //满栈，报错
    return false;
  S.top = S.top + 1;        //指针+1
  S.data[S.top]=x;          //新元素入栈
  return true;
}

3、顺序栈出栈

bool Pop(SqStack &S,ElemType &x){   //注意&x
  if(S.top==-1)      //空栈，报错
    return false;
  x=S.data[S.top];    //栈顶元素先出
  S.top = S.top - 1;    //指针再减一
  return true;
}

4、其他

读栈顶元素和出栈类似，只不过无需将指针减1，不再赘述
清空一个栈只需将top指向-1，空间的释放在函数结束会自动完成
上述是一种操作思路，另一种思路是将指针指向栈顶元素之后的那个位置，也就是下一个可以进栈的位置，这使得进栈可以先入栈再移动指针，出栈先指针减一再弹出元素。也因此top指向0即为空栈。
共享栈：即两个栈共用一个空间，栈顶指针分别从空间两头向中间移动
共享栈栈满条件是 top0 + 1 == top1;

✍链栈

链式存储的栈（类似单链表）
链栈的实现方式和单链表几乎一样，不再详细记录，也分为带头结点和不带头结点，推荐是不带头结点。链栈进栈类似单链表头插法，出栈则对应后删操作。

✍栈的应用

括号匹配

IDE开发环境中可以检测括号是否出现配对错误（没有成双成对），当检测到左括号就入栈，当检测到右括号就出栈进行对比，若属于同一形状则匹配成功，反之则匹配失败报错。当检测到右括号而栈为空，则也是报错。

表达式求值

输入一个表达式，如 ((15÷ (7-(1+1))) × 3)-(2+ (1 +1)) 对其求出结果
使用波兰表达式（前缀表达式）和逆波兰表达式（后缀表达式）
表达式各个部分生效顺序可以不同，意味着一个中缀表达式可以对应多个前、后缀表达式。
左优先原则：左边的运算符能先算就先算，这保证了一个中缀表达式得到的后缀表达式的唯一性
右优先原则：左边的运算符能先算就先算，这保证了一个中缀表达式得到的前缀表达式的唯一性
栈实现后缀表达式运算：

从左往右扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到1；否则执行3
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1

栈实现前缀表达式的计算:

从右往左扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到1;否则执行3
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1

中缀表达式转后缀表达式
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

从左到右处理各个元素，直到末尾。可能遇到三种情况:

遇到操作数。直接加入后缀表达式。

遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，自到弹出“(”为止。注意:“(”不加入后缀表达式。

遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

中缀表达式求值 = 中缀表达式转后缀表达式 + 后缀表达式运算，这是算法上的结合，实际上可以同时进行，所以不是简单地将两者独立进行。

递归

函数调用：最后被调用的函数最先被执行（LIFO），函数调用时需要用一个栈存储调用返回地址、实参、局部变量
递归调用时，函数调用栈可称为 “递归工作栈”。每进入一层递归，就将递归调用所需信息压入栈顶；每退出一层递归，就从栈顶弹出相应信息
太多层递归会导致空间复杂度升高，可能导致栈溢出

🔥队列

✍基本概念

队列只允许在一端进行插入（入队），另一端进行删除（出队），无元素的队列即空队列，队内元素先进先出（FIFO）
队头：允许删除操作的一端
队尾：允许插入操作的一端

✍基本操作

lnitQueue(&Q):初始化队列，构造一个空队列Q。
DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间。
EnQueue(&Q,x):入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q,&x):出队，若队列Q非空，删除队头元素，并用x返回。

✍顺序队列

预分配空间

1、顺序队列初始化

#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];   //静态数组存放队列元素
  int front,rear;         //队头指针和队尾指针
} SqQueue;
void InitQueue(SqQueue &Q){   //初始化队列
  Q.rear=Q.front=0;       //队头、队尾指针指向0
}

队尾指针指向下一个可插入元素的位置，队头指针指向队头元素
用Q.rear==Q.front判空

2、顺序队列入队

当队列只有一个空间时就判断为满队列，否则两个指针将重叠，这导致判空和判满冲突。

bool EnQueue(SqQueue &Q,ElemType x){
  if((Q.rear+1)&MaxSize==Q.front)   //判断满的条件
    return false;
  Q.data[Q.rear]=x;   //x插入队尾
  Q.rear=(Q.rear+1)%MaxSize;    //队尾指针+1后取模，保证队列空间循环使用
  return true;
}

如上，队列空间类似环形，新释放的空间能被使用，称为循环队列

3、顺序队列出队

bool DeQueue(SqQueue &Q,ElemType &x){
  if(Q.rear==Q.front)       //判断空
    return false;
  x=Q.data[Q.front];
  Q.front=(Q.front+1)%MaxSize;      //队头指针后移
  return true;
}

4、顺序队列查询

查询通常只查队头元素

bool GetHead(SqQueue Q,ElemType &x){
  if(Q.rear==Q.front)     //判空
    return false;
  x=Q.data[Q.front];
  return true;
}

5、其他

第二种方案可以利用所有申请到的空间，就是在结构体添加一个size变量，实时反馈当前队列的元素，用size的大小进行判空和判满，就不会发生冲突。同时这也增大了结构体空间，但是增加了一个数量信息。
第三种方案，结构体添加一个变量tag记录上一步操作，当上一步进行删除就为0，进行添加就为1，当两个指针相等时，只有上一步进行了添加才能是满的，上一步进行了删除才是空的。该变量可以用bool值比较省空间

✍链式队列

操作思想和单链表差不多，动态分配空间
一般不判满，因为一般是够用的

1、链式队列初始化

链式队列初始化

2、链式队列入队

带头结点

void EnQueue(LinkQueue &Q,ElemType x){
  LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));   //申请新的结点的空间
  s->data=x;
  s->next=NULL;
  Q.rear->next=s;       //新结点插入到rear后
  Q.rear=s;         //修改队尾指针
}

不带头结点

void EnQueue(LinkQueue &Q,ElemType x){
  LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));   //申请新的结点的空间
  s->data=x;
  s->next=NULL;
  if(Q.front==NULL){    //空队列的第一个元素
    Q.front=s;          //膝盖队头队尾指针
    Q.rear=s;
  }
  else{
    Q.rear->next=s;       //新结点插入到rear后
    Q.rear=s;         //修改队尾指针
  }
}

3、链式队列出队

带头结点

bool DeQueue(LinkQueue &Q,ElemType &x){
  if(Q.front==Q.rear)
    return false;
  LinkNode *p=Q.front->next;
  x=p->data;              //用x返回队头元素
  Q.front->next=p->next;    //修改头结点的next指针
  if(Q.rear==p)         //此次是最后一个结点出队
    Q.rear=Q.front;     //修改rear指针
  free(p);            //释放结点空间
  return true;
}

不带头结点

bool DeQueue(LinkQueue &Q,ElemType &x){
  if(Q.front==NULL)
    return false;
  LinkNode *p=Q.front;      //p指向此次出队的结点
  x=p->data;
  Q.front=p->next;        //修改front指针
  if(Q.rear==p){
    Q.front=NULL;
    Q.rear=NULL
  }
  free(p);            //释放结点空间
  return true;
}

✍双端队列

允许从两端插入和删除的队列
分为三种：

输入输出两端都能进行
输入受限：一端插入，两端删除
输出受限：一端删除，两端插入

✍队列的应用

树的层次遍历：对于每一层，将当层的每个结点的子结点加入队尾，然后删去改层的结点，如此往复遍历树的每一层。树的概念将在后面的章节详细记录
图的广度优先遍历：类似树的层次遍历，都将在后续记录
操作系统：多进程抢占资源时，FCFS（先来先服务）是常用的策略，类似队列的先进先出原则。也可以应用在打印机的缓冲区存放打印请求队列