循环队列-队列的顺序表示和实现循环队列的三种状态循环队列-队列的顺序实现 （代码演示）CycleQueue.hCycleQueue.cppmain.cpp测试结果
循环队列-队列的顺序表示和实现
是限制仅在表头删除和表尾插入的顺序表。
利用一组地址连续的存储单元依次存放队列中的数据元素。
因为：队头和队尾的位置是变化的，所以：设头、尾指针。
在顺序队列中，当尾指针已经指向了队列的最后一个位置的下一位置时，若再有元素入队，就会发生“溢出”。
“假溢出”——队列的存储空间未满，却发生了溢出。
解决“假溢出”的问题有两种可行的方法：
(1)、平移元素：把元素平移到队列的首部。效率低。 (2)、将新元素插入到第一个位置上，构成循环队列， 入队和出队仍按“先进先出”的原则进行。操作效率、空间利用率高。
循环队列的三种状态
解决办法： (1)、另设一个布尔变量以区别队列的空和满(使用一个计数器记录队列中元素的总数。)；
(2)、少用一个元素的空间，约定入队前测试尾指针在循环意义下加 1 后是否等于头指针，若相等则认为队满；
循环队列-队列的顺序实现 （代码演示）
CycleQueue.h
#pragma once#define MAXQSIZE 100 //最大队列长度 typedef int QElemType;//定义数据类型typedef struct {QElemType* base; // 预分配存储空间基址 int front; // 头指针，若队列不空， // 指向队列头元素 int rear; // 尾指针，若队列不空， // 指向队列尾元素 的下一个位置 } SqQueue;void InitCycleQueue(SqQueue* Q);//初始化循环队列void DestroyCycleQueue(SqQueue* Q); //销毁循环队列int LengthCycleQueue(SqQueue Q); //求循环队列的长度bool InputCycleQueue(SqQueue* Q, QElemType val); //入循环队列bool OutputCycleQueue(SqQueue* Q, QElemType * val); //出循环队列void Show(SqQueue Q); //打印循环队列的元素
CycleQueue.cpp
#include "CycleQueue.h"#include <malloc.h>#include <stdlib.h>#include <stdio.h>void InitCycleQueue(SqQueue* Q){Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));if (!Q->base){printf("InitQueue file\n");exit(-1);}Q->front = Q->rear = 0;}void DestroyCycleQueue(SqQueue* Q) //销毁循环队列{free(Q->base);}int LengthCycleQueue(SqQueue Q) //求循环队列的长度{return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;}bool InputCycleQueue(SqQueue* Q, QElemType val)//入循环队列{if ((Q->rear + 1) % MAXQSIZE == Q->front)return false;Q->base[Q->rear] = val;Q->rear = (Q->rear + 1) % MAXQSIZE;return true;}bool OutputCycleQueue(SqQueue* Q, QElemType* val) //出循环队列{if(Q->rear == Q->front)return false;*val = Q->base[Q->front];Q->front = (Q->front + 1) % MAXQSIZE;return true;}void Show(SqQueue Q)//打印循环队列的元素{while (Q.front % MAXQSIZE != Q.rear)printf("%d\t", Q.base[Q.front++]);printf("\n");}
main.cpp
#include "CycleQueue.h"#include <stdio.h>int main(){SqQueue Q;InitCycleQueue(&Q);printf("入循环队列:\n");for (int i = 0; i < 10; i++)InputCycleQueue(&Q, i * 11);Show(Q);QElemType tmp;printf("出循环队列:\n");OutputCycleQueue(&Q, &tmp);Show(Q);printf("出循环队列:\n");OutputCycleQueue(&Q, &tmp);Show(Q);printf("循环队列长度为%d\n", LengthCycleQueue(Q));DestroyCycleQueue(&Q);return 0;}
