栈(stack)

什么是栈？

栈是一种线性的数据结构，其是一种运算受限（限定仅在表尾进行插入和删除的线性表）的线性表。栈的结构类似下图的容器：

如上图所示，栈的结构就像一个端封闭，另一端开口的容器，往容器放入小球（对应栈中的元素），先放入的小球就越靠近容器的底部，最早进入的小球对应的位置就是栈底（bottom），最后放入的小球对应的位置就是栈顶（top），放入小球的动作就叫做入栈（push）；取出小球的时候，只能按照放入顺序相反的顺序来取，即先取后放入的，再去先放入的，每次取小球的动作就叫做出栈（pop）。由于栈的单端口进出的限制，决定了栈中的元素只能先进后出（FILO, First In Last Out）。栈的数据结构可以使用数组来实现，也可以用链表来实现，具体如下图所示：

栈的基本操作和应用

入栈（push)

入栈就是把元素存放入栈中，由于栈的结构只允许从一次存放元素，所以新元素的存入后所在的位置就是该栈新的栈顶，我们以栈的数组实现为例，入栈的过程如下图所示：

出栈（pop)

出栈就是把元素从栈中弹出，同样的由于栈结构单端进出的限制，出栈时候的元素就是栈顶对应的元素，取出元素后，出栈元素前面的那个元素对应的位置将变成新的栈顶。出栈的过程如下：

入栈和出栈的复杂度和应用场景

由于栈的后进先出的特性，使得入栈和出栈只会影响到栈中最后一个元素，不会涉及到其他元素的移动，因此入栈和出栈的时间复杂都为$O(1)$。同样的，栈的先入后出的特性，也使得栈不能拥有遍历、随机访问和随机插入的功能。

由于栈的特殊结构，栈常用于以下场景：

• 逆序输出：由于栈先入后出的特性，使用栈结构可以轻松实现逆序输出的操作。

• 语法检测：对于一些成对出现的符号，如"[]“、”()"等，凡是遇到符号的前半部分，即入栈（push）该符号，凡是遇到括号后半部分的，就与栈顶元素进行匹配，如果匹配成功，则出栈（pop），否则就是匹配失败，语法错误。

• 数字进制转换：顺序计算，继续结果逆序输出。

栈的应用场景还有很多，这里就不一一举例，实际上栈的应用都是基于栈的先入后出的特性。

类模板std::satck

stack类是C++标准库提供的一个容器适配器，它给使用者提供了栈的功能，实现的栈的先进后出（FILO）的数据结构，并提供了特定的函数集合，其定义如下所示：

template<
    class T,
    class Container = std::deque<T>
> class stack;

该类模板在头文件<stack>中定义。

形参T和Container

• T：代表存储元素的类型
• Container：用于存储元素的底层容器类型。该类型必须满足序列容器的要求，同时该容器类型能够提供通常语义下的back()、push_back()和pop_back()函数。默认情况下使用标准容器std::deque。满足该要求的标准容器还有std::vector和std::list。

成员函数

元素访问

访问栈顶元素使用top()函数，该函数的定义如下：

reference top();
const_reference top() const;

该函返回栈中栈顶元素的引用。实际上调用的就是底层容器的back()。

栈的容量

• size()：返回底层容器中的元素数 。实际上调用的就是底层容器的size()。

• empty()：检查底层容器是否为空，如果为空返回true，否则false。实际上调用的就是底层容器的empty()。

栈的修改

• push：向栈中推入元素。其函数声明如下：

  void push( const value_type& value );
  void push( value_type&& value ); //C++11 起
  

• emplace：推入新元素到栈中，与push不同的是该函数是原位构造元素（直接在容器内构造对象，不用拷贝一个复制品再使用），既不进行也不进行复制操作。其函数声明如下：

  template< class... Args >
  void emplace( Args&&... args ); //C++11 起 C++17 前
  
  template< class... Args >
  decltype(auto) emplace( Args&&... args ); //C++17 起
  

  其中args为转发给元素构造函数的参数。也正是由于emplace的原位构造元素，省去了拷贝构造的过程，使得emplace的效率高于push。

• pop：从栈中移除站定元素。实际上调用的就是底层元素的pop_back()。

• swap：交换栈与另一个栈中的内容，其函数声明如下：

  void swap( stack& other ) noexcept(/* see below */); //C++11 起
  

用法示例

#include <iostream>
#include <stack>
using namespace std;
int main() {
    
  stack<int> s;

  // push()
  s.push(1);
  s.push(2);
  s.push(3);

  cout << "按顺push元素1、2、3后" << endl;
  cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
  cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
  if (!s.empty())
    cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
  else
    cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;

  s.pop();  // 弹出栈顶元素
  cout << "\n弹出栈顶元素3, 即pop()后" << endl;
  cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
  cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
  if (!s.empty())
    cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
  else
    cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;

  s.pop();
  cout << "\n弹出栈顶元素2, 即pop()后" << endl;
  cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
  cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
  if (!s.empty())
    cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
  else
    cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;

  s.pop();
  cout << "\n弹出栈顶元素1, 即pop()后" << endl;
  cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
  cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
  if (!s.empty())
    cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
  else
    cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;

  // swap()操作
  s.emplace(1);
  s.emplace(2);
  s.emplace(3);

  stack<int> s1;

  cout << "\n-----------栈s和s1交换前----------" << endl;
  cout << "\ns的状态: " << endl;
  cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
  cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
  if (!s.empty())
    cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
  else
    cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;

  cout << "\ns1的状态: " << endl;
  cout << "栈s1中元素的数量, 即s1.size() = " << s1.size() << endl;
  cout << "此时, 栈s1是否为空,即s1.empty() = " << s1.empty() << endl;
  if (!s1.empty())
    cout << "此时, 栈s1非空, 栈顶元素,即s1.top() = " << s1.top() << endl;
  else
    cout << "此时, 栈s1为空, 不能使用top访问栈顶元素" << endl;

  s1.swap(s);  // s和s1进行交换

  cout << "\n-----------栈s和s1交换后----------" << endl;
  cout << "\ns的状态: " << endl;
  cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
  cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
  if (!s.empty())
    cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
  else
    cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;

  cout << "\ns1的状态: " << endl;
  cout << "栈s1中元素的数量, 即s1.size() = " << s1.size() << endl;
  cout << "此时, 栈s1是否为空,即s1.empty() = " << s1.empty() << endl;
  if (!s1.empty())
    cout << "此时, 栈s1非空, 栈顶元素,即s1.top() = " << s1.top() << endl;
  else
    cout << "此时, 栈s1为空, 不能使用top访问栈顶元素" << endl;

  return 0;
}

输出结果：

按顺push元素1、2、3后
栈s中元素的数量, 即s.size() = 3
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 3

弹出栈顶元素3, 即pop()后
栈s中元素的数量, 即s.size() = 2
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 2

弹出栈顶元素2, 即pop()后
栈s中元素的数量, 即s.size() = 1
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 1

弹出栈顶元素1, 即pop()后
栈s中元素的数量, 即s.size() = 0
此时, 栈s是否为空,即s.empty() = 1
此时, 栈s为空, 不能使用top访问栈顶元素

-----------栈s和s1交换前----------

s的状态: 
栈s中元素的数量, 即s.size() = 3
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 3

s1的状态: 
栈s1中元素的数量, 即s1.size() = 0
此时, 栈s1是否为空,即s1.empty() = 1
此时, 栈s1为空, 不能使用top访问栈顶元素

-----------栈s和s1交换后----------

s的状态: 
栈s中元素的数量, 即s.size() = 0
此时, 栈s是否为空,即s.empty() = 1
此时, 栈s为空, 不能使用top访问栈顶元素

s1的状态: 
栈s1中元素的数量, 即s1.size() = 3
此时, 栈s1是否为空,即s1.empty() = 0
此时, 栈s1非空, 栈顶元素,即s1.top() = 3

文章首发公众号：iDoitnow如果喜欢话，可以关注一下