C++实现栈：从基础到高级 |21xrx.com

C++实现栈：从基础到高级

2023-07-01 13:02:16 深夜i -- --

C++语言栈数据结构基础实现高级实现算法优化

栈是一种基本的数据结构，它具有后进先出的特点。在计算机科学和编程中，栈经常被用来处理递归调用，表达式计算和其他需要后进先出访问的情况。C++是一种非常流行的编程语言，它的面向对象特性使得实现栈变得更加容易。在本文中，我们将介绍从基础到高级的C++实现栈的方法。

1. 基础实现

首先，我们需要定义栈的数据结构。在C++中，可以使用STL中的std::stack容器，也可以自己实现一个栈类。在本文中，我们将使用自己实现的栈类。

栈类必须具有以下基本功能：

1.入栈(push)：向栈中添加一个元素。

2.出栈(pop)：从栈中移除并返回栈顶的元素。

3.查询栈顶元素(top)：返回栈顶的元素。

4.查询栈的大小(size)：返回栈中元素的数量。

下面是一个基础的栈类的代码实现：


class Stack {
 private:
  int *items;
  int top_index;
  int max_size;
 public:
  Stack(int size) {
    items = new int[size];
    top_index = -1;
    max_size = size;
  }
  ~Stack() {
    delete[] items;
  }
  bool is_full() {
    return top_index == max_size - 1;
  }
  bool is_empty() {
    return top_index == -1;
  }
  void push(int item) {
    if (is_full()) {
      throw std::overflow_error("Stack is full!");
    }
    items[++top_index] = item;
  }
  int pop() {
    if (is_empty()) {
      throw std::out_of_range("Stack is empty!");
    }
    return items[top_index--];
  }
  int top() {
    if (is_empty()) {
      throw std::out_of_range("Stack is empty!");
    }
    return items[top_index];
  }
  int size() {
    return top_index + 1;
  }
};

2. 高级实现

在基础实现中，我们只实现了一个整数类型的栈。但是，我们可以使用C++的模板特性来实现通用的栈类，使得栈可以存储任意类型的数据。我们只需要将int替换为typename T即可：


template<typename T>
class Stack {
 private:
  T *items;
  int top_index;
  int max_size;
 public:
  Stack(int size) {
    items = new T[size];
    top_index = -1;
    max_size = size;
  }
  ~Stack() {
    delete[] items;
  }
  bool is_full() {
    return top_index == max_size - 1;
  }
  bool is_empty() {
    return top_index == -1;
  }
  void push(T item) {
    if (is_full()) {
      throw std::overflow_error("Stack is full!");
    }
    items[++top_index] = item;
  }
  T pop() {
    if (is_empty()) {
      throw std::out_of_range("Stack is empty!");
    }
    return items[top_index--];
  }
  T top() {
    if (is_empty()) {
      throw std::out_of_range("Stack is empty!");
    }
    return items[top_index];
  }
  int size() {
    return top_index + 1;
  }
};

这个栈类可以存储任何数据类型，如下面的例子所示：


Stack<int> int_stack(10);
Stack<std::string> string_stack(10);
int_stack.push(1);
int_stack.push(2);
int_stack.push(3);
string_stack.push("Hello");
string_stack.push("World");
int_stack.pop();
string_stack.pop();

3. 总结

实现栈是编程中的一个基本技能，尤其是在处理复杂问题时。在本文中，我们展示了从基础到高级的C++实现栈的方法。我们使用了简单的整数类型的栈和通用的栈类，可以存储任何类型的数据。如果你正在学习C++编程，实现一个栈是一个很好的练习，它可以帮助你理解C++的语法和面向对象编程的概念。

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

下一篇: C++冒泡排序算法代码

评论区

()

相似文章