队列本质也是受限制的线性结构只能在一端进行插入另一端进行删除的一种数据结构被称为 FIFO(先进先出)同样先来认识一些重要名词队头 front取出元素一端队尾 rear新增元素一端入队 (enqueue)队尾添加元素出队 (dequeue)队头删除元素队空无元素队满顺序队列容量耗尽队列的分类一非循环队列1.顺序队列用数组顺序表实现的非循环队列2.链式队列使用单链表模拟实现一个非循环队列二循环队列1.循环顺序队列用数组顺序表实现的循环队列2.循环链式队列使用单链表模拟实现一个循环队列———————————————————————————————————————————一.顺序队列的操作实现0.定义结构体typedef int ElemType; #define STACKINISIZE 10//初始容量 #define STACKINCREMENT 2//每次扩容的倍数 typedef struct SeqQueue { ElemType* front;//队头指针 ElemType* rear;//队尾指针 size_t queuesize;//当前容量 }SeqQueue, * PSeqQueue;1.初始化void InitSeqQueue(PSeqQueue pq) { assert(pq!NULL); //开辟空间初始容量为STACKINISIZE ElemType* p(ElemType*)malloc(sizeof(ElemType)*STACKINISIZE); if(pNULL){ printf(malloc申请空间失败); return; } pq-frontpq-rearp; //头尾指针指向空间开始位置 pq-queuesizeSTACKINISIZE; }2..判空bool IeEmpty(const PSeqQueue pq){ assert(pq!NULL); return pq-frontpq-rear; }3.判满bool IsFull(PSeqQueue pq){ assert(pq!NULL); return (pq-rear-pq-front)pq-queuesize; }4.获取队列元素个数int GetSize(const PSeqQueue pq){ assert(pq!NULL); return (pq-rear-pq-front); }5.入队队尾入队//扩容函数 bool IncMem(PSeqQueue pq) {//这里实现一下不使用malloc进行扩容的方法 assert(pq!NULL); int newsizepq-queuesize*STACKINCREMENT;//新容量为旧容量*扩容倍数 //1.使用malloc申请大小为新容量的新空间 ELemType* p(ELemType*)malloc(sizeof(ELemType)*newsize); if(pNULL){ printf(申请新空间失败); return false; } //2.使用memmove手动复制所有元素 memmove(p,pq-front,(pq-rear-pq-front)*sizeof(ElemType)); //3.释放原空间设置头尾指针和新容量 free(pq-front); pq-frontp; pq-rearpq-frontpq-queuesize; pq-queuesizenewsize; return true; } //入队 bool Push(PSeqQueue pq,ElemType val) { assert(pq ! NULL); if(IsFull(pq)){ if(IncMem(pq)false){ return false; } } //队尾插入新元素队尾指针向后移动 *pq-rearval; pq-rear; return true; }6.出队队头出队bool Pop(PSeqQueue pq,ElemType* pval){ assert(pq!NULL); if(IsEmpty(pq)){ printf(队列为空); return falsel } *pvalpq-front;//保存队头元素 //使用memmove覆盖队头元素 memmove(pq-front1,pq-front,(pq-rear-pq-front-1)*sizeof(ElemType)); //队尾指针向前移动 pq-rear--; return true; }7.打印void PrintQueue(const PSeqQueue pq){ assert(pq!NULL); //队头到队尾不包括队尾指针的值 for(ElemType* ppq-front;p!p-rear;p){ printf(%d ,*p); } printf(\n); }8.获取队头元素bool GetFront(const PSeqQueue pq, ElemType* val) { assert(pq ! NULL); if (IsEmpty(pq))return false; *val *pq-front; return true; }9.获取队尾元素bool GetBack(const PSeqQueue pq, ElemType* val) { assert(pq ! NULL); if (IsEmpty(pq))return false; *val *pq-rear; return true; }10.清空队列void ClearQueue(PSeqQueue pq){ assert(pq!NULL); if(IsEmpty(pq))return; pq-rearpq-front; }11.销毁队列void DestroyQueue(PSeqQueue pq){ assert(pq!NULL); ClearQueue(pq);//调用清空函数清空元素 free(pq-front); pq-frontpq-rearNULL; pq-queuesize0; }———————————————————————————————————————————二.链式队列(有头节点)的操作实现0.定义结构体typedef char ElemType; typedef struct QueueNode {//链表的节点 ElemType val;//链表节点的数据域 struct QueueNode* next;//链表节点的指针域 }QueueNode, * PQueueNode; typedef struct LinkQueue {//管理链表节点的结构体(用于模拟实现队列) PQueueNode front;//队头指针 PQueueNode rear;//队尾指针 size_t queuesize;//当前节点个数 }LinkQueue,* PLinkQueue;1.初始化//创建节点后续也会用到 PQueueNode BuyNode(ElemType val) { PQueueNode p(PQueueNode)malloc(sizeof(QueueNode)); if(pNULL)return NULL; p-valval; p-nextNULL; return p; } void InitLinkQueue(PLinkQueue pq) { assert(pq!NULL); PQueueNode pBuyNode(0); if(pNULL){ printf(头节点申请失败); return; } pq-frontpq-rearp; pq-queuesize0; }2.判空bool IsEmpty(const PLinkQueue pq){ assert(pq!NULL); return pq-frontpq-rear; }3.队中元素个数size_t GetSize(const PLinkQueue pq){ assert(pq!NULL); return pq-queuesize; }4.入队尾插入队bool Push(PLinkQueue pq, ElemType val) { assert(pq!NULL); //1.创建新节点 PQueueNode pBuyNode(val); if(pNULL)return false; //2.尾插新节点 p-nextpq-rear-next; pq-rear-nextp; //3.修改尾指针 pq-rearp; //元素个数1 pq-queuesize; return true; }5.出队头删出队并获取头部节点值bool Pop(PLinkQueue pq, ElemType* pval) { assert(pq!NULL); if(IsEmpty(pq)){ printf(队列为空); return false; } //指针保存要删节点 PQueueNode ppq-front-next; //头删该节点 pq-front-nextp-next; //保存节点值 *pvalp-val; //释放该节点 free(p); return true; }6.打印从头到尾void PrintQueue(const PLinkQueue pq){ assert(pq!NULL); for(PQueueNode ppq-front-next;p!NULL;pp-next){ printf(%d ,*p); } printf(\n); }7.获取队头元素bool GetFront(PLinkQueue pq, ElemType* pval) { assert(pq ! NULL); if (IsEmpty(pq))return false; *pval pq-front-next-val; return true; }8.获取队尾元素bool GetBack(PLinkQueue pq, ElemType* pval) { assert(pq ! NULL); if (IsEmpty(pq))return false; *pval pq-rear-val; return true; }9.清空队列void ClearQueue(PLinkQueue pq) { assert(pq!NULL); if(IsEmpty(pq))return; //头删所有节点 while(p!NULL){ PQueueNode ppq-front-next; pq-front-nextp-next; free(p); } pq-queuesize0; pq-rearpq-front;//头尾指针都指向头节点 }10.销毁队列void DestroyQueue(PLinkQueue pq) { assert(pq!NULL); //头删所有节点包括头节点 while(pq-front!NULL){ PQueueNode p pq-front; pq-frontp-next; free(p); } pq-queuesize0; pq-front pq-rear NULL;//头尾指针都指向空 }———————————————————————————————————————————这就是非循环队列的全部内容下节我们将继续学习循环队列的内容期待下一次相遇~~~