头文件
/* * my_queue.h * * Created on: Dec 3, 2018 * Author: lgh */#ifndef INCLUDE_MY_QUEUE_H_#define INCLUDE_MY_QUEUE_H_#include#include /* 队列: 只允许在表的一端(队尾rear)进行插入操作，而在另一端(队头front)进行删除操作的线性表 * 插入操作简称为入队 删除操作简称为出队 队列具有先进先出的特点 *//*=====队列的入队、出队示意图======== * * 出队 ----------------- 入队 * <--- a1,a2,a3,...,an <--- * ----------------- * *================================*/typedef enum{ OK=0, //正确 ERROR=1, //出错 TRUE=2, //为真 FALSE=3 //为假}status;typedef int ElemType; //宏定义队列的数据类型#define MAX_SIZE 20/*一、使用数组存储队列的称为静态顺序队列 *二、使用动态分配的指针的称为动态顺序队列*/// 【这里的是动态顺序队列】typedef struct{ ElemType *pBase; //数组指针 ElemType front; //队头索引 ElemType rear; //队尾索引 int maxSize; //当前分配的最大容量}queue;//创建空队列 queueCapacity-队列容量status initQueue(queue *PQueue,int queueCapacity);//销毁队列void destroyQueue(queue *PQueue);//清空队列void clearQueue(queue *PQueue);//判断队列是否为空status isEmpityQueue(queue *PQueue);//判断队列是否为满status isFullQueue(queue *PQueue);//获得队列长度int getQueueLen(queue *PQueue);//新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素status enQueue(queue *PQueue,ElemType element);//新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]status deQueue(queue *PQueue,ElemType *pElement);//遍历队列void queueTraverse(queue *PQueue);#endif /* INCLUDE_MY_QUEUE_H_ */
源文件
/* * my_queue.c * * Created on: Dec 3, 2018 * Author: lgh */#include "my_queue.h"/* 队列: 只允许在表的一端(队尾rear)进行插入操作，而在另一端(队头front)进行删除操作的线性表 * 插入操作简称为入队 删除操作简称为出队 队列具有先进先出的特点 *//*=====队列的入队、出队示意图======== * * 出队 ----------------- 入队 * <--- a1,a2,a3,...,an <--- * ----------------- * *================================*///创建队列 queueCapacity-队列容量status initQueue(queue *PQueue,int queueCapacity){ //给数组指针分配内存 PQueue->pBase = (ElemType *)malloc(sizeof(ElemType)*queueCapacity); if(!PQueue->pBase) { printf("给数组指针分配内存失败\n"); return ERROR; } PQueue->front = 0; //最开始创建时，队头索引为0 PQueue->rear = 0; //最开始创建时，队尾索引为0 PQueue->maxSize = queueCapacity; return OK;}//销毁队列void destroyQueue(queue *PQueue){ free(PQueue); //释放队列数组指针指向的内存 PQueue = NULL; //队列数组指针重新指向NULL,避免成为野指针}//清空队列void clearQueue(queue *PQueue){ PQueue->front = 0; //队头索引清0 PQueue->rear = 0; //队尾索引清0}//判断队列是否为空status isEmpityQueue(queue *PQueue){ if( PQueue->front == PQueue->rear ) //队头==队尾，说明为空 return TRUE; return FALSE;}/* *在循环队列中,“队满”和“队空”的条件有可能是相同的，都是front==rear， *这种情况下，无法区别是“队满”还是“队空”。 *针对这个问题，有3种可能的处理方法： *（1）另设一个标志以区别是“队满”还是“队空”。（即入队/出队前检查是否“队满”/“队空”） *（2）设一个计数器，此时甚至还可以省去一个指针。 *（3）少用一个元素空间，即约定队头指针在队尾指针的下一位置时就作为“队满”的标志， *即“队满”条件为：(PQueue->rear+1)%MAX_SIZE == PQueue->front。 * 【这里采用了第3种处理方法】 *///判断队列是否为满status isFullQueue(queue *PQueue){ if( (PQueue->rear+1)%PQueue->maxSize == PQueue->front ) //队列满 return TRUE; return FALSE;}//获得队列长度int getQueueLen(queue *PQueue){ //正常情况下，队列长度为队尾队头指针之差，但如果首尾指针跨容量最大值时，要% return (PQueue->rear - PQueue->front + PQueue->maxSize)%PQueue->maxSize;}//新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素status enQueue(queue *PQueue, ElemType element){ if(isFullQueue(PQueue)==TRUE) { printf("队列已满,不能再插入元素了!\n"); return FALSE; } //向队列中添加新元素 PQueue->pBase[PQueue->rear] = element; PQueue->rear = (PQueue->rear+1) % PQueue->maxSize; //将rear赋予新的合适的值 return TRUE;}//新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]status deQueue(queue *PQueue,ElemType *pElement){ //如果队列为空,则返回false if(isEmpityQueue(PQueue)==TRUE) { printf("队列为空，出队失败!\n"); return FALSE; } *pElement = PQueue->pBase[PQueue->front]; //先进先出 PQueue->front = (PQueue->front+1) % PQueue->maxSize; //移到下一位置 return TRUE;}//遍历队列void queueTraverse(queue *PQueue){ int i = PQueue->front; //从头开始遍历 printf("遍历队列：\n"); while(i != PQueue->rear) //如果没有到达rear位置，就循环 { printf("%d ", PQueue->pBase[i]); i = (i+1) % PQueue->maxSize; //移到下一位置 } printf("\n");}int main(){ //定义的指针必须分配动态内存空间； queue *pQueue=malloc(sizeof(queue)); if(OK!=initQueue(pQueue,50)) { printf("队列初始化失败.\n"); return -1; } queueTraverse(pQueue); //给队列赋值； int i; for(i=0;i<21;i++) { enQueue(pQueue,i); } queueTraverse(pQueue); //进列； enQueue(pQueue,10); queueTraverse(pQueue); //出列； ElemType *pElement=malloc(sizeof(ElemType)); deQueue(pQueue,pElement); queueTraverse(pQueue); //获取队列长度； int length=getQueueLen(pQueue); printf("length=%d\n",length); //销毁队列； destroyQueue(pQueue); free(pElement); return 0;} 结果：
遍历队列：遍历队列：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 遍历队列：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10 遍历队列：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10 length=21