循环队列的顺序储存结构

文章目录

循环队列的顺序储存结构队列的基本定义队列的基本操作初始化队列求队列长度入队列操作出队列函数打印该队列 项目整体源代码：

队列的基本定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

线性表有顺序储存和链式储存，栈是线性表，所以也有这两种储存方式。同样，队列作为一种特殊的线性表，也同样存在这两种储存方式。但是队列的顺序储存结构是有许多不足的，比如假溢出，所以，我们一般使用循环队列来弥补这个不足。

循环队列：我们把队列这种头尾相接的顺序储存结构称为循环队列

循环队列中引入了两个指针，front和rear，front指向队头元素，rear指向队尾元素的下一个位置。这样当front等于rear时，此队列不是还剩一个元素，而是空队列。循环队列的好处就是不会产生假溢出现象，当rear指针到达数组尾部时，它可以改为指向下标为0的位置。

但是，还有一个问题，我们刚才说，空队列时，front等于rear，可是，仔细想想，队列满时，因为你的rear是指向队尾元素的后一个位置，所以，也是front等于rear，那么如何判断此时的队列是空还是满呢。

其实，我们可以保留一个元素空间，也就是说，队列满时，数组中还有一个空闲单元。这样front就不会等于rear了

队列的基本操作

初始化队列

int InitQueue(SqQueue *Q) //初始化队列 { Q->front = 0; Q->rear = 0; return 0; }

求队列长度

int Queue_Length(SqQueue *Q) //返回队列的长度 { return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; //通用的计算队列长度公式 }

通用的计算队列长度公式为(rear - front + MAXSIZE) % MAXSIZE

入队列操作

int EnQueue(SqQueue *Q, elemtype e) //入队操作 { if ((Q->rear + 1) % MAXSIZE == Q->front) //队列满的判断 { printf("队列已满！\n"); return 0; } Q->data[Q->rear] = e; //将元素e赋值给队尾 Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置，若到最后则转到数组头部 return 0; }

出队列函数

int DeQueue(SqQueue *Q, elemtype *e) //出队操作 { if (Q->front == Q->rear) //若队列为空，返回 { printf("队列为空！"); return 0; } *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; //front指针向后移一位置，若到最后则转到数组头部 return 0; }

打印该队列

void Show_Queue(SqQueue *Q) //打印出队列 { int i = Q->front; //保存原先头指针的位置 if (Q->front == Q->rear) { printf("当前队列为空！\n"); return; } printf("当前队列元素为:"); while ((Q->front) % MAXSIZE != Q->rear) //循环，依次打印队列元素 { if (Q->front == MAXSIZE) //如果头指针超过数组后，就从头开始 Q->front %= MAXSIZE; printf(" %d ", Q->data[Q->front]); Q->front++; } printf("\n"); Q->front = i; //将头指针回到原先位置 }

到此，队列顺序储存的基本操作就已经完成了，下面附上源码

项目整体源代码：

#include<stdio.h> #include<stdlib.h> #define MAXSIZE 5 typedef int elemtype; typedef struct { elemtype data[MAXSIZE]; int front; //头指针 int rear; //尾指针，若队列不为空，指向队尾元素的下一个位置 }SqQueue,*SSqQueue; int InitQueue(SqQueue *Q) //初始化队列 { Q->front = 0; Q->rear = 0; return 0; } int Queue_Length(SqQueue *Q) //返回队列的长度 { return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; //通用的计算队列长度公式 } int EnQueue(SqQueue *Q, elemtype e) //入队操作 { if ((Q->rear + 1) % MAXSIZE == Q->front) //队列满的判断 { printf("队列已满！\n"); return 0; } Q->data[Q->rear] = e; //将元素e赋值给队尾 Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置，若到最后则转到数组头部 return 0; } int DeQueue(SqQueue *Q, elemtype *e) //出队操作 { if (Q->front == Q->rear) //若队列为空，返回 { printf("队列为空！"); return 0; } *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; //front指针向后移一位置，若到最后则转到数组头部 return 0; } void Show_Queue(SqQueue *Q) //打印出队列 { int i = Q->front; //保存原先头指针的位置 if (Q->front == Q->rear) { printf("当前队列为空！\n"); return; } printf("当前队列元素为:"); while ((Q->front) % MAXSIZE != Q->rear) //循环，依次打印队列元素 { if (Q->front == MAXSIZE) //如果头指针超过数组后，就从头开始 Q->front %= MAXSIZE; printf(" %d ", Q->data[Q->front]); Q->front++; } printf("\n"); Q->front = i; //将头指针回到原先位置 } int main() { SqQueue Q; elemtype e; InitQueue(&Q); Show_Queue(&Q); printf("当前队列长度为：%d\n", Queue_Length(&Q)); EnQueue(&Q, 5); EnQueue(&Q, 3); EnQueue(&Q, 42); EnQueue(&Q, 78); Show_Queue(&Q); printf("当前队列长度为：%d\n", Queue_Length(&Q)); DeQueue(&Q, &e); printf("被删除的元素为%d\n",e); Show_Queue(&Q); DeQueue(&Q, &e); printf("被删除的元素为%d\n", e); Show_Queue(&Q); EnQueue(&Q, 13); Show_Queue(&Q); EnQueue(&Q, 32); Show_Queue(&Q); printf("当前队列长度为：%d\n", Queue_Length(&Q)); system("pause"); return 0; }