循环队列实现
1.思路1.1循环队列入队伪算法1.2 循环队列出队伪算法1.3 如何判断循环队列是否为空1.4 如何判断循环队列是否为满2.头文件3.源文件4.测试文件5.测试结果1.思路
1.1循环队列入队伪算法
（1）把值存在rear所在的位置；（2）rear=（rear+1）%maxsize ，其中maxsize代表数组的长度；
1.2 循环队列出队伪算法
（1）先保存出队的值；（2）front=（front+1）%maxsize ，其中maxsize代表数组的长度；
1.3 如何判断循环队列是否为空
if（front==rear）队列空；else队列不空；
1.4 如何判断循环队列是否为满
少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满；
2.头文件
#ifndef __CIRCULARQUE_H__#define __CIRCULARQUE_H__#include <stdbool.h>#define MAXSIZE (5) //最大队列容量长度+1typedef int ElemType;typedef struct queue{ElemType *pBase;ElemType front; //指向队列第一个元素ElemType rear; //指向队列最后一个元素的下一个元素ElemType maxsize; //循环队列的最大存储空间} QUEUE, *PQUEUE;void InitQueue(PQUEUE Q, ElemType maxsize);void TraverseQueue(PQUEUE Q);bool FullQueue(PQUEUE Q);bool EmptyQueue(PQUEUE Q);bool PushQueue(PQUEUE Q, ElemType val);bool PopQueue(PQUEUE Q, ElemType *val);ElemType QueueLength(PQUEUE Q);ElemType QueueFreeLength(PQUEUE Q);#endif // !__CIRCULARQUE_H__
3.源文件
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdbool.h>#include "circularQue.h"/*** @brief Create a empty Queue object** @param Q* @param maxsize*/void InitQueue(PQUEUE Q, ElemType maxsize){Q->pBase = (ElemType *)malloc(maxsize * sizeof(ElemType));if (!Q->pBase){printf("Memory allocation failure");exit(-1);}Q->front = 0; Q->rear = 0;Q->maxsize = maxsize;memset(Q->pBase, 0, Q->maxsize);}/*** @brief 遍历队列元素* * @param Q */void TraverseQueue(PQUEUE Q){ElemType i = Q->front;printf("队中的元素是:\n");while (i % Q->maxsize != Q->rear){printf("%d ", Q->pBase[i]);i ++;}printf("\n");}/*** @brief 判断队列满* * @param Q * @return true * @return false */bool FullQueue(PQUEUE Q){if (Q->front == (Q->rear + 1) % Q->maxsize) //判断循环链表是否满，留一个预留空间不用{printf("Full Queue\r\n");return true;} elsereturn false;}/*** @brief 判断队列为空* * @param Q * @return true * @return false */bool EmptyQueue(PQUEUE Q){if (Q->front == Q->rear) //判断是否为空return true;elsereturn false;}/*** @brief 插入元素val为Q的新的队尾元素* * @param Q * @param val * @return true * @return false */bool Pushqueue(PQUEUE Q, ElemType val){if (FullQueue(Q)){return false;}else{Q->pBase[Q->rear] = val;Q->rear = (Q->rear + 1) % Q->maxsize;return true;}}/*** @brief 若队列不空，则删除Q的队头元素，用val返回其值，并返回OK；否则返回ERROR * * @param Q * @param val * @return true * @return false */bool PopQueue(PQUEUE Q, ElemType *val){if (EmptyQueue(Q)){return false;}else{*val = Q->pBase[Q->front];Q->front = (Q->front + 1) % Q->maxsize;return true;}}/*** @brief 销毁队列Q，Q不再存在* * @param Q */void DestroyQueue(PQUEUE Q){if (Q->pBase)free(Q->pBase);Q->pBase = NULL;Q->front = Q->rear = 0;Q->maxsize = 0;}/*** @brief 将Q清为空队列* * @param Q */void ClearQueue(PQUEUE Q){Q->front = Q->rear = 0;memset(Q->pBase, 0, Q->maxsize);}/*** @brief 返回Q中当前的元素个数，即队列的长度* * @param Q * @return ElemType */ElemType QueueLength(PQUEUE Q){//printf("Q->rear:%d, Q->front:%d\r\n",Q->rear,Q->front);return (Q->rear - Q->front + Q->maxsize) % Q->maxsize;}/*** @brief 返回Q中还剩余的空间长度* * @param Q * @return ElemType */ElemType QueueFreeLength(PQUEUE Q){return (Q->maxsize -1) - QueueLength(Q); //会浪费一个空间}/*** @brief 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR* * @param Q * @param e * @return Status */bool GetHead(PQUEUE Q,ElemType *e){if (EmptyQueue(Q)){return false;}*e = Q->pBase[Q->front];printf("GetHead:%d\r\n",*e);return true;}
4.测试文件
void test(void){ElemType headValue = 0;ElemType popValue = 0;ElemType queueLen = 0;ElemType freeQueueLen = 0;QUEUE *queue = ( QUEUE *)malloc(sizeof(QUEUE));InitQueue(queue,MAXSIZE);Pushqueue(queue,1);Pushqueue(queue,2);Pushqueue(queue,3);Pushqueue(queue,4);freeQueueLen = QueueFreeLength(queue);printf("freeQueueLen:%d\r\n",freeQueueLen);Pushqueue(queue,5);TraverseQueue(queue);queueLen = QueueLength(queue);printf("queueLen:%d\r\n",queueLen);GetHead(queue,&headValue);PopQueue(queue,&popValue);printf("popValue:%d\r\n",popValue);TraverseQueue(queue);queueLen = QueueLength(queue);printf("queueLen:%d\r\n",queueLen);}int main(void){test();system("pause");return 0;}
