C++ stack(STL stack)

╰+攻爆jí腚メ 2023-06-11 03:11 110阅读 0赞

容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。  
  
stack<T>容器适配器中的数据是以 LIFO (后进先出)的方式组织的，这和自助餐馆中堆叠的盘子、箱子中的一堆书类似。图 1 展示了一个理论上的 stack 容器及其一些基本操作。只能访问 stack 顶部的元素；只有在移除 stack 顶部的元素后，才能访问下方的元素。  
![format_png][]  
图 1 stack 容器的基本操作

stack 容器有广泛的应用。例如，编辑器中的 undo (撤销)机制就是用堆栈来记录连续的变化。撤销操作可以取消最后一个操作，这也是发生在堆栈顶部的操作。编译器使用堆栈来解析算术表达式，当然也可以用堆栈来记录 [C++][C] 代码的函数调用。下面展示了如何定义一个用来存放字符串对象的 stack 容器：

std::stack<std::string> words;

stack 容器适配器的模板有两个参数。第一个参数是存储对象的类型，第二个参数是底层容器的类型。stack<T> 的底层容器默认是 deque<T> 容器，因此模板类型其实是 stack<typename T, typename Container=deque<T>>。通过指定第二个模板类型参数，可以使用任意类型的底层容器，只要它们支持 back()、push\_back()、pop\_back()、empty()、size() 这些操作。下面展示了如何定义一个使用 list<T> 的堆栈：

std::stack<std::string,std::list<std::string>> fruit;

创建堆栈时，不能在初始化列表中用对象来初始化，但是可以用另一个容器来初始化，只要堆栈的底层容器类型和这个容器的类型相同。例如：

std::list<double> values {1.414, 3.14159265, 2.71828};
    std::stack<double,std::list<double>> my_stack (values);

第二条语句生成了一个包含 value 元素副本的 my\_stack。这里不能在 stack 构造函数中使用初始化列表；必须使用圆括号。如果没有在第二个 stack 模板类型参数中将底层容器指定为 list，那么底层容器可能是 deque，这样就不能用 list 的内容来初始化 stack；只能接受 deque。  
  
stack<T> 模板定义了拷贝构造函数，因而可以复制现有的 stack 容器：

std::stack<double,std::list<double>>copy_stack {my_stack}

copy\_stack 是 my\_stack 的副本。如你所见，在使用拷贝构造函数时，既可以用初始化列表，也可以用圆括号。

## 堆栈操作 ##

和其他序列容器相比，stack 是一类存储机制简单、所提供操作较少的容器。下面是 stack 容器可以提供的一套完整操作：

*  top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
 *  push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push\_back() 函数完成的。
 *  push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push\_back() 函数完成的。
 *  pop()：弹出栈顶元素。
 *  size()：返回栈中元素的个数。
 *  empty()：在栈中没有元素的情况下返回 true。
 *  emplace()：用传入的参数调用构造函数，在栈顶生成对象。
 *  swap(stack<T> & other\_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

stack<T> 模板也定义了复制和移动版的 operator=() 函数，因此可以将一个 stack 对象赋值给另一个 stack 对象。stack 对象有一整套比较运算符。比较运算通过字典的方式来比较底层容器中相应的元素。字典比较是一种用来对字典中的单词进行排序的方式。依次比较对应元素的值，直到遇到两个不相等的元素。第一个不匹配的元素会作为字典比较的结果。如果一个 stack 的元素比另一个 stack 的多，但是所匹配的元素都相等，那么元素多的那个 stack 容器大于元素少的 stack 容器。

[format_png]: /images/20230531/6c3d36254ed049eeb21ff86933ee21eb.png
[C]: http://c.biancheng.net/cplus/