7.6　堆栈

堆栈stack容器，与queue和priority_queue一起被归类为适配器，这意味着它们将通过调整某一个基本序列容器以存储自己的数据。这是一个遗憾的令人困惑的情况，为什么某些事情一定要与它的底层实现的细节联系在一起呢—这些容器被称为“适配器”的真相只对库的创建者才有基本的价值。当用户使用它们时，通常并不关心它们是否是适配器，仅需知道它们能够解决自己的问题就行了。诚然，有时知道可以选择不同的实现或者在现存的容器对象之上建立一个适配器是很有用的，但是，通常那一层次的功能已经在适配器的行为中被删除了。因此，如果看到在别处某个容器被强调是一个适配器，一般只能指出实际上什么时候它是有用的。注意，每一种类型的适配器都有一个该适配器构建在其上的默认的容器，而且这种默认是最明智的实现方式。在大多数情况下，用户不必关心容器的底层的具体实现。

下面的例子显示实现stack＜string＞的3种方式：默认方式（使用deque），然后采用vector的方式，最后一个采用list的方式：

如果读者使用过其他stack类的话，这里的top（）和pop（）操作似乎并不直观。当调用pop（）时，它返回一个void值而不是所预期的栈顶元素。如果想要栈顶元素，可以通过top（）取得指向它的一个引用。这样做的结果效率更高，因为传统的pop（）函数必须返回一个值而不是一个引用，因此调用拷贝构造函数。更重要的是，这是异常安全的（exception safe），就像我们在第1章中讨论的那样。如果pop（）在改变栈状态的同时试图返回栈顶元素，那么在元素的拷贝构造函数中产生的某个异常就会导致元素的丢失。在使用stack（或者一个priority_queue，将在稍后描述）时，可以高效地查阅top（），就像你希望得那么快，然后明确使用pop（）将栈顶元素丢弃。（也许，如果使用一些不同于大家熟悉的“pop”这样的术语来定义函数，解释起来可能会更清楚一点儿。）

stack模板有一个简单的接口—本质上就是在较早前看到的那些成员函数。因为对于一个stack来说，只有访问其栈顶元素才有意义，没有提供能够遍历它的迭代器。也没有复杂的初始化形式，但是如果需要这样做的话，可以使用stack的底层容器。比如，假定有一个函数，期望stack的接口，但是在程序的其余部分需要将对象存储在list中。下面的程序存储文件中的每一行，与该行中的前导空白字符的个数一起存储。（可以想象把它作为对源代码执行某种重新格式化操作的出发点。）

需要stack接口的函数仅仅发送每个top（）对象到一个ostream，然后通过调用pop（）将其删除。Line类判断前导空白字符的个数，然后存储没有这些前导空白字符的行的内容。ostream operator＜＜重新插入前导空白字符，因此该行能够被正确地打印出来，但是能很容易地通过改变lspaces的值来改变空白字符的个数。（做这件事的成员函数没有在这里显示。）在main（）函数中，输入文件被读入到list＜Line＞，然后链表中的每一行都被复制到一个stack，该stack被送到stackOut（）函数中。

不能从头至尾对一个stack进行迭代；这就强调了，当创建一个stack时，只能希望对其进行stack操作。可以使用一个vector及其back（）、push_back（）和pop_back（）成员函数获得等价的“堆栈”功能，还拥有vector的所有附加的功能。程序Stack1.cpp可以重写成如下形式：

这个程序产生像Stack1.cpp一样输出，但现在还可以进行与vector一样的操作。list也可以将元素压入前端，但是它通常比与vector一起使用push_back（）的效率低。（另外，对于将元素压入前端的操作，deque通常比list的效率更高。）