队列

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 【基础】取扑克牌

CCFPB06D06 Blash数集