正文
1.队列的概念及结构
队列对于临时数据的处理也十分有趣，它跟栈一样都是有约束条件的数组（或者链表）。区别在于我们想要按什么顺序去处理数据，而这个顺序当然是要取决于具体的应用场景。
你可以将队列想象成是电影院排队。排在最前面的人会最先离队进入影院。套用到队列上，就是首先加入队列的，将会首先从队列移出。
因此计算机科学家都用缩写“FIFO”（first in, first out）先进先出，来形容它。
与栈类似，队列也有 3个限制（但内容不同）。
▶ 只能在末尾插入数据（这跟栈一样）。
▶ 只能读取开头的数据（这跟栈相反）。
▶ 只能移除开头的数据（这也跟栈相反）。
下面来看看它是怎么运作的，先准备一个空队列。
首先，插入 5（虽然栈的插入就叫压栈，但队列的插入却没有固定的叫法，一般可以叫放入、加入、入队）。
然后，插入 9。
接着，插入 100。
目前为止，队列表现得还跟栈一样，但要是移除数据的话，就会跟栈反着来了，因为队列是从开头移除数据的。
想移除数据，得先从 5 开始，因为开头就是它。
接着，移除 9。
这样一来，队列就只剩下 100了。
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.1队列结构的定义
typedef struct Queue { QNode* head; //记录队头的位置 QNode* tail; //记录队尾的位置 int size; //记录队列的长度 }Queue;
2.2队列中存储数据的结点
typedef int QDataType; typedef struct QueueNode { QDataType data; //存储的数据 struct QueueNode* next; //记录下一个结点的位置 }QNode;
2.3函数接口的实现
首先是在Queue.h文件中进行函数声明
Queu.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDataType; typedef struct QueueNode { QDataType data; //存储的数据 struct QueueNode* next; //记录下一个结点的位置 }QNode; typedef struct Queue { QNode* head; //记录队头的位置 QNode* tail; //记录队尾的位置 int size; //记录队列的长度 }Queue; //队列的初始化 void QueueInit(Queue* pq); //释放malloc出的内存 void QueueDestroy(Queue* pq); //入队 void QueuePush(Queue* pq, QDataType x); //出队 void QueuePop(Queue* pq); //获取队头的数据 QDataType QueueFront(Queue* pq); //获取队尾的数据 QDataType QueueBack(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //队列数据的个数 int QueueSize(Queue* pq);
在Queue.c文件中进行函数的定义
Queue.c
#define _CRT_SECURE_NO_DEPRECATE 1 #include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); //用cur找尾 QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->size = 0; pq->head = pq->tail = NULL; } void QueuePush(Queue* pq,QDataType data) { assert(pq); QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } //初始化结点 newNode->data = data; newNode->next = NULL; if (pq->tail == NULL) { //队列为空时入队 pq->head = newNode; pq->tail = newNode; } else { //队列不为空时入队 pq->tail->next = newNode; pq->tail = newNode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { //只有一个结点时 free(pq->head); pq->head = pq->tail = NULL; } else { //一般情况 QNode* del = pq->head; pq->head = pq->head->next; free(del); } pq->size--; } 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; } bool QueueEmpty(Queue* pq) { assert(pq); //return pq->size==0; return pq->head == NULL && pq->tail == NULL; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
