描述 栈 Stack 是一种先入后出的数据结构，最先入栈的元素称为栈底，最后入栈的元素称为栈顶。为了方便，可用 node.hpp 中的链表结构实现栈，并用链表头指向栈顶元素。 根据下述定义，请实现一个类模板 Stack ，使其可以保存不同类型的数据。 template <typename ElementType> //genericStack.h class Stack{ public: Stack(); ~Stack(); void push(ElementType obj); //将新元素入栈 void pop(); //将栈顶元素出栈 ElementType getTop() const; //返回栈顶元素 bool isEmpty() const; //判断栈是否为空 private: struct Node{ // 栈结点类型 ElementType element; // 结点中存放的元素 Node *next; // 指向下一结点的指针 }; Node *top; // 栈顶 } template <typename ElementType> //genericStack.h class Stack{ public: Stack(); ~Stack(); void push(ElementType obj); //将新元素入栈 void pop(); //将栈顶元素出栈 ElementType getTop() const; //返回栈顶元素 bool isEmpty() const; //判断栈是否为空 private: struct Node{ // 栈结点类型 ElementType element; // 结点中存放的元素 Node *next; // 指向下一结点的指针 }; Node *top; // 栈顶 } ​ Sample Output 8 7 6 5 4 3 2 1

以下是实现栈的代码示例：

#include "node.hpp"

template <typename ElementType>
class Stack{
public:
  Stack() {
    top = nullptr; // 初始化栈顶指针为空
  }

  ~Stack() {
    while (!isEmpty()) {
      pop(); // 释放所有结点
    }
  }

  void push(ElementType obj) {
    Node *newNode = new Node; // 创建一个新结点
    newNode->element = obj; // 将元素存储到结点中
    newNode->next = top; // 新结点的 next 指针指向当前的栈顶
    top = newNode; // 更新栈顶指针
  }

  void pop() {
    if (!isEmpty()) {
      Node *temp = top; // 保存当前的栈顶指针
      top = top->next; // 更新栈顶指针
      delete temp; // 释放当前的栈顶结点
    }
  }

  ElementType getTop() const {
    if (!isEmpty()) {
      return top->element; // 返回栈顶元素
    }
    throw std::out_of_range("Stack is empty"); // 抛出异常
  }

  bool isEmpty() const {
    return top == nullptr; // 如果栈顶指针为空，则认为栈为空
  }

private:
  struct Node{
    ElementType element;
    Node *next;
  };
  Node *top;
};

使用示例：

#include <iostream>
#include "genericStack.h"

int main() {
  Stack<int> s;

  for (int i = 1; i <= 8; i++) {
    s.push(i); // 将 1 到 8 入栈
  }

  while (!s.isEmpty()) {
    std::cout << s.getTop() << " "; // 输出栈顶元素
    s.pop(); // 出栈
  }

  std::cout << std::endl; // 换行

  return 0;
}

输出结果为：

8 7 6 5 4 3 2 1