一、队列的定义
队列( queue )是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。如图所示：
二、循环队列的引出
为了避免当队中只剩一个元素的时候，队头队尾重合使处理变得麻烦。所以我们引入两个指针，front指针指向队头元素，rear指针指向队尾元素。这样当front=rear时，队列中不是只剩一个元素，而是它是一个空队列。而且这样也大大方便了我们删除队头元素。这样就当我们删除队头元素时就只需要移动front指针，这样可以大大降低算法的时间复杂度。
但是当删除元素的时候，front不断后移，前面的位置不断空出来。插入元素时rear指针 b不断后移。对于一个有限的队列来说，在不断得插入元素时rear最终会指向一个无效位置。具体情况如下图所示：
删除元素时：
插入元素时：
用循环队列可以巧妙得解决这个问题。
三、循环队列
1、循环队列的定义
**我们把队列的这种头尾相接的顺序存储结构称为循环队列。**如下图所示：
循环队列满时：
循环队列空时：
判断循环队列空的条件是：
front == rear;
判断循环队列满的条件是：
(rear+1)%6==front
为了区别判空和判满的状态，我们总在插入元素时牺牲一个空间来区别这两种状态，这也是为啥判满的时候是(rear+1)%6==front
2、循环队列的简单实现
（1）循环队列的整体结构的设计
typedef int ElemType;
#define MAX_SIZE 10
typedef structc Queue
{
ElemType arr[MAX_SIZE];
int front;//队头指针
int rear;//队尾指针
};Queue,pQueue2、初始化(init)
初始化的时候我们只需要将我们的头指针和尾指针置成0即可。
void init(pQueue pqu)
{
if(pqu != NULL)
{
pqu->front = pqu->rear = 0;
}
} 3、入队操作(enqueue)
在进行入队操作之前我们首先应该对队列进行判满的操作。如果队列是满的，我们就插入不了元素。如果队列不满我们就可以进行我们的入队操作。
判满
int full(pQueue pqu)
{
return (pqu->rear + 1)%MAX_SIZE == front ? 1 : 0;
}插入元素
插入元素时，我们只需要将这个队列中的rear指针的下标置成我们要插入的元素即可。
int enqueue(pQueue pqu,ElemType val)
{
if(full(pqu))
{
return 0;
}
pqu->arr[pqu->rear] = val;
pqu->rear = (pqu->rear + 1)%MAX_SIZE;
return 1;
}4、出队操作(dequeue)
在进行出队操作时，我们首先要判断的是队列是否为空。若队列中的元素为空，则就无法进行出队的操作。
判空
int empty(pQueue pqu)
{
return (pqu->rear == pqu->front) ? 1 : 0;
}出队操作
int dequeue(Pqueue pqu)//只是删除元素
{
if(empty(pqu))
{
return 0;
}
pqu->front = (pqu->front + 1) % MAX_SIZE;
return 1;
}5、获取队头元素(front)
int front(pQueue pqu)
{
if(empty(pqu))
{
return -1;//牺牲一个数值位
}
return pqu->arr[pqu->front];
}6、获取队尾元素(back)
int back(pQueue pqu)
{
if(empty(pqu))
{
return -1;//队列为NULL
}
return pqu->arr[(pqu->rear + MAX_SIZE - 1)%MAX_SIZE];
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/hz/115264.html