LinkedStack.hpp

//链式栈，利用栈的后进先出性质来存路线
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H
#include <iostream>
template <typename T>
struct StackNode{
    T data;
    StackNode* next;
    StackNode(T val): data(val),next(nullptr) {}
};
template <typename T>
class LinkedStack{
    private:
    StackNode<T>* topNode;
    int StackSize;
    public:
    LinkedStack() : topNode(nullptr),StackSize(0) {}
    ~LinkedStack() {while(topNode != nullptr) pop();}
    void push(T val){
        StackNode<T>* newnode = new StackNode<T>(val);//新建 节点
        newnode -> next = topNode;//新入栈的节点指向上一个栈顶,实现逆推
        topNode = newnode;//更新栈顶
        StackSize++;
    }
    void pop(){
        if (topNode == nullptr) return;
        StackNode<T>* tmp = topNode;
        topNode = topNode -> next;
        delete tmp;StackSize--;
    }
    T top(){
        if (empty()) throw std::runtime_error("Stack is empty");
        return topNode -> data;
    }
    int GetSize(){
        return StackSize;
    }
    bool empty(){
        return topNode == nullptr;
    }
};
#endif