目录
一 队列的概念与结构
1 概念
概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
入队列：进行插入操作的一端称为队尾；
出队列：进行删除操作的一端称为队头。
2 结构
那用数组实现队列还是链表实现队列呢？
如果只从复杂度分析，没有办法判断出使用数组好还是使用队列好，如果我们使用优化来对比呢？
（1）假如用数组进行时间复杂度优化
（1）像删除数据，比如我们在队头删除数据，所有的数据都要往前（队头）移，你能不能说我们删除数据但是不往前移呢？也不行，如果不往前移，会影响后面插入数据；
（2）如果把队头和队尾互换一下？也不能。头插前面必须要留位置。
这样看来，用数组来进行时间复杂度的优化好像不太现实。
2）假如用链表进行时间复杂度优化
可以再定义一个指针，直接在ptail后面去插入，插入的时间复杂度就变成O(1)
所以如上所述，用链表实现队列
二 队列的实现（链表）
队列结构体的定义需要两个结构体
1 队列的定义：
struct ListNode //节点的结构
{
STDataType data;
struct ListNode* Next;
}
struct Queue //队列
{
struct ListNode* phead;//指向队头节点的指针
struct ListNode* ptail;//指向队尾节点的指针
}2 队列的初始化
Queue.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
//定义节点的结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{
QueueNode* phead;//指向队头节点的指针
QueueNode* ptail;//指向队尾节点的指针
}Queue;
//初始化
void QueueInit(Queue* pq);Queue.c:
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
}test.c:
#include"Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
}
int main()
{
test01();
return 0;
}3、队列的入队（插入）——队尾
插入操作分为两种情况：（1）队列不为空（2）队列为空
（1）队列不为空
（2)队列为空
要把队列为空考虑进去
//入队列，队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建值为x的节点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
}插入的时候要一个一个插入
4 判断队列是否为空
Queue.c
//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead = NULL;
}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 取队头数据和取队尾数据
（1）取队头数据
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}（2）取队尾数据
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}（3）同时取
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}test.c
#include"Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4); //1 2 3 4
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
printf("队头：%d\n", QueueFront(&q));
printf("队尾：%d\n", QueueBack(&q));
}
int main()
{
test01();
return 0;
}7 获取队列有效数据个数
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
++size;
pcur = pcur->next;
}
return size;
}test.c
#include"Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4); //1 2 3 4
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
printf("队头：%d\n", QueueFront(&q));
printf("队尾：%d\n", QueueBack(&q));
printf("size: %d\n", QueueSize(&q));
}
int main()
{
test01();
return 0;
}运行结果为：
队头：1
队尾：4
size:48 销毁链表
//销毁
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;//防止phead、ptail变野指针
}队列结构完整代码：
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
//定义节点的结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{
QueueNode* phead;//指向队头节点的指针
QueueNode* ptail;//指向队尾节点的指针
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队列，队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);Queue.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
}
//入队列,队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建值为x的节点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
}
//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
// 出队列，队头
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;
}
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
++size;
pcur = pcur->next;
}
return size;
}test.c:
#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); //1 2 3 4
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
printf("队头：%d\n", QueueFront(&q));
printf("队尾：%d\n", QueueBack(&q));
printf("size: %d\n", QueueSize(&q));
}
int main()
{
test01();
return 0;
}