一、队列的概念及结构
1、概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)。
入队列:进行插入操作的一端称为队尾。
出队列:进行删除操作的一端称为队头。
2、结构
(1)队列的顺序存储结构
- 入队,不需要移动任何元素,时间复杂度为 O(1) 。
- 出队,所有元素需要往前移动,时间复杂度为 O(N) 。
(2)队列的链表存储结构
首先我们定义两个指针,队头指针指向第一个节点,队尾指针指向尾节点。
- 入队(尾插),时间复杂度为 O(1) 。
- 出队(头删),时间复杂度为 O(1) 。
二、队列的实现
如果使用数组删除队头数据,再挪动数据效率为 O(N),不适合。 选择用单向链表来完成队列的实现更好,可以发现头删和尾插效率都很高,而双向链表在这里发挥不出很大的作用。
1、创建文件
- test.c(主函数、测试队列各个接口功能)
- Queue.c(队列接口函数的实现)
- Queue.h(队列的类型定义、接口函数声明、引用的头文件)
2、Queue.h 头文件代码
// Queue.h
// 链式结构:表示队列
#pragma once
#include<stdio.h>
#include<stdbool.h> //bool
#include<assert.h> // assert
#include<stdlib.h> // malloc
typedef int QDataType;
typedef struct QueueNode // 队列节点结构
{
struct QueueNode* next; // 节点指针
QDataType data; // 节点数据
}QueueNode;
typedef struct Queue // 队列的链式结构
{
QueueNode* head; //队头指针
QueueNode* tail; //队尾指针
}Queue;
// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType data);
// 队头出队列
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* pq);
三、Queue.c 中各个接口函数的实现
1、初始化队列
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
2、队列的销毁
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
cur = NULL;
pq->head = pq->tail = NULL;
}
3、队尾入队列(尾插)
// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 动态申请一个节点
newnode->data = x;
newnode->next = NULL; // 尾节点next指针置空
if (pq->head == NULL) // 队列为空
{
pq->head = pq->tail = newnode;
}
else // 队列不为空
{
pq->tail->next = newnode;
pq->tail = newnode; // 更新队尾指针
}
}
4、队头出队列(头删)
// 队头出队列
// 写法一:
void QueuePop(Queue* pq)
{
assert(pq);
//温柔处理方式:
/* if(pq->head == NULL)
return; */
//暴力处理方式:
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next; // 记录头节点的直接后继
free(pq->head); // 释放头节点
pq->head = next; // 更新队头指针
if (pq->head == NULL) // 队列中只有一个节点
{
pq->tail = NULL;
}
}
// 写法二:
void QueuePop(Queue* pq)
{
assert(pq);
//暴力处理方式:
assert(!QueueEmpty(pq));
if(pq->head->next == NULL) // 一个节点
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else // 多个节点
{
QueueNode* next = pq->head->next; // 记录头节点的直接后继
free(pq->head); // 释放头节点
pq->head = next; // 更新队头指针
}
}
注意:链表只有一个节点时,要单独处理,否则可能会造成 pq->tail 野指针的情况。
5、获取队列头部元素
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
6、获取队列队尾元素
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
7、获取队列中有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}
如果频繁调用这个接口函数,可以在 QueuePtr 中加一个 size 来记录数据的个数。
8、检查队列是否为空
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* pq);
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
四、整合代码
// Queue.c
#include "Queue.h"
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
cur = NULL;
pq->head = pq->tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 动态申请一个节点
newnode->data = x;
newnode->next = NULL; // 尾节点next指针置空
if (pq->head == NULL) // 队列为空
{
pq->head = pq->tail = newnode;
}
else // 队列不为空
{
pq->tail->next = newnode;
pq->tail = newnode; // 更新队尾指针
}
}
// 队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next; // 记录头节点的直接后继
free(pq->head); // 释放头节点
pq->head = next; // 更新队头指针
if (pq->head == NULL) // 队列中只有一个节点
{
pq->tail = NULL;
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* pq);
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
五、测试队列的功能
六、拓展
实际中我们有时还会使用一种队列叫循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。
1、空的循环队列
文章来源:https://www.toymoban.com/news/detail-618913.html
2、满的循环队列
文章来源地址https://www.toymoban.com/news/detail-618913.html
到了这里,关于【数据结构】队列(Queue)的实现 -- 详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!