<style> .reveal p{text-align:left;}</style> # 队列 --- ## 1. 特性 队列（queue）是一种特殊的线性表，只允许在表的头部（队首）进行删除操作，只允许在表的尾部（队尾）进行插入操作，是一种操作受限制的线性表。队列的数据元素又称为队列元素，在队列中插入一个队列元素称为入队操作，从队列中删除一个队列元素称为出队操作。 因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 --- ## 2. 逻辑结构  --- ## 3. 物理结构 - 队列可用顺序存储方式实现，借助数组便可简单模拟一个队列，但数组空间难以确定，太小会空间不足，太大会造成空间浪费。 - 基于链式存储的队列无需确定空间大小，虽然创建、插入和删除结点较为繁琐，但却可以实现空间的动态增长。 --- ## 4. STL中queue的使用 ``` #include<queue> // 引入头文件 queue<type> q; // 新建队列q，队列中元素类型为type q.size(); // 返回队列长度 q.empty(); // 判断队列是否为空，空则返回true q.push(node); // 入队操作，结点node入队 q.pop(); // 出队操作 q.front(); // 返回队首元素 q.back(); // 返回队尾元素 ``` --- ## 5. 数组模拟实现一个队列 队列是一种操作受限的线性数据结构，可以理解为操作受限的数组，因此，我们可以自行模拟出队列。 --- 栈的操作在队首和队尾执行，因此设立队首指针（数组下标）head、队尾指针tail，初始均为0。 入队即队尾位置赋值，然后队尾+1。 ``` queue[tail++] = t; ``` 出队即队首+1 ``` head++; ``` 取队首即返回队首元素 ``` return queue[head]; ``` --- 取队尾即返回队尾元素 ``` return queue[tail - 1]; // 有效的元素是head -> tail-1 ``` 队列大小即tail-head ``` return tail - head; ``` 判断队空就看队首队尾的大小关系 ``` return head >= tail; // 空则返回true ``` --- ## 6. 结构体队列 queue本质上是数组，所以可以存放各种数据类型，包括结构体。 queue存放了结构体数组类型后，队首队尾访问到的就是结构体类型变量了，需要按照结构体变量的方式去使用。 --- ## 例题与练习题 [**P102** 【基础】取扑克牌](http://39.99.183.126:8888/p/102) [**CCFPB06D06** Blash数集](http://39.99.183.126:8888/p/CCFPB06D06)