前言

日期：2023.7.25

书籍：2024年数据结构考研复习指导（王道考研系列）

内容：实现顺序队列的基本实现，主要功能如下：
1.链队列的数据结构
2.入队
3.出队
4.遍历
5.求队长

6.清空，销毁

1.链队列的定义

首先我们来看看什么是队列？队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列的结构图如下所示：

明白了队列之后，链队列就非常简单了，用链表表示的队列就简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能惟一确定。

2.链队列的结构

3.链队列的操作

3.1定义链队列

//1.定义一个链队列
//队列的节点类型
typedef struct  LinkNode{ElemType data;//数据域struct LinkNode *next;//指针域
}LinkNode;
//链式队列管理结构
typedef struct LinkQueue{LinkNode *front;  //队头指针LinkNode *rear;   //队尾指针
}LinkQueue;

3.2初始化

//2.初始化
//初始化队列
void InitQueue(LinkQueue *Q){//申请头结点内存空间LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));//初始化时，将头指针和尾指针都指向头结点Q->front = Q->rear = s;//将头结点的下一结点赋空Q->rear->next = NULL;
}

3.3入队

//3.入队
//在队尾执行插入操作
//入队操作：在队尾执行插入操作
void EnQueue(LinkQueue *Q, ElemType x){//申请队列结点LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));//为申请的队列结点赋值s->data = x;s->next = NULL;//将申请的队列结点插入到队尾Q->rear->next = s;//更改队列管理结点中尾指针的指向Q->rear = s;
}

3.4出队

//4.出队
//出队操作：删除队头的第一个有效结点
int DeQueue(LinkQueue *Q,ElemType *x){//如果队中无有效结点，无需进行操作if(Q->front == Q->rear)return 0;//获取队头的第一个有效结点LinkNode *p = Q->front->next;//将队头的第一个有效结点从队列中断开x=p->data;Q->front->next = p->next;//释放该结点free(p);//如果删除的结点是最后一个有效结点，需要更改尾指针的指向if(p == Q->rear)Q->rear = Q->front;return 1;
}

3.5遍历求表长

//5.遍历
//打印队列内的数据
void ShowQueue(LinkQueue *Q){//获取队列中第一个有效结点LinkNode *p = Q->front->next;printf("Front:>");//将队列中每个有效结点中的数据打印while(p != NULL){printf("%d ",p->data);p = p->next;}printf("<:rear.\n");
}//6.求队长
//求队列的长度
int Length(LinkQueue *Q){int len = 0;//初始长度为0//获取队头的第一个有效结点LinkNode *p = Q->front->next;//遍历队列，获取一个结点，将队列长度加一while(p != NULL){len++;p = p->next;}//返回长度值return len;
}

3.6清空，销毁

//7.清空，销毁
//清空队列：释放所有的有效结点
int ClearQueue(LinkQueue *Q){//如果队中无有效结点，无需进行操作if(Q->front == Q->rear)return 0;//获取队头的第一个有效结点LinkNode *p = Q->front->next;//遍历队列中的有效结点while(p != NULL){//移除结点Q->front->next = p->next;//释放结点free(p);//指向下一个结点p = Q->front->next;}Q->rear = Q->front;
}
//销毁队列
void DestroyQueue(LinkQueue *Q){//清空队列ClearQueue(Q);//释放头结点free(Q->front);//将管理结点中的头指针和尾指针都指向空Q->front = Q->rear = NULL;
}

4.完整代码

#include <stdio.h>
#include <stdlib.h>#define ElemType int//1.定义一个链队列
//队列的节点类型
typedef struct  LinkNode{ElemType data;//数据域struct LinkNode *next;//指针域
}LinkNode;
//链式队列管理结构
typedef struct LinkQueue{LinkNode *front;  //队头指针LinkNode *rear;   //队尾指针
}LinkQueue;//2.初始化
//初始化队列
void InitQueue(LinkQueue *Q){//申请头结点内存空间LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));//初始化时，将头指针和尾指针都指向头结点Q->front = Q->rear = s;//将头结点的下一结点赋空Q->rear->next = NULL;
}//3.入队
//在队尾执行插入操作
//入队操作：在队尾执行插入操作
void EnQueue(LinkQueue *Q, ElemType x){//申请队列结点LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));//为申请的队列结点赋值s->data = x;s->next = NULL;//将申请的队列结点插入到队尾Q->rear->next = s;//更改队列管理结点中尾指针的指向Q->rear = s;
}//4.出队
//出队操作：删除队头的第一个有效结点
int DeQueue(LinkQueue *Q,ElemType *x){//如果队中无有效结点，无需进行操作if(Q->front == Q->rear)return 0;//获取队头的第一个有效结点LinkNode *p = Q->front->next;//将队头的第一个有效结点从队列中断开x=p->data;Q->front->next = p->next;//释放该结点free(p);//如果删除的结点是最后一个有效结点，需要更改尾指针的指向if(p == Q->rear)Q->rear = Q->front;return 1;
}//5.遍历
//打印队列内的数据
void ShowQueue(LinkQueue *Q){//获取队列中第一个有效结点LinkNode *p = Q->front->next;printf("Front:>");//将队列中每个有效结点中的数据打印while(p != NULL){printf("%d ",p->data);p = p->next;}printf("<:rear.\n");
}//6.求队长
//求队列的长度
int Length(LinkQueue *Q){int len = 0;//初始长度为0//获取队头的第一个有效结点LinkNode *p = Q->front->next;//遍历队列，获取一个结点，将队列长度加一while(p != NULL){len++;p = p->next;}//返回长度值return len;
}
//7.清空，销毁
//清空队列：释放所有的有效结点
int ClearQueue(LinkQueue *Q){//如果队中无有效结点，无需进行操作if(Q->front == Q->rear)return 0;//获取队头的第一个有效结点LinkNode *p = Q->front->next;//遍历队列中的有效结点while(p != NULL){//移除结点Q->front->next = p->next;//释放结点free(p);//指向下一个结点p = Q->front->next;}Q->rear = Q->front;
}
//销毁队列
void DestroyQueue(LinkQueue *Q){//清空队列ClearQueue(Q);//释放头结点free(Q->front);//将管理结点中的头指针和尾指针都指向空Q->front = Q->rear = NULL;
}void main(){LinkQueue Q;InitQueue(&Q);//初始化队列for(int i=1; i<=10; ++i){EnQueue(&Q,i);//入队操作}ShowQueue(&Q);int x;DeQueue(&Q,&x);DeQueue(&Q,&x);ShowQueue(&Q);printf("Len = %d\n",Length(&Q));
}