【C++】容器篇（三）—— stack的基本介绍及其模拟实现

前言：

在之前的学习中我们已经了解了 vector 和 list ，今天我将带领学习的是关于STL库中的 stack的学习！！！

（一）基本介绍

学过数据结构的小伙伴对于 stack 结构应该是不陌生的，最主要的特点便是遵循Last In First Out（LIFO）的规则，这意味着最近添加的项目将首先被删除。

1、基本概念

接下来，我们先从文档来认识，看文档中是如何描述的。

• 链接如下：stack文档介绍

1. 从上我们看出stack是STL库中的一种容器，它用于存储数据，并遵循Last In First Out（LIFO）的规则；
2. 堆栈是一种容器适配器，stack在C++ STL库中实现为一个模板类，提供一组特定的成员函数来访问其元素。

2、容器适配器

此时可能就有很多小伙伴比较好奇什么叫做 “容器适配器”了，在这里我简单的介绍一下：

• ⚔️ 容器适配器（又叫配机器）是STL库中的一类容器，使用已有的容器类来实现适配器的功能，从而提供方便的数据结构 ⚔️

容器适配器包括三种：stack、queue和priority_queue（后两者在后面会给大家介绍）

💨 容器适配器有如下特点：

• 1. 使用现有容器类作为底层实现。
• 2. 基于已有的功能来添加和删除元素（例如push()、pop()、top()等），适用于特定的应用场景。
• 3. 通常具有限制和限制，可以有所优化。

💨 这些容器适配器通常用于特定的数据结构，并简化了它们的实现。以下是简要描述：

• 1. stack：stack是一种LIFO（Last-In-First-Out）容器，只允许在容器的一端插入和删除元素。通过stack，我们可以快速、轻松地实现如撤销、反转等功能。
• 2. queue：queue是一种FIFO（First-In-First-Out）容器，只允许在容器的一端插入元素，在容器的另一端删除元素。通过queue，我们可以快速、轻松地实现如模拟消息队列等功能。
• 3. priority_queue：priority_queue是一个优先级队列，它存储一组具有优先级的值，并按照优先级从高到低排序。通过priority_queue，我们可以快速、轻松地实现如任务调度等功能。

总结来说，容器适配器是为了方便使用STL中的已有容器类而设计的。通过简洁的接口，容器适配器提供了更高层次的容器类，简化了某些数据结构的实现。

（二）基本使用

接下来，我先通过具体的使用来带大家先感受一下用法是如何的。

• 具体如下：

void test_1()
{
  stack<int> str;
  // 在栈顶添加元素
  str.push(1);
  str.push(2);
  str.push(3);
  str.push(4);
  str.push(5);
  //栈顶元素
  if (!str.empty())
  {
    cout << str.top() << " " << str.size() << endl;;
  }
  // 从栈顶弹出元素
  str.pop();
  // 获取栈顶元素
  cout << str.top() << endl;
  // 检查栈是否为空
  if (str.empty())
  {
    cout << "Stack is empty" << endl;
  }
  else
  {
    cout << "Stack is not empty" << endl;
  }
  // 获取栈的大小
  cout << "Stack size is " << str.size() << endl;
}

• 结果如下：

解释说明：

• 1、在上述代码中，我们先往栈里面插入了5个元素；
• 2、紧接着，我们就验证了开头说的说的是否符合后进先出的规则，最终结果也成功的表明了相应的观点；
• 3、接下来，经过pop 操作之后，在打印栈顶元素，我们可以发现此时的结果为4，也符合相应的预期；
• 4、接下来，就是对其的栈是否为空的基本判断，以及stack大小的计算操作。

（三）stack模拟实现

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

💨 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

1、stack的使用

2、 模拟实现

💨 从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

• 1️⃣push()

void push(const T& x)
{
  _vv.push_back(x);
}

• 2️⃣pop()

void pop()
{
  if (!_vv.empty())
  {
    _vv.pop_back();
  }
}

• 3️⃣top()

const T& top()
{
  return _vv.back();
}

• 4️⃣empty()

bool empty()
{
  return _vv.empty();
}

• 5️⃣size()

size_t size()
{
  return _vv.size();
}

整体代码如下：

#pragma once
#include<vector>
#include<list>
namespace zp
{
  template<class T, class Container>
  class stack
  {
  public:
    void push(const T& x)
    {
      _vv.push_back(x);
    }
    void pop()
    {
      if (!_vv.empty())
      {
        _vv.pop_back();
      }
    }
    const T& top()
    {
      return _vv.back();
    }
    bool empty()
    {
      return _vv.empty();
    }
    size_t size()
    {
      return _vv.size();
    }
  private:
    Container _vv;
  };
}

• 当我们要实现数组栈、链式栈，我们还需要自己实现吗，在这里就可以使用适配器模式，使用已有的容器对其进行封装操作；
• 但是当我们像 vector<T> _vv 或 list<int> _vv  这样定义时其实还没有真正的实现适配。就像平常生活中的电源适配器一样的，它可以把220v的转化为 10v 或者 20v ，因此在定义模板增加了一个【Container】的模板参数，即  ⚔️ template<class T, class Container> ⚔️ ，当然当我们想实现数组栈还可以这样  ⚔️ template<class T, class Container = vector<T>> ⚔️

当我们想使用时直接用即可：

stack<int, vector<int>> str;
stack<int, list<int>> str;
stack<int> str;

（四）题目讲解

1、逆波兰表达式求值

• 链接如下：150. 逆波兰表达式求值

题目如下：

t

解题思路：

首先，在正式的解题之前，我们先认识一下什么叫做逆波兰表达式。

💨 逆波兰表达式是一种计算表达式的方式，也称为后缀表达式

• 它的特点是把操作符写在操作数的后面，从左到右扫描表达式，遇到操作数就把它压入栈中，遇到操作符就从栈中取出所需的操作数进行运算，运算结果再存入栈中；
• 最后栈中只剩下一个数，即该表达式的计算结果。

首先，我先举例分析一波例如，表达式tokens = ["2","1","+","3","*"] 的运算过程如下：

1. 扫描到数字2，将其压入栈中。
2. 扫描到数字1，将其压入栈中。
3. 扫描到符号"+"，从栈中弹出操作数4和3，计算2+1=3，将结果3压入栈中。
4. 继续扫描，将数字3压入栈中。
5. 扫描到符号" * "，从栈中弹出操作数3和3，计算3*3=9，将结果9压入栈中。
6. 表达式扫描完毕，栈中剩下唯一数字9，即该表达式的计算结果。

因此以下是逆波兰表达式的解题思路：

1. 定义一个栈s，用于存放操作数和中间运算结果。
   
2. 从左到右扫描表达式，遇到数字就把它压入栈中。
   
3. 遇到操作符时，从栈中弹出两个操作数进行运算。运算结果再压入栈中。
   
4. 重复步骤2和3，直到表达式扫描完毕。
   
5. 栈中剩下的唯一数字就是该表达式的计算结果。
   

代码展示：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (auto e : tokens) {
            if (e == "+" || e == "-" || e == "*" || e == "/") {
                int b = s.top();
                s.pop();
                int tmp = s.top();
                s.pop();
                if (e == "+") 
                    s.push(tmp + b);
                else if (e == "-") 
                    s.push(tmp - b);
                else if (e == "*") 
                    s.push(tmp * b);
                else if (e == "/") 
                    s.push(tmp / b);
            } 
            else {
                s.push(stoi(e));
            }
        }
    return s.top();
    }
};

（五）总结

到此，关于本期stack的讲解便到此结束了。接下来，总结一下本期都学到了什么吧！！！

• 1、首先，我们通过文档的介绍了解了有关STL库关于stack的基本介绍，知道了在库中是一个模板类，其次给大吉介绍了有关容器适配器的基本知识；
• 2、接下来，我们简单的使用了一下stack，知道了用法；
• 3、紧接着，我们手动的去实现了一个stack，相比之前的stack的实现就显得十分简单了；
• 4、最后，有了基本概念，在带着大家刷了几道题以巩固学到的关于stack的知识。

以上便是本文的基本内容，感谢大家的阅读与支持！！！