stack<T, Sequence>



分类：容器、适配器	组件类型：类型

说明

Astack是一个适配器，它提供 Container 功能的一个受限制子集：它提供插入、删除，以及检查堆栈顶部的元素。Stack是一个 “后进先出” (LIFO) 数据结构：位于stack顶部的元素是最近添加的。 [1]Stack不允许通过其元素进行迭代。 [2]

Stack是一个容器适配器，这意味着它在一些底层容器类型的基础上实现。默认情况下，该底层类型是deque，但可以显式选择一个不同的类型。

示例

int main() {
  stack<int> S;
  S.push(8);
  S.push(7);
  S.push(4);
  assert(S.size() == 3);

  assert(S.top() == 4);
  S.pop();

  assert(S.top() == 7);
  S.pop();

  assert(S.top() == 8);
  S.pop();

  assert(S.empty());
}

定义

在标准头文件中定义 stack，以及非标准向后兼容性头文件中定义 stack.h。

模板参数

参数	说明	默认值
`T`	存储在堆栈中的对象的类型。
`Sequence`	用于实现堆栈的底层容器的类型。	`deque<T>`

模型

Assignable, Default Constructible

类型要求

T的模型为 Assignable。
Sequence的模型为 Back Insertion Sequence。
Sequence::value_type与T.
相同类型，如果operator==被使用，那么T的模型为 Equality Comparable
相同类型，如果operator<被使用，那么T的模型为 LessThan Comparable。

公共基类

无。

成员

成员	在何处定义	说明
`value_type`	`stack`	见下文。
`size_type`	`stack`	见下文。
`stack()`	Default Constructible	默认构造函数。创建一个空的`stack`.
`stack(const stack&)`	Assignable	拷贝构造函数。
`stack& operator=(const stack&)`	Assignable	赋值运算符。
`bool empty() const`	`stack`	见下文。
`size_type size() const`	`stack`	见下文。
`value_type& top()`	`stack`	见下文。
`const value_type& top() const`	`stack`	见下文。
`void push(const value_type&)`	`stack`	见下文。
`void pop()` [3]	`stack`	见下文。
`bool operator==(const stack&, const stack&)`	`stack`	见下文。
`bool operator<(const stack&, const stack&)`	`stack`	见下文。

新成员

这些成员未在 Assignable 和 Default Constructible 要求中定义，但特定于stack.

成员	说明
`value_type`	中存储的对象的类型`stack`。这与`T`和`Sequence::value_type`.
`size_type`	相同，无符号整型。这与`Sequence::size_type`.
`bool empty() const`	相同`返回值`true`stack`如果`不包含任何元素，以及`false`否则。`S.empty()`相当于`.
`size_type size() const`	返回`stack`.
`value_type& top()`	返回堆栈顶部元素的可变引用。先决条件`empty()`是`不包含任何元素，以及`.
`const value_type& top() const`	返回堆栈顶部元素的常引用。先决条件`empty()`是`不包含任何元素，以及`.
`void push(const value_type& x)`	插入`x`在堆栈顶部。后置条件`size()`将递增`1`并且`top()`将等于`x`.
`void pop()`	移除堆栈顶部的元素。 [3] 先决条件`empty()`是`不包含任何元素，以及`. 后置条件`size()`将递减`1`.
`bool operator==(const stack&, const stack&)`	比较两个堆栈是否相等。如果两个堆栈包含相同数量的元素并且逐个元素相等，则这两个堆栈相等。这是一个全局函数，而不是成员函数。
`bool operator<(const stack&, const stack&)`	两个堆栈的字典顺序。这是一个全局函数，而不是成员函数。

备注

[1] 堆栈是一种标准数据结构，所有算法书中都有讲到。例如，参见 Knuth 的 2.2.1 节。（D. E. Knuth，《计算机编程的艺术。第一卷：基本算法》，第二版。Addison-Wesley，1973。）

[2] 这是唯一一个存在stack的原因。请注意，任何前端插入序列或后端插入序列都可以用作堆栈；例如，在 vector 的情况下，堆栈操作是成员函数back, push_back并且pop_back. 使用容器适配器stack唯一的原因是为了明确你仅执行堆栈操作，不执行任何其他操作。

[3] 人们可能想知道为什么pop()返回void而不是value_type。也就是说，为什么必须使用top()和pop()检查并移除顶部元素，而不是将两者组合到一个成员函数中？事实上，这种设计有充分的理由。如果pop()返回顶部元素，则必须按值而不是按引用进行返回：按引用返回会创建一个悬空指针。但是，按值返回效率低下：它至少涉及一次冗余的复制构造函数调用。由于pop()无法以既高效又正确的方式返回值，因此它不返回值并要求客户端使用top()检查堆栈顶部的值更为合理。

另请参见

队列, 优先队列, 容器, 序列