C++实现堆栈的方法 |21xrx.com

C++实现堆栈的方法

2023-07-07 04:56:59 深夜i -- --

C++ 堆栈实现方法

堆栈是一种常见的数据结构，常用于需要先进后出（Last In First Out，LIFO）的场合，例如计算机中的函数调用、表达式求值、图形处理等。在C++中，实现堆栈非常简单，可以通过使用STL（标准模板库）中的stack类或者自定义堆栈类来实现。

使用STL中的stack类

STL中的stack类是一种标准容器，它提供了push()、pop()、top()、empty()等函数，可以方便地实现堆栈的基本功能。

首先，需要引入stack库：


#include <stack>

然后，可以定义一个堆栈：


std::stack<int> myStack;

在这个例子中，我们定义了一个存放整数的堆栈。

接下来，可以使用push()函数将数据压入堆栈：


myStack.push(1);
myStack.push(2);
myStack.push(3);

然后，可以使用top()函数来查看堆栈顶部的元素：


std::cout << myStack.top() << std::endl;

输出为3，这是因为3是最后一个被压入堆栈的元素。

可以使用pop()函数将堆栈顶部的元素弹出：


myStack.pop();

现在，堆栈顶部的元素为2，因为3已经被弹出。

最后，可以使用empty()函数检查堆栈是否为空：


if (myStack.empty())
  std::cout << "Stack is empty.";

如果堆栈为空，将输出“Stack is empty.”。

自定义堆栈类

除了STL的stack类，我们也可以自定义一个堆栈类。堆栈可以用数组或链表来实现，下面是数组实现的一个例子。

首先，需要定义一个堆栈类：


template<typename T>
class Stack {
private:
  T* data;
  unsigned int size;
  unsigned int capacity;
public:
  Stack(unsigned int capacity);
  ~Stack();
  void push(T element);
  T pop();
  T top();
  bool empty();
  bool full();
};

在这个例子中，堆栈类使用了模板，可以实现任何类型的堆栈。

然后，需要在堆栈类的构造函数中初始化数据：


template<typename T>
Stack<T>::Stack(unsigned int capacity) {
  this->capacity = capacity;
  size = 0;
  data = new T[capacity];
}

在此例中，使用new操作符动态地分配了一个T类型的数组，用于存储堆栈中的元素。size变量用于记录当前堆栈中的元素数量，capacity变量用于记录堆栈的最大容量。

接下来，需要实现压入元素、弹出元素、查看堆栈顶部元素、检查堆栈是否为空或满的函数：


template<typename T>
void Stack<T>::push(T element) {
  if (size >= capacity)
    return;
  
  data[size++] = element;
}
template<typename T>
T Stack<T>::pop() {
  if (size == 0) {
    return T();
  }
  return data[--size];
}
template<typename T>
T Stack<T>::top() {
  if (size == 0) {
    return T();
  }
  return data[size - 1];
}
template<typename T>
bool Stack<T>::empty()
  return size == 0;
template<typename T>
bool Stack<T>::full()
  return size == capacity;

在上述函数中，如果堆栈已满或为空，则不能进行push()、pop()、top()等操作。empty()函数和full()函数则用于检查堆栈是否为空或满。

最后，需要在堆栈类的析构函数中释放动态分配的数组内存：


template<typename T>
Stack<T>::~Stack() {
  delete[] data;
}

到这里，我们就完成了自定义堆栈类的编写。

总结

在C++中，使用STL中的stack类，或者自定义堆栈类，都可以实现堆栈的基本功能。自定义堆栈类需要考虑边界情况，例如堆栈已满或为空的情况。堆栈是一种常见的数据结构，为程序员提供了一种方便的数据存储和访问方式。

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

下一篇: C++实现：从n个正整数中选择组成最大的偶数

评论区

()

相似文章