栈 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; // 栈顶 }

下面是 Stack 类模板的实现：

#include "node.hpp"

template <typename ElementType>
class Stack {
public:
    Stack() : top(nullptr) {}  // 构造函数
    ~Stack();                   // 析构函数
    void push(ElementType obj); // 将新元素入栈
    void pop();                 // 将栈顶元素出栈
    ElementType getTop() const; // 返回栈顶元素
    bool isEmpty() const;       // 判断栈是否为空

private:
    Node<ElementType> *top;     // 栈顶指针
};

// 析构函数
template <typename ElementType>
Stack<ElementType>::~Stack() {
    Node<ElementType> *temp;
    while (top != nullptr) {
        temp = top;
        top = top->next;
        delete temp;
    }
}

// 将新元素入栈
template <typename ElementType>
void Stack<ElementType>::push(ElementType obj) {
    Node<ElementType> *newNode = new Node<ElementType>;
    newNode->element = obj;
    newNode->next = top;
    top = newNode;
}

// 将栈顶元素出栈
template <typename ElementType>
void Stack<ElementType>::pop() {
    if (top != nullptr) {
        Node<ElementType> *temp = top;
        top = top->next;
        delete temp;
    }
}

// 返回栈顶元素
template <typename ElementType>
ElementType Stack<ElementType>::getTop() const {
    if (top != nullptr) {
        return top->element;
    }
    throw std::out_of_range("Stack is empty");
}

// 判断栈是否为空
template <typename ElementType>
bool Stack<ElementType>::isEmpty() const {
    return top == nullptr;
}

注意，这里我们使用了 node.hpp 中的链表结构作为栈的底层实现。在 push() 函数中，我们创建一个新的结点并将其指向当前的栈顶元素，然后将栈顶指针指向这个新结点；在 pop() 函数中，我们将栈顶指针指向当前栈顶元素的下一个结点，并删除原来的栈顶结点；在 getTop() 函数中，我们返回栈顶元素的值；在 isEmpty() 函数中，我们简单地判断栈顶指针是否为 nullptr。