线性表--顺序队列 循环队列 双端队列(十三)

1.介绍

1.顺序队列

1.队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 2.队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

在这里插入图片描述

与顺序栈相似，在队列的顺序存储结构种，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组。

在这里插入图片描述

由于队列中的队头和队尾的位置是实时变化的，需要两个指针来随时跟随头尾队列。当队列为空时，两个指针front，rear，指向一个位置，随着数据入队，两指针的位置图1，图2所示。

在这里插入图片描述

出队如图3。

2.循环队列

可以看出随着数据出队，数组前面的空间像静态链表一样被浪费，无法再利用，所以在顺序队列的基础上，使用顺序循环队列，为了方便理解，我们将数组首尾连起来，形成一个环，如下图所示：

在这里插入图片描述

在原来的头出队后，原来的位置可以被尾所利用，避免了内存浪费。我们只研究顺序循环队列，下面来看代码实现。

2.代码实现

1.定义队列

#define MAXSIZE 50
typedef struct
{
 char elem[MAXSIZE];
 int front;
 int rear;
}SeqQueue;

2.初始化队列

void InitQueue(SeqQueue * Q)
{
 Q->front = Q->rear = 0;
}

3.入队

int EnterQueue(SeqQueue * Q, char x)
{
 if ((Q->rear + 1) % MAXSIZE == Q->front)
 //可以看，这种取模法会导致最后一个空间被浪费，当rear等于49时就认为队列已满。另一种方法是增加标记量。
 {
  return(false);
 }
 Q->elem[Q->rear] = x;
 Q->rear = (Q->rear + 1) % MAXSIZE;
 return(true);
}

有些人可能要问为什么要进行取模这样的算法，我来说一下: 上面定义的数组为50个单位，如果rear指针指向49，继续有数据入队，当rear指针+1变为49+1等于50，因为数组下标最大只有49，会造成数组越界并假溢出，此时便不应该是（rear）49继续加1，而是应该将rear重置为0，才可解决问题，所以不采取取膜算法也是可以的，就是将最大的长度重置为0，而其他数和取不取模最后的结果是一样的，只是为了方便，一遍会采取取膜，（49+1）%=0，这种方法会使数组下角标到达最大长度自动置0，省去我们多写一步置0。

4.出队

int DeleteQueue(SeqQueue * Q, char *x)
{
 if (Q->front == Q->rear)return(false);
 *x = Q->elem[Q->front];
 Q->front = (Q->front + 1) % MAXSIZE;
 return (true);
}

3.双端队列

在这里插入图片描述

除了栈和队列，还有一种限定性数据结构是双端队列，双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。这种双端队列看起来比栈和队列更灵活，但是实际应用中远不及栈和队列常用，就不在讨论。

若有错误，欢迎指正批评，欢迎讨论。 每文一句：人生短短几十年，不要给自己留下了什么遗憾，想笑就笑，想哭就哭，该爱的时候就去爱，无谓压抑自己。