考研数据结构——(队列)

队列

• 一、 顺序结构实现队列
• • 1.1 队列的结构体、初始化、判空
  • 1.2 入队操作
  • • 1.2.1 循环队列牺牲一个位置
    • 1.2.2 循坏队列不牺牲位置
  • 1.3 出队操作与获取队头元素
  • 1.4 队列的rear指向 队尾元素时， 各种条件整理！
  • • 1.4.1 牺牲一个元素位置的情况
    • 1.4.2 不牺牲一个元素的判断
  • 1.5 顺序结构思维导图
• 二、 链式结构实现队列
• • 2.1 链式队列的实现
  • 2.2 初始化链式队列
  • • 2.2.1 带头结点版本
    • 2.2.2 不带头结点的
  • 2.3 入队操作
  • • 2.3.1 带头结点的入队操作
    • 2.3.2 不带头结点的入队操作
  • 2.4 出队操作
  • • 2.4.1 带头结点的出队操作
    • 2.4.2 不带头结点的出队操作
  • 2.5 链式队列是否存在队满情况？
  • 2.6 链式队列知识框架
• 三、双端队列
• • 3.1 双端队列的介绍
  • • 3.1.1 限制只在一侧操作
    • 3.1.2 输入受限或者输出受限的双端队列
  • 3.2 判断输出序列合法性
  • • 3.2.1 判断栈的输出序列合法性（卡特兰数）
    • 3.2.2 判断输入受限的双端队列的合法性（容易考选择题）
    • 3.2.3 判断输出受限的双端队列
  • 3.3 双端队列个人理解⭐

一、 顺序结构实现队列

（本文 涉及到的判断条件 基于默认 rear指向队尾元素的下一个）
如果是 rear指向队尾元素的话，特别注释了！

1.1 队列的结构体、初始化、判空

• 队列的结构体， front队头和队尾
• 初始化就是将队头和队尾都设置为 0
• 判断队列空的条件是 队列的头和尾 相等即： front == rear

1.2 入队操作

• 先检查队列是否为满， 非循环队列的话如果一直没出过栈，队尾指针rear==最大长度就是满了，但是如果队头出过队了，这个条件就不成立，因此一般使用循环队列。

1.2.1 循环队列牺牲一个位置

⭐ 循环队列牺牲一个元素位置用来区别队满（front == (rear + 1)%MaxSize）与队空（front==rear）。

• 当队满时，指的是队尾指针的下一个就是队头： (rear+1) % MaxSize == front

1.2.2 循坏队列不牺牲位置

1. 方案一： 设置size记录队长

设置size用于记录队列的长长度

• 初始化时: 将 front rear size都设置为 0；
• 入队时：将size++；
• 出队时：将size–
• 判断队空时： size == 0
• 判断队满时： size==MaxSize

2. 方案二： 设置tag表示最近一次操作是入队还是出队

我们指定tag=1表示 最近一次操作为入队， tag = 0 表示最近一次操作为出队。初始时我们指定 tag为0； 当rear = front的时候 如果时 tag为1表示 入队导致 队头队尾位置相同即是队满，如果tag为0表示 出队导致队头队尾位置相同即是队空。

• 初始化时： rear = front = tag = 0；
• 入队时： 设置 tag = 1；
• 出队时： 设置tag = 0；
• 判断队满： rear == front && tag ==1
• 判断队空： rear == front && tag ==0

1.3 出队操作与获取队头元素

• 出队操作与取得队友元素的唯一区别就是， 出队在读取完队头后，自己要移动位置(自增一)
• 首先判断 队列是否为空： rear == front
• 取除队头后，队头像队尾移动。移动条件： front = (front + 1) % MaxSize

1.4 队列的rear指向 队尾元素时， 各种条件整理！

• 初始化时： front指向0， rear指向 MaxSize-1；
• 入队时： 先自增再赋值 rear = (rear + 1) % MaxSize 再 data[rear] = x；

1.4.1 牺牲一个元素位置的情况

• 判断队满 : (rear + 2) % MaxSize == front
• 判断队空: (rear + 1) % MaxSize == front

1.4.2 不牺牲一个元素的判断

1. 添加一个size记录队长siz

• 初始化： size=0 front = 1 rear = MaxSize -1；
• 进队：先自增再赋值： rear = (rear + 1) % MaxSize ; data[rear] = x； size++；
• 出队：先获取值再自减： x = data[rear] ； rear = (rear - 1) % MaxSize ; size–；
• 判断空： size ==0；
• 判断满： size == MaxSize

2. 添加一个表示 tar（1：表示最近一次操作为入队；0表示最近一次操作为出队）

• 初始化 ：front = 0； rear = MaxSize-1； tar = 0； （因为tag==0 也可以表示为出队导致的队空也可以表示初始为空）
• 进队：先自增再赋值： rear = (rear + 1) % MaxSize ; data[rear] = x； tar=1；
• 出队：先获取值再自减： x = data[rear] ； rear = (rear - 1) % MaxSize ; tar=0；
• 判断空： rear == front && tar ==0； (指的是出队导致的队头队尾重合，队空)
• 判断满： rear == front && tar ==1； （指的是入队导致的队头队尾重合，队满）

1.5 顺序结构思维导图

二、 链式结构实现队列 2.1 链式队列的实现

• LinkQueue指的是队列
• LinkNode是队列中的结点

2.2 初始化链式队列 2.2.1 带头结点版本

• 开辟空间，并将开辟空间的地址赋值给 front与rear，也就是让队头队尾都指向这个空间
• 让front指向null（front->next == NULL）表示队列为空， 当然 front==rear也表示队列为空
• ⭐ 个人理解： front指针就类似于头指针，而front->next就是指向的队列的第一个元素！

2.2.2 不带头结点的

• 初始化的时候直接让 rear与front指向 null即可。
• 当frontnull 或者 frontrear的时候表示 链式队列为空

2.3 入队操作 2.3.1 带头结点的入队操作

• 首先要开创一个新的结点空间，并为它赋值；
• 要将新的结点的next指向为 null；
• 队尾标志rear下一个为新结点： Q.rear->next = s； （白话意思就是将新元素添加到最后一个元素后面）
• 队尾标志后移 Q.rear = s;

2.3.2 不带头结点的入队操作

• 开始依旧是 初始一个新元素空间 1.赋值 2.新元素指向null；
• ⭐ 不带头结点的要注意第一次插入操作时， 要将Q.front与Q.rear都指向 第一个元素！！！（这是带头结点和不带头结点的区别）；判断的条件是: Q.front==NULL 或者 Q.front == Q.rear；
• 不是第一个元素的话， Q.rear->next = s； （也就是将最后一个元素指向 新元素位置）
• Q.rear = s； （也就是标识最后一个元素为队尾）;

2.4 出队操作 2.4.1 带头结点的出队操作

• 首先判断是否队空： Q.rear == Q.front
• 使用临时变量 p 接收 暂存队头结点： p = Q.front->next；
• ⭐ 判断是不是最后一个元素, 如果是最后一个元素，应当让Q.rear指向和Q.front一致:

1. 判断 Q.rear = p (因为p = Q.front->next)；
2. 让队尾和队头指向一致： Q.rear = Q.front；

• 最后free掉结点就行；

2.4.2 不带头结点的出队操作

• 判断队空： Q.front == NULL;
• p临时是存储队头结点： p=Q.front；
• 获取队头元素： x = p->data；
• 队头后移： Q.front = p->next;
  -⭐ 关键一步判断是否为最后一个元素：如果是将 队头队尾指向都设置为NULL： Q.rear = NULL;Q.front = NULL；
• 释放p即可；

2.5 链式队列是否存在队满情况？

jzq回答： 不会，除非内存满了！

2.6 链式队列知识框架

三、双端队列 3.1 双端队列的介绍

• 栈： 只能在一端（栈顶）进行插入删除的线性表
• 队列： 只能在一端（队尾）进行插入，另一端（队头）进行删除的线性表；
• 双端队列： 只允许从两端进行插入以及删除的线性表；

3.1.1 限制只在一侧操作

• 如果限制双端队列只能在一侧进行插入删除，就是栈的功能了。

3.1.2 输入受限或者输出受限的双端队列

3.2 判断输出序列合法性 3.2.1 判断栈的输出序列合法性（卡特兰数）

3.2.2 判断输入受限的双端队列的合法性（容易考选择题）

3.2.3 判断输出受限的双端队列

3.3 双端队列个人理解⭐

1. 输入受限的双端队列， 即两端可输出，只有一端（队尾）可以输入！

这种的个人理解就是 队列的入队方式， 队列＋栈的出队（栈）方式。

• 因此，如果入队顺序为 1 2 3 4 则只有这一种顺序入
• 而出队（栈）

1. 队列的出队： 4 3 2 1
2. 栈的出队： (n + 1 ) C n-2n

2. 输出受限的双端队列， 即双端可入队， 只有一端（队头）可出！

个人理解 入队（栈）顺序为 1 2 3 4

• 入队 其实 有很多顺序 1 2 3 4 | 2 1 3 4 ⭐ 2 1 4 3这种不可能出现
• 出队就按入队的顺序出，那就是由入队决定的

⭐ 因此在讨论 受限制的双端队列的时候：

• 如果是入队受限（只有一个入的序列），则应该考虑各种出队情况是否符合!
• 如果是出队受限（即，出序由入序所决定），则应该考虑各种入的方式能不能组成符合的情况！