网站的色调织梦游戏网站模板
目录
1.什么是队列
2.如何实现队列
3.队列的实现
Queue.h中接口总览
具体实现
结构的定义
初始化
销毁
入队列
出队列
取队头元素
取队尾元素
判断是否为空
获取队列的大小
4.完整代码附录
Queue.h
Queue.c
1.什么是队列
队列是一种特殊的线性表，只允许在一端进行数据的插入操作，在另一端进行数据的删除操作。队列中的数据元素必须满足先进先出的性质。
- 插入数据的操作叫做入队列，插入数据的一端叫做队尾。
- 删除数据的操作叫做出队列，删除数据的一端叫做队头。
队列逻辑结构如下图所示：
2.如何实现队列
要想实现队列，必须满足队列的要求，也就是以下两点：
- a、在一端插入数据，在另一端删除数据。
- b、满足先进先出的性质。
所以，我们使用数组（顺序表）或者 链表实现，那么使用哪种结构来实现更好呢？
我们可以对比一下：
| 数组（顺序表） | 链表（单链表） | |
| 头插效率 | O(N) | O(1) |
| 头删效率 | O(N) | O(1) |
| 尾插效率 | O(1) | O(N) |
| 尾删效率 | O(1) | O(N) |
貌似使用数组和链表实现都是一样的，在一端进行插入or删除的效率是O(1)，在另一端进行删除or插入的效率就是O(N) 。
但是我们可以优化一下链表，链表在尾部进行插入or删除的效率之所以是O(N)，是因为需要遍历链表找尾结点，但是，如果我们能够直接找到尾结点，那么链表在尾部进行插入和删除的效率不就都是O(1)了吗？
所以，我们可以使用两个指针head和tail分别指向链表的头结点和尾结点。这样一来，进行尾插时，直接就能找到尾结点，所以尾插的效率也是O(1)。
所以我们实现的队列的最终形态如下：
3.队列的实现
队列的实现，我们主要实现Queue.h和Queue.c文件即可，Queue.h文件中存放声明，Queue.c文件中存放定义。
Queue.h中接口总览
具体实现
结构的定义
实现队列结构的时候，由于我们采用的是链表来实现队列，所以我们需要定义一个个的结点；前面我们分析可知，head指向头结点，tail指向尾结点，可以使得入队列和出队列的时间复杂度都为O(1)，所以我们需要管理好head指针和tail指针，这里我们也采用结构体来管理。
初始化
初始化队列只需要初始化 struct Queue 结构体对象中的成员即可。
- head和tail指针都初始化为空。
- size初始化为0。
销毁
销毁队列的时候，首先需要将节点全部释放，然后将head和tail指针置空，并将size置为0。
入队列
入队列的时候要区分两种情况：
- 入队列的结点是第一个结点，此时让head和tail同时指向该结点即可。
- 入队列的结点不是第一个结点，此时让新结点连接到尾结点的后面即可。
- 最后记得将size++。
出队列
出队列的时候要区分三种情况：
- 队列不能为空。
- 只有一个结点的情况。此时，释放结点之后，将head和tail指针置空。
- 不止一个结点的情况。此时，记录head指向的结点，将head后移，然后释放记录的节点。
注意：最后记得将size--。
取队头元素
直接返回head指向的结点的数据即可。
取队尾元素
直接返回tail指向的结点的数据即可。
判断是否为空
当队列为空时，head和tail都指向空，所以直接判断head或者tail是否为空都可以。
获取队列的大小
直接返回struct Queue结构体类型对象中的size即可。
4.完整代码附录
Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode // 定义结点
{struct QueueNode* next; // 存储下一个结点的地址 QDataType data; // 存储数据
}QNode;typedef struct Queue // 定义队列
{QNode* head; // 指向头结点 QNode* tail; // 指向尾结点 int size; // 记录队列的大小
}Que;// 初始化
void QueueInit(Que* pq);
// 销毁
void QueueDestroy(Que* pq);
// 入队列
void QueuePush(Que* pq, QDataType x);
// 出队列
void QueuePop(Que* pq);
// 取队头元素
QDataType QueueFront(Que* pq);
// 取队尾元素
QDataType QueueBack(Que* pq);
// 判断是否为空
bool QueueEmpty(Que* pq);
// 获取队列的大小
int QueueSize(Que* pq);Queue.c
// 初始化队列
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}// 销毁队列
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur) // 遍历释放结点 {QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}// 入队列
void QueuePush(Que* pq, QDataType x)
{assert(pq); // pq指针不能为空 QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新结点 if (newnode == NULL){perror("malloc fail");exit(-1);}// 初始化新结点中的成员 newnode->data = x;newnode->next = NULL;if (pq->tail == NULL) // 入队列的结点是第一个结点 {pq->head = pq->tail = newnode;}else // 入队列的结点不是第一个结点 {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}// 出队列
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq)); // 出队列的时候，队列不能为空 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;}pq->size--;
}// 取队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}// 取队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}// 判空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}// 获取队列的大小
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}