C++中vector的应用

vector的实现与数组相似。我们知道，数组的元素都是排列在一起的，所以随机访问某一个元素只需要首个元素的地址加上偏移量就能够定位到。而在删除数组中元素的时候，我们需要将被删除元素后面的所有元素往前移动一格，不然数组会有空隙。因此，我们知道vector适用于元素随机访问多但添加、删除中间元素少的程序。

动手写12.2.4

动手写12.2.4展示了使用vector判断单词是不是anagram的应用。运行结果如图12.2.3所示：

图12.2.3　判断anagram程序

在这个程序中我们需要统计有限的字母出现的次数，所以可以定义一个确定大小为26的vector。由于vector支持快速随机访问，我们可以高效地频繁修改字母出现的次数。这个程序也可以通过关联容器map实现，但是这里由于字母数量是确定的且值很小，使用vector反而更高效。

虽然vector在中间添加和删除元素的效率很低，但是在末尾添加和删除元素还是很直观有效的，我们可以用现成的push_back（）和pop_back（）函数，还可以把vector当作栈来使用。栈（Stack）是一种满足只从线性数据集合一端添加和删除元素的数据结构，这个栈和之前介绍的分配局部变量的内存分区有异同之处。它们添加和删除的行为类似，但是之前介绍的栈是一个具体的内存中的分区，而这里的栈是一个抽象的概念，数据不一定都存在一个地方。栈的操作符合后进先出（LIFO，Last In First Out）原理，而且栈在解决许多问题的时候常有奇效。用现实的例子打比方的话，栈就是一摞盘子，只有拿走了上面的盘子，也就是后放的盘子，才能拿走下面的盘子。

(www.xing528.com)

图12.2.4　栈图解

如图12.2.4所示，栈一开始有3个元素，我们在顶上放入D后又取出D，然后才能取出压在下面的C。

动手写12.2.5

动手写12.2.5展示了一种基于栈的解决有效括号判断的方法。运行结果如图12.2.5所示：

图12.2.5　判断有效括号

因为有效的括号一定是成对出现的，所以我们一定要有相等数量的左括号和右括号，这可以用两个指针分别从左到右遍历的方式解决，但是这不一定是有效率的。如果遇到很多左括号叠在一起的情况，我们就可以用栈先将它们叠起来，后面看到相应的右括号再抵消掉。这类需要暂时将一些数据搁置起来等进入下一层再处理的问题有些像函数调用，都可以用栈来解决。