第8章队列与deque类2025/6/171队列的特点队列的创建与独特的函数队列与回文串队列与加密解密队列与约瑟夫问题队列与广度搜索优先队列队列与排队

8.1队列的特点2025/6/172队列擅长在线性表的头、尾两端实施删除和添加操作，甚至可以把线性表实现成只在头、尾两端操作，所以人们也称队列是受限的线性表。入列时，最先进入的节点在队头，最后进入的节点在队尾。出列时，从队列的头开始删除节点，最后一个删除的节点是队尾的节点。队列是一种先进先出的数据结构，简称FIFO（FirstInFirstout）

8.1队列的特点2025/6/173头节点（队头）在左边、尾节点（队尾）在右边。

8.2队列的创建与独特函数2025/6/174std::deque是C++标准模板库（StandardTemplateLibrary,STL）中的模板类，用于实现队列这种数据结构，即提供先进先出的数据结构（也称队列是STL的容器之一），std::deque支持在队列的两端进行入列和出列操作（称为双端队列）。需要注意，当std使用作用域运算符（也称解析运算符））“：：”访问deque时不要误写为str::Deque，即不可以将deque的首写字母写成大写的D。称std::deque类的实例（对象）为队列，其中的节点的逻辑结构是线性结构。

2025/6/1758.2队列的创建与独特函数1创建队列使用std::deque类创建队列时，必须要指定模板类中的参数类型的具体类型，类型是可以是C++允许的数据类型，比如int、float、char和类等，即指定队列中节点里的数据的类型。例如，指定队列deque的节点中的数据的类型是std::string类型：std::dequestr::stringqueue;deque队列栈的存储方式是顺序存储，即使用数组管理节点，后面叙述中说队列的节点中的数据或队列中的数据都是正确的。注意：如果只在头、尾端操作链表，就可以把链表当队列来使用，那么这样的队列是链式存储。

2025/6/1768.2队列的创建与独特函数2独特的函数?

2025/6/1778.2队列的创建与独特函数2独特的函数?

2025/6/1788.2队列的创建与独特函数3单端队列queuestd::queue是C++标准模板库的队列适配器，相对于双端队列std::deque，称std::queue的实例是单端队列，单端队列std::queue只提供了队列的基本操作接（只适配了双端队列的部分方法），如入列push()、出列pop()、返回队头数据front()，返回队尾数据back(),但不提供从队尾出列、从对头入列的操作。因此，如果需要在队列的两端进行快速插入和删除操作，包括从队尾出列、对头入列，可以使用双端队列std::deque；如果只需要队列的基本操作，则可以使用单端队列std::queue。创建单端队列时，例如queueWithList,可以指定queueWithList的存储方式是std:list,那么queueWithList将使用链式存储（不可以指定双端队列的存储方式是链式存储）例如：std::queueint,std::listintqueueWithList;

2025/6/1798.2队列的创建与独特函数ch8_1.cpp例子1使用队列的独特函数ch8_1.cpp使用了队列的独特函数.

8.3队列与回文串2025/6/1710回文串是指和其反转（倒置）相同的字符串，例如：racecar,123321，level”，toot，civic，pop，eye，rotator，pip都是回文串。我们曾在第3章例子4，使用递归方法判断一个字符串是否是回文串。

2025/6/17118.3队列与回文串ch8_2.cpp例子2使用队列也可以判断一个字符串是否是回文串。将字符串中的全部字符按顺序依次入列，然后开始分别从头、尾出列，如果字符串是回文串，那么从头出列的节点一定和从尾出列的节点相同，当队列中剩余的节点数目不足2个时，停止出列。利用队列判断字符串是否是回文串读者可以和第7章中的例7-2进行比较，分别体会栈和队列的特点。

8.4队列与加密解密2025/6/1712用队列可以方便地对字符串实施加密（解密）操作。出列的对象参与加密字符串中一个字符（出列的对象参与解密字符串中一个字符），然后再重新入列，一直到字符串中的字符全部被加密完毕（字符串中的全部字符被解密完毕）。

2025/6/17138.4队列与加密解密encryption_decryption.cpp例子3ch8_3.cpp使用队列加密、解密字符串encryption_decryption.cpp中的函数使用队列加密、解密字符串。

8.5队