队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
如果：
入队列：1 2 3 4 那么，出队列：1 2 3 4
DFS——深度优先遍历——递归/栈实现非递归
BFS——广度优先遍历——队列
几个题目：
1.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（ D ）
A 1
B 2
C 99
D 0或者100
2.以下( B )不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
3.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据) （ B )
A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
定义两个结构体，一个表示队列的结点的结构，一个表示队列的结构
typedef int QDataType; // 链式结构：表示队列 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; // 队列的结构 typedef struct Queue { QueueNode* phead;//头指针 QueueNode* ptail;//尾指针 int size; }Queue;
初始化队列：
// 初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
销毁队列：
一个结点一个结点的释放
// 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->phead; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
队尾入队列：
// 队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; //是空队列的情况 if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
检测队列是否为空：
// 检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; }
队头出队列：
// 队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //1.一个结点 //2.多个结点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { //相当于头删 QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }
获取队列头部元素：
// 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; }
获取队列尾部元素：
// 获取队列队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; }
获取队列中有效元素的个数：
// 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
顺序队列
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。循环队列
在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。
测试一下队列的功能：
#include"Queue.h" int main() { Queue p; QueueInit(&p); QueuePush(&p, 1); QueuePush(&p, 2); printf("队头元素：%d\n", QueueFront(&p)); QueuePop(&p); QueuePush(&p, 3); QueuePush(&p, 4); printf("队列中元素个数：%d\n", QueueSize(&p)); while (!QueueEmpty(&p)) { printf("队头元素：%d\n", QueueFront(&p)); QueuePop(&p); } QueueDestroy(&p); return 0; }
源代码如下：
Queue.h的内容：
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDataType; // 链式结构：表示队列 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; // 队列的结构 typedef struct Queue { QueueNode* phead;//头指针 QueueNode* ptail;//尾指针 int size; }Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 队尾入队列 void QueuePush(Queue* pq, QDataType x); // 队头出队列 void QueuePop(Queue* pq); // 获取队列头部元素 QDataType QueueFront(Queue* pq); // 获取队列队尾元素 QDataType QueueBack(Queue* pq); // 获取队列中有效元素个数 int QueueSize(Queue* pq); // 检测队列是否为空 bool QueueEmpty(Queue* pq);
Queue.c的内容：
#include"Queue.h" // 初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } // 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->phead; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } // 队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; //是空队列的情况 if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } // 检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; } // 队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //1.一个结点 //2.多个结点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { //相当于头删 QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } // 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } // 获取队列队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } // 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
好啦，小雅兰今天的队列的学习内容就到这里啦，还要继续加油噢！！！
