王道3.2 队列

一、队列的基本概念

1. 队列是只允许在一端进行插入，在另一端删除的线性表
2. 先进先出原则
3. 术语

• 队头：允许删除的一端
• 队尾：允许插入的一端
• 空队列：不含任何元素的空表

二、队列的顺序存储结构

（一） 基础队列

1. 队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：front指向队头，rear指向队尾的下一个位置
2. 队列的顺序存储类型可以描述为：

using namespace std;
#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];
  int front rear;
}SqQueue;
void testQueue(){
    SqQueue Q;
}
1
2
3
4
5
6
7
8
9

4. 初始化操作

void InitQueue(SqQueue &Q){
   //初始化时，队头队尾指针指向0
   Q.rear= Q.front=0;
}
1
2
3
4

5. 判断是否为空
   判断条件Q.rear==Q.front

//判读为空
bool QueueEmpty(SqQueue Q){
  if (Q.rear==Q.front)
  return true;
  else return false;
}
1
2
3
4
5
6

6. 入队操作
   队不满时，先将值送到队尾元素，再将队尾元素加1

//入队操作
bool EnQueue(SqQueue &Q,ElemTypr x){
  if (Q.rear==MaxSize)//判断队列是否已满
    return false;
  Q.data[Q.rear]=x;//将x插入队尾
  Q.rear=Q.rear+1;//改变队尾指针的位置
}
1
2
3
4
5
6
7

7. 出队操作
   队不空时，先取队头元素值，再让队头指针加一
8. 缺陷
   入队操作出现问题，如果队满条件设置为：Q.rear==MaxSize，那么就会出现“上溢出”
   如图所示 ，最后一个rear=maxsize但是队列是空的，上溢出背后其实是假溢出
   为了解决这一问题，提出了循环队列

（二） 循环队列

1. 逻辑上视为一个环，称为循环队列
2. 一些判断设定：

• 初始化：Q.rear= Q.front=0;
• 队首指针进1：Q.frontr=(Q.front+1)%MaxSize;//改变队首指针的位置
• 对队尾进行操作：Q.rear=(Q.rear+1)%MaxSize;//改变队尾指针的位置

3. 一些基础操作
   （1） 初始化、判空一样
   （2）入队出队需要讨论判断条件
4. 循环队列的入队操作判断队满的三种方式
   （1）判断是否队满：(Q.rear+1)%MaxSize==Q.front
   牺牲一个单元，实现Q.rear= Q.front时队空以及队满的区别
   

对队尾进行操作：Q.rear=(Q.rear+1)%MaxSize;//改变队尾指针的位置

bool EnQueue(SqQueue &Q,ElemTypr x){
  if ((Q.rear+1)%MaxSize==Q.front)//判断队列是否已满
    return false;
  Q.data[Q.rear]=x;//将x插入队尾
  Q.rear=(Q.rear+1)%MaxSize;//改变队尾指针的位置
}
1
2
3
4
5
6

（2） 类型中增设表示元素个数的数据成员，这样，队空就是Q.size==0
队满就是Q.size$==$maxsize

• 初始化时：rear=front=0；size=0；
• 队空条件 ：size = 0
• 队满条件：size = maxsize

(3) 类型中增设tag数据成员，tag=0时，就说嘛是因为删除导致的Q.rear= Q.front，则表示队空；tag=1时，就说嘛是因为插入导致的Q.rear= Q.front，则表示队满

• 初始化条件：rear=front=0；tag=0；
• 队空条件 ：tag=0&&front$==$rear
• 队满条件：tag=1&&front$==$rear

5. 出队操作

bool DeQueue(SqQueue &Q,ElemTypr x){
  if (Q.rear==Q.front)//判断队列是否为空
    return false;
  Q.data[Q.front]=x;//将x插入队尾
  Q.front=(Q.front+1)%MaxSize;//改变队尾指针的位置
}
1
2
3
4
5
6

6. 出题方向
   初始时，队尾指针指向下一个元素还是当前元素时操作的区别

三、队列链式实现

1. 链式描述