目录

1：队列的概念和结构

2：队列的实现 

2-1：创建队列

2-2：初始化队列

2-3：销毁队列

2-4：入列

2-5：出列

2-6：判断队列是否为空

2-7：获取队列中元素个数

2-8：获取队头元素

2-9：获取队尾元素

2-10：打印队列

3：总代码

Queue.h文件

Queue.c文件

Test.c文件

1：队列的概念和结构

队列的概念📝

队列：

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)的原则。

入队列：

进行插入操作的一端称为队尾。

出队列：

进行删除操作的一端称为队头。

队列的结构📝

⭐先进先出：入队顺序：A B C D    出队顺序：A B C D 

应用场景📝

栈：解决括号匹配；逆波兰表达式求解；递归改非递归等等。

队列：公平排队，广度优先遍历等等。

2：队列的实现 

🖊：队列的实现可以使用数组或者是链表结构，相对而言链表的结构更优一些，如果是数组结构，那当我们出队时还要移动剩余元素。时间复杂度为O(N).而对于链表结构我们可以创建一个指针变量保存尾结点地址，其出队和入队时间复杂度均为O(1).

2-1：创建队列

思路：

队列的创建需要定义两个结构体，一个用来保存链式结构，另外一个用来记录队头和队尾。

Queue.h文件

//创建队列
typedef int QDataType;
typedef struct QueueNode
{QDataType data;         //储存数据struct QueueNode* next; //储存下一个结点地址
}QNode;//记录队列头尾结点地址
typedef struct Queue
{QNode* head;  //储存头结点地址QNode* tail;  //储存尾结点地址
}Queue;

2-2：初始化队列

思路：

初始化队列时把记录队列队头和队尾的头结点和尾结点地址置空，记录队列队头和队尾的结构体不可能为空，需断言。

Queue.h文件

//初始化队列
void QueueInit(Queue* pq);

Queue.c文件

//初始化队列
void QueueInit(Queue* pq)
{assert(pq);//断言pq->head = pq->tail = NULL;//置空
}

 2-3：销毁队列

思路：

创建指针变量cur初始化为pq->head,然后一边遍历一遍free链表结点。当cur为空时停止遍历。同时把tail和head置空。

Queue.h文件

//销毁队列
void QueueDestory(Queue* pq);

Queue.c文件

//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;//从队头开始遍历销毁结点while (cur){QNode* next = cur->next;//销毁前保存下一个结点地址free(cur);cur = next;}pq->head = pq->tail = NULL;
}

  2-4：入列

思路：

首先创建一个新的结点来保存所要插入的数据，然后开始进行尾插。如果队列为空，则直接把head和tail指向新创建的结点newnode即可。如果队列不为空，那么只需要将tail的next指向新的结点newnode然后刷新尾结点将newnode赋值给tail。

Queue.h文件

//入列
void QueuePush(Queue* pq, QDataType x);

Queue.c文件

//入列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建一个新的结点QNode* newnode =(QNode*)malloc(sizeof(QNode));assert(newnode); //新结点不能为空//将所要入列的元素赋值给新创建的结点newnode->data = x;newnode->next = NULL;//队列为空的情况if (pq->tail == NULL){assert(pq->tail == NULL);//队列为空，其头结点也必定为空pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;//刷新尾结点}
}

 2-5：出列

思路：

想要出队列的前提是队列不为空，这里出队列需要讨论两种情况。在一般情况下我们只需要定义一个指针变量next用来保存head的下一个结点，然后free掉head，将next的的值赋值给head完成head的刷新。但当我们删除到只剩下一个结点，再删一次head为空指针，而此时tail就变为了野指针。此时我们需要把head和tail都置空。

Queue.h文件

//出列
void QueuePop(Queue* pq);

Queue.c文件

//出列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head && pq->tail);//出列必须保证队列不为空//当出列到只剩下一个元素，tail为野指针，需单独判断if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}

 2-6：判断队列是否为空

思路：

当head为空，队列就为空，此时tail也为空，直接返回即可。

Queue.h文件

//判断队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c文件

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);//return pq->head == NULL && pq->next==NULL;return pq->head == NULL;
}

 2-7：获取队列中元素个数

思路：

法一：创建临时变量size，然后创建指针变量cur来遍历链表，遍历一个结点size++，直到cur为空指针。其时间复杂度为O(N).

法二：在创建结构体时多创建一个size结构体成员，用来记录有效数据个数，入队列size++，出队列size--。其时间复杂度为O(1).

Queue.h文件

//获取队列中元素个数
size_t QueueSize(Queue* pq);

Queue.c文件

//获取队列中元素个数
size_t QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;
}

  2-8：获取队头元素

思路：

要获取队头元素首先队列不能为空，需要断言。然后直接返回头部结点的数据即可。

Queue.h文件

//获取队头元素
QDataType QueueFront(Queue* pq);

Queue.c文件

//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}

   2-9：获取队尾元素

思路：

断言队列不为空，直接返回尾部结点数据。

Queue.h文件

//获取队尾元素
QDataType QueueBack(Queue* pq);

Queue.c文件

//获取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}

2-10：打印队列

思路：

在队列不为空的情况下访问头结点数据，然后出队列，继续访问，继续出队列，直到队列为空。

Test.c文件

void TestQueue()
{Queue q;QueueInit(&q);//入队QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//打印while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");
}

3：总代码

Queue.h文件

#pragma once#include 
#include 
#include 
#include //创建队列
typedef int QDataType;
typedef struct QueueNode
{QDataType data;         //储存数据struct QueueNode* next; //储存下一个结点地址
}QNode;//记录队列头尾结点地址
typedef struct Queue
{QNode* head;  //储存头结点地址QNode* tail;  //储存尾结点地址
}Queue;//初始化队列
void QueueInit(Queue* pq);//销毁队列
void QueueDestory(Queue* pq);//入列
void QueuePush(Queue* pq, QDataType x);//出列
void QueuePop(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//获取队列中元素个数
size_t QueueSize(Queue* pq);//获取队头元素
QDataType QueueFront(Queue* pq);//获取队尾元素
QDataType QueueBack(Queue* pq);

Queue.c文件

#include "Queue.h"//初始化队列
void QueueInit(Queue* pq)
{assert(pq);//断言pq->head = pq->tail = NULL;//置空
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;//从队头开始遍历销毁结点while (cur){QNode* next = cur->next;//销毁前保存下一个结点地址free(cur);cur = next;}pq->head = pq->tail = NULL;
}//入列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建一个新的结点QNode* newnode =(QNode*)malloc(sizeof(QNode));assert(newnode); //新结点不能为空//将所要入列的元素赋值给新创建的结点newnode->data = x;newnode->next = NULL;//队列为空的情况if (pq->tail == NULL){assert(pq->tail == NULL);//队列为空，其头结点也必定为空pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;//刷新尾结点}
}//出列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head && pq->tail);//出列必须保证队列不为空//当出列到只剩下一个元素，tail为野指针，需单独判断if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);//return pq->head == NULL && pq->next==NULL;return pq->head == NULL;
}//获取队列中元素个数
size_t QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;
}//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}//获取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}

Test.c文件

#include "Queue.h"void TestQueue()
{Queue q;QueueInit(&q);//入队QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//打印while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");
}int main()
{TestQueue();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！