什么是队列?
队列是一种特殊的线性表, 特殊之处在于它只允许在表的前端 (front) 进行删除操作, 而在表的后端 (rear) 进行插入操作, 和栈一样, 队列是一种操作受限制的线性表. 进行插入操作的端称为队尾, 进行删除操作的端称为队头. 队列中没有元素时, 称为空队列.
链式队列是用单链表的形式来表示队列, 但是要符合队列 "尾进头出" 的规则
链式队列的构建:
链式队列 = 单链表 + 队列.
如下代码是对一个队列的链式存储的定义: 首先定义一个构成单链表基本单元的结点, 然后定义由指向结点的头指针, 指向结点的尾指针和表示队列长度的变量组成的队列
- // 链式队列 链式结构 + 队列
- // 链式结构体 = 单链表的基本单元: 结点
- struct Node{
- int data;// 数据域
- struct Node* next; // 指针域
- };
- // 队列结构体 = 头指针 + 尾指针 + 队列大小
- struct Queue{
- struct Node* front;// 指向结点的头指针
- struct Node* rear;// 指向结点的尾指针
- int queueSize; // 队列大小 / 长度
- };
创建结点:
队列是由一个一个结点通过指针链接起来的
- // 创建结点
- struct Node* createNode(int data){
- struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
- newNode->next=NULL;
- newNode->data=data;
- return newNode;
- };
队列的初始化:
首先使用 malloc 函数为队列分配一块内存, 初始状态队列的头指针和尾指针在一起都为空(不带头结点), 然后设置队列的大小为 0. 这样队列的初始化操作就完成了.
- // 队列初始化
- struct Queue* createQueue(){
- struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));// 分配内存空间
- queue->front=queue->rear=NULL;// 头指针和尾指针在一起为空
- queue->queueSize=0;// 队列大小为 0
- return queue;
- }
入队操作:
准备工作: 首先创建入队函数 push()传入两个参数, 一个是需要插入那个队列另一个是需要插入的数据. 然后调用 createNode()函数创建一个新的结点, 保存插入的数据.
准备工作完成后: 先判断队列是否是空队列, 如果为空队列直接将 front 和 rear 指针指向这个新建结点即可, 若不为空, 则将尾指针的下一个位置指向新建结点, 然后再将尾指针修改为这个新建结点.(这个地方我个人感觉比较难懂, 我的理解是 先告诉这个新建结点在哪里, 然后在移动 rear 指针到新建结点把他设为队尾).
最后别忘记 queueSize 自增, 表示队列长度的增加.
- void push(struct Queue* queue,int data){
- struct Node* newNode=createNode(data);
- if(queue->queueSize==0)
- queue->front=newNode;
- else
- queue->rear->next=newNode;
- queue->rear=newNode;
- queue->queueSize++;
- }
获取对头元素:
首先判断队列 queueSize 是否为 0 如果为 0 说明队列为空, 如果不为空直接返回队列头指针的 data 值.
- // 获取对头元素
- int queryFront(struct Queue* queue) {
- if(queue->queueSize==0){
- printf("队列为空无法获取对头元素");
- printf("\n");
- return -1;
- }
- return queue->front->data;
- }
判断队列是否为空:
代码很简单就不一一解释了.
- // 判断队列是否为空
- int empty(struct Queue* queue){
- if(queue->queueSize==0)
- return 0;
- else
- return 1;
- }
出队操作:
新建头结点指针指向队列 front 指针所指结点的下一个位置(因为出队操作是在对头进行的), 然后释放原来的队头结点, 最后设置这个新的头结点为队头. 最后队列的大小减 1.
- // 出队操作
- void pop (struct Queue* queue){
- if(queue->queueSize==0){
- printf("队列为空不能出队");
- exit(0);
- }else{
- struct Node* newFrontNode=queue->front->next;
- free(queue->front);
- queue->front=newFrontNode;
- queue->queueSize--;
- }
- }
最后附上完整代码:
- #include <stdio.h>
- #include <stdlib.h>
- // 链式队列 链式结构 + 队列
- // 链式结构体 = 单链表的基本单元: 结点
- struct Node{
- int data;// 数据域
- struct Node* next; // 指针域
- };
- // 队列结构体 = 头指针 + 尾指针 + 队列大小
- struct Queue{
- struct Node* front;// 指向结点的头指针
- struct Node* rear;// 指向结点的尾指针
- int queueSize; // 队列大小 / 长度
- };
- // 创建结点
- struct Node* createNode(int data){
- struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
- newNode->next=NULL;
- newNode->data=data;
- return newNode;
- };
- // 队列初始化
- struct Queue* createQueue(){
- struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));// 分配内存空间
- queue->front=queue->rear=NULL;// 头指针和尾指针在一起为空
- queue->queueSize=0;// 队列大小为 0
- return queue;
- }
- // 入队
- void push(struct Queue* queue,int data){
- struct Node* newNode=createNode(data);
- if(queue->queueSize==0)
- queue->front=newNode;
- else
- queue->rear->next=newNode;
- queue->rear=newNode;
- queue->queueSize++;
- }
- // 获取对头元素
- int queryFront(struct Queue* queue) {
- if(queue->queueSize==0){
- printf("队列为空无法获取对头元素");
- printf("\n");
- return -1;
- }
- return queue->front->data;
- }
- // 判断队列是否为空
- int empty(struct Queue* queue){
- if(queue->queueSize==0)
- return 0;
- else
- return 1;
- }
- // 出队操作
- void pop (struct Queue* queue){
- if(queue->queueSize==0){
- printf("队列为空不能出队");
- exit(0);
- }else{
- struct Node* newFrontNode=queue->front->next;
- free(queue->front);
- queue->front=newFrontNode;
- queue->queueSize--;
- }
- }
- int main(){
- struct Queue* myQueue=createQueue();
- push(myQueue,1);
- push(myQueue,2);
- push(myQueue,3);
- while(empty(myQueue)){
- printf("%d\t",queryFront(myQueue));
- pop(myQueue);
- }
- printf("\n");
- system("pause");
- return 0;
- }
来源: https://www.cnblogs.com/it1997/p/12071309.html