队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，在表的后端进行插入操作。插入操作的端称为队尾，删除操作的端为对头。
队列核心是先进先出。
队列又可因为存储方式不同分为顺序存储和链式存储。今天就先讲一下顺序存储结构——循环队列。
建立循环队列结构，必须为其静态或者动态申请一片连续的存储空间，并且设置两个指针管理，一个是队头指针front，指向对头元素。另外一个是队尾指针rear，指向下一个入队元素的存储位置。如图所示
image.png
当front=rear的时候，队列没有任何元素，称为空队列。
当每次在队尾插入一个元素，rear+1；当在队头删除一个元素时，front+1；队头和队尾都是可以变化的，但当rear指向分配的连续空间之外，队列就没有办法插入新元素，但是此时队头前面的空间还未被占用。这就是假溢出现象。
为了防止假溢出现象，用循环队列。即当rear+1或者front+1时超出所分配的队列空间，就让其指向这片连续空间的起始位置。如图所示
循环队列.png
但是如果队头和队尾还是指向同一个存储单元，无法判断是空还是满，所以牺牲一个存储单元，使其为空。如图所示
image.png
循环队列中头尾指针与元素之间的关系
image.png
1、判断对空：Q.front == Q.rear;
2、判断队满：(Q.rear + 1) % MAXSIZE == Q.front
有了以上思路，下面就设计代码：
首先呢，
1.创建数据结构
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
//队列的顺序结构
typedef struct {
QElemType *data;
int front;
int rear;
}SqQueue;
2.初始化
Status InitSqQueue(SqQueue *Q){
Q->data = malloc(sizeof(SqQueue)*MAXSIZE);
Q->front = 0;
Q->rear = 0;
return OK;
}
3.将队列清空
Status ClearSqQueue(SqQueue *Q){
//将队头和队尾指向同一存储单位
Q->front =Q->rear= 0;
return OK;
}
- 若队列Q为空队列,则返回TRUE,否则返回FALSE
Status EmptySqQueue(SqQueue Q){
if (Q.front==Q.rear) {
return TRUE;
}else{
return FALSE;
}
}
- 返回Q的元素个数,也就是队列的当前长度
Status LengthSqQueue(SqQueue Q){
if (Q.front== 0 && Q.rear ==0) {
//空队列
return 0;
}else{
return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
}
6 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR
Status HeadSqQueue(SqQueue Q,int *e){
if (Q.front == Q.rear) {
return ERROR;
}else{
*e = Q.data[Q.front];
}
return OK;
}
- 若队列未满,则插入元素e为新队尾元素
Status InsertSqQueue(SqQueue *Q,int e){
//队列已满
if ((Q->rear+1)%MAXSIZE == Q->front) {
return ERROR;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return OK;
}
- 若队列不空,则删除Q中队头的元素,用e返回值
Status DeleteSqQueue(SqQueue *Q,QElemType *e){
//队列为空，返回
if (Q->front == Q->rear) {
return ERROR;
}
*e = Q->data[Q->front];
Q->front = (Q->front +1)%MAXSIZE;
return OK;
}
- 从队头到队尾依次对队列的每个元素数组遍历
Status TraverseSqQueue(SqQueue Q){
//队列为空，返回
if (Q.front == Q.rear) {
return ERROR;
}
int i = Q.front;
while (i!= Q.rear) {
printf("%d ",Q.data[i]);
i++;
}
printf("\n");
return OK;
}
网友评论