企业官网建设流程全解析

队列，本质也是受限制的线性结构，只能在一端进行插入另一端进行删除的一种数据结构，被称为 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(p==NULL){ printf("malloc申请空间失败"); return; } pq->front=pq->rear=p; //头尾指针指向空间开始位置 pq->queuesize=STACKINISIZE; }

2..判空

bool IeEmpty(const PSeqQueue pq){ assert(pq!=NULL); return pq->front==pq->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 newsize=pq->queuesize*STACKINCREMENT;//新容量为旧容量*扩容倍数 //1.使用malloc申请大小为新容量的新空间 ELemType* p=(ELemType*)malloc(sizeof(ELemType)*newsize); if(p==NULL){ printf("申请新空间失败"); return false; } //2.使用memmove手动复制所有元素 memmove(p,pq->front,(pq->rear-pq->front)*sizeof(ElemType)); //3.释放原空间，设置头尾指针和新容量 free(pq->front); pq->front=p; pq->rear=pq->front+pq->queuesize; pq->queuesize=newsize; return true; } //入队 bool Push(PSeqQueue pq,ElemType val) { assert(pq != NULL); if(IsFull(pq)){ if(IncMem(pq)==false){ return false; } } //队尾插入新元素，队尾指针向后移动 *pq->rear=val; pq->rear++; return true; }

6.出队：队头出队

bool Pop(PSeqQueue pq,ElemType* pval){ assert(pq!=NULL); if(IsEmpty(pq)){ printf("队列为空"); return falsel } *pval=pq->front;//保存队头元素 //使用memmove覆盖队头元素 memmove(pq->front+1,pq->front,(pq->rear-pq->front-1)*sizeof(ElemType)); //队尾指针向前移动 pq->rear--; return true; }

7.打印

void PrintQueue(const PSeqQueue pq){ assert(pq!=NULL); //队头到队尾，不包括队尾指针的值 for(ElemType* p=pq->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->rear=pq->front; }

11.销毁队列

void DestroyQueue(PSeqQueue pq){ assert(pq!=NULL); ClearQueue(pq);//调用清空函数，清空元素 free(pq->front); pq->front=pq->rear=NULL; pq->queuesize=0; }

———————————————————————————————————————————

二.链式队列(有头节点)的操作实现：

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(p==NULL)return NULL; p->val=val; p->next=NULL; return p; } void InitLinkQueue(PLinkQueue pq) { assert(pq!=NULL); PQueueNode p=BuyNode(0); if(p==NULL){ printf("头节点申请失败"); return; } pq->front=pq->rear=p; pq->queuesize=0; }

2.判空

bool IsEmpty(const PLinkQueue pq){ assert(pq!=NULL); return pq->front==pq->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 p=BuyNode(val); if(p==NULL)return false; //2.尾插新节点 p->next=pq->rear->next; pq->rear->next=p; //3.修改尾指针 pq->rear=p; //元素个数+1 pq->queuesize++; return true; }

5.出队：头删出队，并获取头部节点值

bool Pop(PLinkQueue pq, ElemType* pval) { assert(pq!=NULL); if(IsEmpty(pq)){ printf("队列为空"); return false; } //指针保存要删节点 PQueueNode p=pq->front->next; //头删该节点 pq->front->next=p->next; //保存节点值 *pval=p->val; //释放该节点 free(p); return true; }

6.打印（从头到尾）

void PrintQueue(const PLinkQueue pq){ assert(pq!=NULL); for(PQueueNode p=pq->front->next;p!=NULL;p=p->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 p=pq->front->next; pq->front->next=p->next; free(p); } pq->queuesize=0; pq->rear=pq->front;//头尾指针都指向头节点 }

10.销毁队列

void DestroyQueue(PLinkQueue pq) { assert(pq!=NULL); //头删所有节点，包括头节点 while(pq->front!=NULL){ PQueueNode p = pq->front; pq->front=p->next; free(p); } pq->queuesize=0; pq->front = pq->rear = NULL;//头尾指针都指向空 }

———————————————————————————————————————————

这就是非循环队列的全部内容，下节我们将继续学习循环队列的内容，期待下一次相遇~~~