C++实现栈 - 数据结构基础之一 |21xrx.com

C++实现栈 - 数据结构基础之一

2023-06-27 11:36:40 深夜i -- --

C++ 实现栈数据结构基础

栈是计算机科学中的一种基本数据结构，它具有后进先出 (LIFO) 的性质。常见的应用场景包括函数调用的调用栈、表达式求值中的运算符栈、以及浏览器中的历史记录。在 C++ 中，我们可以很容易地实现栈这一数据结构。

首先, 定义一个类模板作为栈的容器。这里我们使用一个动态数组 vector 实现。


template <typename T>
class Stack {
 public:
  void push(T val) {
    // 添加元素到数组末尾
    _data.push_back(val);
  }
  T pop() {
    // 弹出末尾元素并返回
    T val = _data.back();
    _data.pop_back();
    return val;
  }
  T top() const {
    // 返回末尾元素
    return _data.back();
  }
  bool empty() const {
    // 判断栈是否为空
    return _data.empty();
  }
  size_t size() const {
    // 返回栈的大小
    return _data.size();
  }
 private:
  std::vector<T> _data;
};

在这个实现中，我们定义了五个方法：

- push: 将一个元素推入栈中

- pop: 弹出栈顶的元素并返回它

- top: 返回栈顶的元素但不弹出

- empty: 判断栈是否为空

- size: 返回栈的大小

这些方法的实现比较简单，核心都是对动态数组向量的操作。

现在，我们可以测试一下这个栈实现：


int main() {
  Stack<int> s;
  s.push(1);
  s.push(2);
  s.push(3);
  std::cout << s.pop() << '\n';  // 3
  std::cout << s.pop() << '\n';  // 2
  std::cout << s.top() << '\n';  // 1
  std::cout << s.pop() << '\n';  // 1
  std::cout << s.empty() << '\n'; // 1
}

在这个测试中，我们首先创建了一个 int 类型的栈。然后，我们依次将数字 1、2、3 推入栈中。接着，我们弹出栈顶的元素并输出它，得到 3；再弹出栈顶元素并输出它，得到 2；然后，我们输出栈顶元素，得到 1；最后，我们依次弹出 1 并检查栈是否为空。

栈是计算机科学中的基本数据结构之一，是许多算法和程序所必需的。在 C++ 中，我们可以通过使用 vector 实现栈，这使得栈的实现变得非常简单。我们只需要实现几个基本的操作方法即可。

上一篇: idea打包java可执行jar包

下一篇: C++和C#有何不同？

评论区

()

相似文章