【数据结构】链栈的基本操作(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;//定义头指针
    
}
© 版权声明
THE END
点赞12 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容