【数据结构】链栈的基本操作（C++实现）

什么是链栈

链栈是一种基于链表实现的栈（Stack）数据结构。栈是一种后进先出（Last In, First Out，LIFO）的数据结构，而链栈通过链表的形式来组织栈中的元素。链栈与顺序栈相比，不需要预先分配固定大小的内存空间，因此能够更灵活地处理栈的大小。链栈的主要特点是使用链表节点来存储栈中的元素，并通过一个栈顶指针（Top）来指示链表的头部。

链栈的定义

//链栈
typedef struct Snode{
    double data;
    struct Snode *next;
}Snode,*LinkStack;

链栈不需要空的头节点

链栈的初始化

//初始化
bool InitStack(LinkStack &s){
    s=nullptr;
    return true;
}

入栈

入栈是将新元素节点压入栈顶，将新元素节点插入到第一个节点的前面，然后修改栈顶指针

//入栈
bool Push(LinkStack &s,double e){
    LinkStack p;
    p=new Snode;
    p->data=e;
    p->next=s;
    //修改栈顶，相当于链表头插
    s=p;
    return true;
}

出栈

出栈是把栈顶元素删除，栈顶指向下一个节点，释放空间

//出栈
bool Pop(LinkStack &s,double &e){
    LinkStack p;
    if (s==nullptr){
        return false;//栈空了
    }
    //获取到数据，出栈
    e=s->data;
    //待删除节点p
    p=s;
    //栈顶指向下一个
    s=s->next;
    //删除旧栈顶
    delete p;
    return true;
}

取栈顶

把栈顶元素复制一份，栈顶指针不变

//取栈顶
double GetTop(LinkStack s){
    if (s!=nullptr){
        return s->data;
    }
    else{
        return -1;
    }
}
int main(){
    LinkStack s;//定义头指针
    
}