cpp_stl_stack

C++ 标准库中的栈容器

• C++ 标准库中的栈容器
  • 1. 创建 stack 对象
    • 1.1 stack()
    • 1.2 stack(const stack&)
  • 2. 元素入栈
  • 3. 元素出栈
  • 4. 取栈顶元素

栈是一个线性表，插入和删除只在表的一端进行。这一端称为栈顶(Stack Top)，另一端则为栈底(Stack Bottom)。堆栈的元素插入称为入栈，元素的删除称为出栈。由于元素的入栈和出栈总在栈顶进行，因此，堆栈是一个后进先出(Last In First Out)表，即 LIFO 表。

C++ STL 的堆栈泛化是直接通过现有的序列容器来实现的，默认使用双端队列 deque 的数据结构，当然，可以采用其他线性结构（vector 或 list等），只要提供堆栈的入栈、出栈、栈顶元素访问和判断是否为空的操作即可。由于堆栈的底层使用的是其他容器，因此，栈可看做是一种适配器，即将一种容器转换为另一种容器(栈容器)。

为了严格遵循堆栈的数据后进先出原则，stack 不提供元素的任何迭代器操作，因此，stack 容器也就不会向外部提供可用的前向或反向迭代器类型。

stack 堆栈容器的 C++ 标准头文件为 stack ，必须用宏语句 “#include <stack>” 包含进来，才可对 stack 堆栈的程序进行编译。

1. 创建 stack 对象

使用堆栈前，先要利用构造函数进行初始化，创建一个堆栈对象，以进行元素的入栈、出栈等操作。

1.1 stack()

默认构造函数，创建一个空的 stack 对象。例如，下面一行代码使用默认的 deque 为底层容器，创建一个空的堆栈对象 s：

stack<int> s;

1.2 stack(const stack&)

复制构造函数，用一个 stack 栈创建一个新的栈。例如，下面的代码利用 s1 ，创建一个以双向链表为底层容器的空堆栈对象 s2。

// stack<int, list<int> >   s1;
stack<int, list<int>> s2(s1);

2. 元素入栈

stack 容器的元素入栈函数为 push 函数。由于 C++ STL 的堆栈函数是不预设大小的，因此，入栈函数就不考虑堆栈空间是否为满，均将元素压入堆栈，从而函数没有标明入栈成功与否的返回值。如下是他的使用原型：

void push(const value_type& x)

3. 元素出栈

stack 容器的元素出栈函数为 pop 函数，由于函数并没有判断堆栈是否为空，才进行元素的弹出，因此，需要自行判断堆栈是否为空，才可执行 pop 函数。 stack 的元素出栈操作是不返回栈顶元素的，需要另外通过取栈顶函数获得。

void pop()

下列的示例代码将栈中所有元素全部出栈

// stack<int> s
while (!s.empty()) {
  s.pop();
}

4. 取栈顶元素

stack 容器的栈顶元素的读取函数为 top 函数，将取出最后入栈的元素，如下是它的使用原型

value_type& top()