目录
一、队列（先进先出的特殊结构）
队列的概念与结构
队列：只允许在一端进行插入数据数据操作，在另一端进行删除数据的特殊线性表，队列具有先进先出的结构
同栈一样，我们先来讨论一下队列的底层结构该如何选型？
首先我们来看一下数组的结构，如果将数组当做队列底层的结构，那么入队列操作的时间复杂度为O(1)，由于出队列操作，数组要删除头部的数据，那么数组头部之后的数据就要整体向前挪动一位，所以出队列的时间复杂度为O(N)；若将队尾与队头对调，他们的时间复杂度将对调。
其次，我们来考虑链表结构，以单链表为例，假设链表的头为队头，链表的尾为队尾，队头用来出数据，时间复杂度为O(1)，队尾用来入数据，由于每次入数据都要遍历找到尾结点，所以时间复杂度为O(N)，如果将队头队尾对调，他们的时间复杂度也将对调。
那么，既然这样，我们就要想一些法子，来减少时间复杂度：
如果用双向链表可不可行呢？这个问题值得思考，假设使用双向链表，对头的prev指针指向队尾，但是每一个结点除去原有的数据，还要存储两个指针类型的数据，如果是32字节的系统，假设是整型数据，int类型数据占4个字节，两个地址占4*2=8字节，4+8=12字节，考虑内存对齐，共消耗了16字节的空间，这个数据过于庞大，所以我们不再考虑双向链表。
下面，我们考虑优化链表的时间复杂度来实现队列的底层结构。
如果是链表头结点为队头，即入队时间复杂度为O(1)，出队时间复杂度为O(N)的情况，我们可以用定义两个指针，分别记录队头和队尾：phead、ptail，来将出队操作的时间复杂度降为O(1)。
从此处我们可以得出一个结论，队列的逻辑结构是线性的，而物理结构不一定是线性的。
二、代码实现
下面，我们来准备一下队列的代码实现：
1、定义队列的结构
//定义结点的结构
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
}Queue;
2、队列的初始化操作
Void QueueInit(Queue*pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
}3、判空操作
bool QueueEmpty(Queue*pq)
{
assert(pq);
return pq->phead == NULL;
}4、入队操作
Void QueuePush(Queue* pq,QueueDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueDataType));
if(newnode == NULL)
{
perror("malloc failed!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if(QueueEmpty(pq))//考虑队列为空的情况
{
pq->phead = pq->ptail = newnode;
}else{
//队列非空
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
}5、出队操作
void QueuePop(Queue* pq)
{
assert(!QueueEmpty(pq));
if(pq->phead == pq->ptail)
{//只有一个结点
free(pq->phead);
pq->phead = pq->ptail = NULL;
}else{
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
}6、取队头、队尾操作
//取队头
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
return pq->phead->data;
}
//取队尾
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
return pq->ptail->data;
}
7、队列销毁操作
//销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
}
8、队列中有效数据个数
//队列有效数据个数
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
size++;
pcur = pcur->next;
}
return size;
}
这里的时间复杂度为O(N)，仅适用于不频繁调用有效数据个数的情况，如果想优化这则代码，我们可以在对列中定义一个整型的size，如果写了size，那么我们在入队列时，size要++，出队列时，size要--，销毁时，size要置为0。
9、测试代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
//QueuePush(&q, 4);
//QueuePop(&q);
int front = QueueFront(&q);
int rear = QueueBack(&q);
int size = QueueSize(&q);
printf("front = %d\n", front);
printf("rear = %d\n", rear);
printf("size = %d\n", size);
}
int main()
{
test01();
return 0;
}10、.h文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//定义结点的结构
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
//int size;
}Queue;
//队列的初始化
void QueueInit(Queue* q);
//入队，队尾
void QueuePush(Queue* pq, QueueDataType x);
//出队，队头
void QueuePop(Queue* pq);
//取队头操作
QueueDataType QueueFront(Queue* pq);
//取队尾操作
QueueDataType QueueBack(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//有限数据个数
int QueueSize(Queue* pq);