【数据结构】_队列的结构与实现

目录

1. 队列的概念和结构

2. 队列的应用

3. 队列的实现

3.1 队列实现的底层结构选择

3.2 结构体设计

3.2.1 仅为链表结点设计结构体

3.2.2 为链表再设计一个结构体

3.3 Queue.h

3.4 Queue.c

3.5 Test_Queue.c

注：部分方法实现细节

1. 队列的概念和结构

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

入队列：进行插入操作的一端称为队尾；

出队列：进行删除操作的一端称为队头；（尾进头出）

2. 队列的应用

队列的最大特点是保持公平性。其主要应用场景有以下两个：

（1）设置排队器：实现先进先出；

（2）实现二叉树的广度优先遍历；

3. 队列的实现

3.1 队列实现的底层结构选择

1、若采用数组实现：

若将数组头视为队头，数组尾视为队尾，则插入对应尾插实现方便，但删除对应头删实现麻烦；

若将数组头视为队尾，数组尾视为队头，则删除对应尾删实现方便，但插入对应头插实现麻烦；

选数组实现队列则不便实现。

2、若采用单链表实现：（采用此种结构）

（相较于双链表，单链表更节省空间）

将链表尾视为队尾，链表头视为队头，

则插入对应尾插实现方便（记录尾结点可避免遍历），删除对应头删也实现方便。

3.2 结构体设计

采用单链表结构实现队列，则结点包括数据域val和后继指针域next两个成员。

且队列的插入通过链表尾插实现，为了避免每次插入都需遍历链表，采取插入传参尾结点的方式；

3.2.1 仅为链表结点设计结构体

以插入和删除操作为例，都有可能造成第一个结点指针和尾结点指针的变化，故需传二级指针：

typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;
// 队尾插入
void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
// 队头删除
void QueuePop(QNode** pphead, QNode** pptail);

注：若采取设有头结点的单链表，可传一级指针，但仍然需传队尾结点指针，仍需要传递两个参数，总体而言依然较为麻烦。 

3.2.2 为链表再设计一个结构体

由于插入删除操作均需队头指针与队尾指针，可为其再设置一个结构体。

同时考虑：由于需要提供返回队列元素个数的方法，若在该方法内部对单链表进行遍历，则该方法时间复杂度为O(N)，可以在Queue结构体内再设置一个变量size以计算队列元素个数：

typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;
typedef struct Queue {
	QNode* phead;
	QNode* ptail;
    int size;
}Queue;
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);

采取这种方式，队头队尾指针作为Queue结构体变量，改变队头队尾指针只需传递该结构体的一级指针即可。

既避免了使用二级指针可能导致的的接口不一致问题，也使得插入删除方法大的参数减少。

3.3 Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;
typedef struct Queue {
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 销毁
void QueueDestory(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 计算列表元素个数；
int QueueSize(Queue* pq);
// 取队头/队尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
// 判空
bool QueueEmpty(Queue* pq);

3.4 Queue.c

#include"Queue.h"
// 初始化
void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
// 队尾插入
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL) {
		perror("malloc fail");
		return;
	}
	newNode->val = x;
	newNode->next = NULL;
	// 情况1：队列为空
	if (pq->ptail == NULL) {
		pq->phead = pq->ptail = newNode;
	}
	// 情况2：队列不为空：队尾插入
	else {
		pq->ptail->next = newNode;
		pq->ptail = newNode;
	}
	pq->size++;
}
// 队头删除
void QueuePop(Queue* pq) {
	assert(pq);
	assert(QueueSize(pq)!=0);
	// 情况1：队列仅一个结点
	if (pq->phead->next == NULL) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	// 情况2：队列有多个结点
	else {
		QNode* pheadNext = pq->phead->next;
		free(pq->phead);
		pq->phead = NULL;
		pq->phead = pheadNext;
	}
	pq->size--;
}
// 计算列表元素个数；
int QueueSize(Queue* pq) {
	return pq->size;
}
// 取队头/队尾数据
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}
// 判空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->size == 0;
}
// 销毁
void QueueDestory(Queue* pq) {
	assert(pq);
	QNode* cur = pq->phead;
	while (cur) {
		QNode* curNext = cur->next;
		free(cur);
		cur = NULL;
		cur = curNext;
	}
	pq->phead = pq->ptail = NULL;
}

3.5 Test_Queue.c

#include"Queue.h"
int main() {
	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);
	}
	QueueDestory(&q);
	return 0;
}

注：部分方法实现细节

对于队头的删除操作，按照方法完善思路，首先应该是考虑多个结点的无特殊情况，而后考虑对于删除结点的特殊操作进行补充：

（1）需保证队列当中有结点可删，即队列数据个数不为0：可直接使用assert实现；

（2）若队列仅剩一个元素，按当前无特殊情况处理的方法实现，则pq->ptail未置空，使得其成为野指针，故需对其进行单独处理。

综合以上两点，方法实现如下：

// 队头删除
void QueuePop(Queue* pq) {
	assert(pq);
	assert(QueueSize(pq)!=0);
	QNode* pheadNext = pq->phead->next;
	free(pq->phead);
	pq->phead = NULL;
	pq->phead = pheadNext;
	pq->size--;
	// 特殊情况单独处理：队列仅有一个结点
	if (pq->phead == NULL) {
		pq->ptail = NULL;
	}
}

这种方法框架可以正确实现功能，但程序结构并不清晰，可以在此基础上进行结构的优化，即使用分支处理① 队列仅有一个结点 ② 队列有≥2个结点。具体实现见3.4部分程序，此处不再重复。