我的书签
添加书签
移除书签第24章 自适应容器：栈和队列
标准模板库（STL）提供了一些这样的容器，即使用其他容器模拟栈和队列的行为。这种内部使用一种容器但呈现另一种容器的行为特征的容器称为自适应容器（adaptive container）。
在本章中，您将学习：
• 栈和队列的行为特征；
• 使用STL stack；
• 使用STL queue；
• 使用STL priority_queue。
24.1 栈和队列的行为特征
栈和队列与数组或list极其相似，但对插入、访问和删除元素的方式有一定的限制。可将元素插入到什么位置以及可从什么位置删除元素决定了容器的行为特征。
栈是LIFO（后进先出）系统，只能从栈顶插入或删除元素。可将栈视为一叠盘子，最后叠上去的盘子首先被取下来，而不能取下中间或底部的盘子。图24.1说明了这种“在顶部添加和删除”的元素组织方式。
泛型STL容器std::stack模拟了栈的这种行为。
图24.1 对栈的操作
要使用std::stack，必须包含头文件<stack>：
队列是FIFO（先进先出）系统，元素被插入到队尾，最先插入的元素最先删除。可将队列视为一系列在邮局排队购买邮票的人：先加入队列的人先离开。图24.2说明了这种“在末尾加入、从开头删除”的元素组织方式。
泛型STL容器std::queue模拟了队列的这种行为。
要使用std::queue，必须包含头文件<queue>：
图24.2 队列的操作
24.2 使用STL stack类
STL stack是一个模板类，要使用它，必须包含头文件<stack>。它是一个泛型类，允许在顶部插入和删除元素，而不允许访问中间的元素。从这种角度看，std::stack的行为很像一叠盘子。
在有些STL实现中，std::stack的定义如下：
参数elementType是stack存储的对象类型。第二个模板参数Container是stack使用的默认底层容器实现类。stack默认在内部使用std::deque来存储数据，但可指定使用vector或list来存储数据。因此，实例化整型栈的代码类似于下面这样：
要创建存储类（如Tuna）对象的栈，可使用下述代码：
要创建使用不同底层容器的栈，可使用如下代码：
程序清单24.1演示了各种实例化方式。
程序清单24.1 实例化STL stack
分析：
该示例没有输出，但演示了如何实例化STL模板stack。第8行和第11行实例化了两个stack对象，分别用于存储类型为int和double的元素。第14行也实例化了一个用于存储double元素的stack，但将第二个模板参数（stack在内部使用的集合类）指定为vector。如果没有指定第二个模板参数，stack将自动使用默认的std::deque。最后，第17行表明，可使用一个stack对象的拷贝来创建另一个stack对象。
stack改变了另一种容器（如deque、list或vector）的行为，通过限制元素插入或删除的方式实现其功能，从而提供严格遵守栈机制的行为特征。表 24.1 解释了 stack 类的公有成员函数并演示了如何将这些函数用于整型栈。
表24.1 std::stack的成员函数
如表所示，stack的公有成员函数只提供了这样的方法，即插入或删除元素的位置符合栈的行为特征。也就是说，虽然底层容器可能是deque、vector或list，但禁用了这些容器的有些功能，以实现栈的行为特征。
24.2.3 使用push()和pop()在栈顶插入和删除元素
要插入元素，可使用成员方法stack<T>::push()：
根据定义，通常只能访问栈顶元素，为此可使用成员方法top()：
要删除栈顶元素，可使用成员方法pop()：
程序清单24.2演示了如何使用push()和pop()在栈中插入和删除元素。
程序清单24.2 使用整型stack
输出：
分析：
该示例首先使用 stack::push()将一些值插入到整型 stack stackInts中，如第 10～13行所示；然后使用stack::pop()从stack中删除元素。stack只允许访问栈顶元素，可使用成员stack::top()访问栈顶元素，如第18行所示。使用stack::pop()可每次从stack中删除一个元素，如第19行所示。第19行所属的while循环确保不断执行pop()操作，直到stack为空。从元素弹出的顺序可知，最后插入的元素最先弹出，这说明了stack的典型LIFO（后进先出）特征。
程序清单24.2演示了stack的所有5个成员函数。注意，被stack类用作底层容器的所有STL顺序容器都提供了push_back和insert，但它们不是stack的公有成员函数；用于访问非容器顶部元素的迭代器也如此。stack只暴露了栈顶元素，而没有暴露其他任何元素。
24.3 使用STL queue类
STL queue是一个模板类，要使用它，必须包含头文件<queue>。queue是一个泛型类，只允许在末尾插入元素以及从开头删除元素。queue不允许访问中间的元素，但可以访问开头和末尾的元素。从这种意义上说，std::queue的行为与超市收银台前的队列极其相似。
std::queue的定义如下：
其中elementType是queue对象包含的元素的类型。Container是std::queue用于存储其数据的集合类型，可将该模板参数设置为std::list、vector或deque，默认为deque。
实例化整型queue的最简单方式如下：
如果要创建这样的queue，即其元素类型为double，并使用std::list（而不是默认的queue）存储这些元素，可以像下面这样做：
与stack一样，也可使用一个queue来实例化另一个queue：
程序清单24.3演示了各种实例化std::queue的方式。
程序清单24.3 实例化STL queue
分析：
上述示例演示了如何实例化STL泛型类queue，第8行创建了一个整型queue，而第11行创建了一个双精度型 queue。第 14行实例化 queue qDoublesInList时，显式地指定 queue使用底层容器 std::list来管理内部数据，这是通过第二个模板参数指定的。如果没有指定第二个模板参数（就像实例化前两个queue那样），默认将使用底层容器std::deque来管理queue的内容。
与std::stack一样，std::queue的实现也是基于STL容器vector、list或deque的。queue提供了几个成员函数来实现队列的行为特征。表 24.2通过程序清单 24.3所示的整型 queue qIntegers解释了 queue的成员函数。
表24.2 std::queue的成员函数
STL queue没有提供 begin()和 end()等函数，而大多数STL容器都提供了这些函数，包括 queue类在底层使用的 deque、vector 或list。这是有意为之的，旨在只允许对 queue执行符合队列行为特征的操作。
24.3.3 使用push()在队尾插入以及使用pop()从队首删除
对于queue，元素在末尾插入，这是使用成员方法push()完成的：
删除是在开头进行的，这是使用成员方法pop()完成的：
与stack不同，queue允许查看其两端的元素，即容器的开头和末尾：
程序清单24.4演示了如何插入、删除和查看元素。
程序清单24.4 在整型queue中插入、删除和查看元素
输出：
分析：
在第9～12行，使用push()在队列qIntegers的末尾插入元素。第15行和第16行分别使用函数front()和back()引用了队首和队尾的元素。第18～22行的while循环显示队首的元素，然后使用 pop()删除它（第 21 行），直到队列为空。从输出可知，元素被删除的顺序与插入顺序相同，因为元素在队尾插入，从队首删除。
24.4 使用STL优先级队列
STL priority_queue是一个模板类，要使用它，也必须包含头文件<queue>。priority_queue与 queue的不同之处在于，包含最大值（或二元谓词认为是最大值）的元素位于队首，且只能在队首执行操作。
std::priority_queue类的定义如下：
其中elementType是一个模板参数，指定了优先级队列将包含的元素的类型。第二个模板参数指定priority_queue在内部将使用哪个集合类来存储数据，第三个参数让程序员能够指定一个二元谓词，以帮助队列判断哪个元素应位于队首。如果没有指定二元谓词，priority_queue类将默认使用std::less，它使用运算符<比较对象。
要实例化整型priority_queue，最简单的方式如下：
如果要创建一个这样的priority_queue，即其元素类型为double，且按小到大的顺序存储在std::deque中，则可这样做：
与stack一样，也可使用一个priority_queue来实例化另一个priority_queue：
程序清单24.5演示了如何实例化priority_queue对象。
程序清单24.5 实例化STL priority_queue
分析：
第7行和第10行实例化了两个priority_queue，其元素类型分别为int和double。由于没有指定其他模板参数，因此将默认使用std::vector作为内部数据的容器，并默认使用std::less提供的比较标准。因此，这两个队列将包含的值最大的元素放在队首。然而，实例化pqIntegers_Inverse时，通过第二个参数指定使用deque作为内部容器，并将谓词指定为std::greater，该谓词导致最小的元素位于队首。
本章后面的程序清单24.7说明了使用谓词std::greater<T>带来的影响。
queue提供了成员函数front()和back()，但priority_queue没有。表24.3简要地介绍了priority_queue的成员函数。
表24.3 std::priority_queue的成员函数
从该表可知，只能使用top()来访问队列的成员，该函数返回值最大的元素，最大的元素是根据用户指定的谓词或默认的std::less确定的。
24.4.3 使用push()在priority_queue末尾插入以及使用pop()在priority_queue开头删除
要在priority_queue中插入元素，可使用成员方法push()：
要在priority_queue开头删除元素，可使用pop()：
程序清单24.6演示了如何使用priority_queue的成员函数。
程序清单24.6 使用priority_queue的成员函数push()、top()和pop()
输出：
分析：
这个示例首先将一些整数插入到priority_queue中（如第9～12行所示），然后使用pop()删除队首元素，如第18行所示。从输出可知，值最大的元素位于队首，因此调用priority_queue::pop()将删除容器中值最大的元素；可通过方法top()访问该元素，如第17行所示。由于这里没有提供优先级谓词，优先级队列自动将元素按降序排列（最大的值位于队首）。
下一个示例（程序清单 24.7）使用谓词 std::greater <int>实例化一个 priority_queue。该谓词导致优先级队列认为包含的数字最小的元素为最大的元素，并将其放在队首。
程序清单24.7 通过使用谓词将值最小的元素放在priority_queue开头
输出：
分析：
在这个示例中，大多数代码以及提供给priority_queue的所有值都与前一个示例（程序清单24.6）相同，但输出表明这两个队列的行为不同。这个 priority_queue使用谓词 greater <int>比较其元素，如第8行所示。该谓词导致包含的整数最小的元素被认为是最大的，因此放在队首。这样，第19行使用的函数top()总是显示priority_queue中最小的整数，然后第20行使用pop()将其删除。
因此，弹出元素时，该priority_queue按升序弹出整数。
24.5 总结
本章阐述了 3个重要的自适应容器——STL stack、queue和 priority_queue。这些容器使用顺序容器并对其进行改造，以满足其内部数据存储需求，再通过成员函数呈现出栈与队列独特的行为特征。
24.6 问与答
问：能否修改栈中间的元素？
答：不能，这不符合栈的行为特征。
问：能否对队列中的所有元素进行迭代？
答：队列不支持迭代器，只能访问队尾的元素。
问：STL算法能否用于自适应容器？
答：STL算法使用迭代器。由于stack和queue类都没有提供标记范围两端的迭代器，因此无法将STL算法用于这些容器。
24.7 作业
作业包括测验和练习，前者帮助读者加深对所学知识的理解，后者提供了使用新学知识的机会。请尽量先完成测验和练习题，然后再对照附录 D的答案。在继续学习下一章前，请务必弄懂这些答案。
1．能否修改priority_queue的行为，使得值最大的元素最后弹出？
2．假设有一个包含Coins对象的priority_queue，要让priority_queue将币值最大的硬币放在队首，需要为Coins定义哪种成员运算符？
3．假设有一个包含6个Coins对象的stack，能否访问或删除第一个插入的Coins对象？
1．邮局有一个包含人（Person类）的队列。Person包含两个成员属性，分别用于存储年龄和性别，其定义如下：
请编写一个二元谓词，帮助priority_queue优先向老人和妇女提供服务。
2．编写一个程序，使用stack类反转用户输入的字符串的排列顺序。
