数据结构：链式栈的基本操作

叁歲伎倆 2022-05-27 12:10 304阅读 0赞

采用链式存储的栈称为链式栈或者链栈，采用单向链表实现，链栈由一个个结点构成，结点包括数据域和指针域两部分。数据域存放链栈中的元素，指针域表示元素之间的关系。插入和删除元素的一端称为栈顶，栈顶由栈顶指针top指示，带头结点的链栈，栈顶指针top始终指向头结点，头结点的指针始终指向链栈的第一个结点。与顺序栈相比，链栈的结点空间可以动态申请，因此，不存在栈满上溢的情况。

--------------------

链栈的基本操作包括：

*  链栈的初始化操作。链栈的初始化操作就是把链栈初始化为空，设栈顶指针为top，初始化时，不带头结点`top==NULL;`带头结点`top->next ==NULL;`
 *  判断链栈是否为空。判断链栈是否为空，就是判断链栈的头结点指针域是否为空，即：`top->next ==NULL;`带头结点，不带头结点的链栈栈空条件为：`top==NULL;`
 *  进栈操作。进栈操作就是将数据元素data插入到链栈的栈顶，就是将新结点插入到链表的第一个结点之前，将新结点插入到链表中分为3个步骤`p->data = data; p->next = top->next; top->next = p;`p为指向新结点的指针；
 *  出栈操作。出栈操作就是将栈的第一个结点删除，并将结点元素赋值给data，在元素出栈前要判断栈是是否为空；
 *  取栈顶元素。取栈顶元素就是把栈顶的元素取出，并返回。在去栈顶元素之前，同样要判断栈是否为空；
 *  求链栈的长度。求链表的长度就是返回链栈中的元素个数，从栈顶指针开始，通过指针域找到下一个结点，并使用变量计数，直到栈底为止；
 *  销毁链栈操作。链栈的空间是动态申请的，在程序结束时要把这些结点空间通过free函数释放；
 *  打印栈中元素。打印栈中元素即：将栈中元素输出。  
    
    
    --------------------

#### 实现带头结点的链栈的基本操作源代码 ####

#include<stdio.h>
    #include<stdlib.h>
    #include<Windows.h>
    
    typedef int DataType;
    
    typedef struct Node
    {
        DataType data;
        struct Node* next;
    }LStackNode,*LinkStack;
    
    //链栈的初始化
    
    void InitStack(LinkStack* top)
    {
        if ((*top = (LinkStack)malloc(sizeof(LStackNode))) == NULL)//为头结点开辟一个存储空间
        {
            exit(-1);
        }
        (*top)->next = NULL; //将链栈的头结点指针域置为空
    }
    
    //判断链栈是否为空
    int StackEmpty(LinkStack top)
    {
        if (top->next==NULL)       
        {
            return 1;
        }
        return 0;
    }
    
    //进栈操作
    
    void PushStack(LinkStack top, DataType data)
    {
        LStackNode*  p;
        p = (LStackNode*)(malloc(sizeof(LStackNode))); 
        if (p == NULL)
        {
            printf("内存分配失败！\n");
        }
        else
        {
            p->data = data;
            p->next = top->next;
            top->next = p;
        }
    }
    
    //出栈操作
    
    void PopStack(LinkStack top,DataType* data)
    {
        LStackNode* p;
        p = top->next;
        if (p==NULL)
        {
            printf("栈为空！\n");
        }
        else
        {
            top->next = p->next;
            *data = p->data;
            free(p);   //释放p指向的结点
        }
    }
    
    //取栈顶元素
    
    int GetTop(LinkStack top, DataType *data)
    {
        LStackNode* p;
        p = top->next;
        if (StackEmpty(top))
        {
            printf("栈为空！\n");
        }
        else
        {
            *data = p->data;
        }
        return *data;
    }
    
    //求表长操作
    
    int StackLength(LinkStack top)
    {
        int count = 0;
        LStackNode *p;
        p = top;
        while (p->next != NULL)
        {
            count++;
            p = p->next;
        }
        return count;
    }
    
    //销毁链栈
    void DestoryStack(LinkStack top)
    {
        LStackNode *p;
        LStackNode *q;
        p = top;
        while (!p)
        {
            q = p;
            p = p->next;
            free(q);
        }
    
    }
    
    //打印栈中元素
    void StackPrint(LinkStack top)
    {
        LStackNode* p;
        if (StackEmpty(top))
        {
            printf("栈为空！\n");
        }
        printf("栈中元素为：\n");
        p = top;
        while (p->next != NULL)
        {
            p = p->next;
            printf("%-3d", p->data);
    
        }
    
        printf("\n");
    }
    int main()
    {
        LinkStack Ls;
        DataType data;
        InitStack(&Ls);
        printf("将1，2，3，4依此入栈:\n\n");
        PushStack(Ls, 1);
        PushStack(Ls, 2);
        PushStack(Ls, 3);
        PushStack(Ls, 4);
        StackPrint(Ls);
        printf("栈的长度为：%d\n", StackLength(Ls));
        printf("栈顶元素为：%d\n", GetTop(Ls, &data));
        printf("\n");
        printf("退一次栈！\n");
        PopStack(Ls, &data);
        StackPrint(Ls);
        printf("栈的长度为：%d\n", StackLength(Ls));
        printf("栈顶元素为：%d\n", GetTop(Ls,&data));
        printf("\n");
        printf("将8入栈：\n");
        PushStack(Ls, 8);
        printf("将9进栈：\n");
        PushStack(Ls, 9);
        printf("退一次栈：\n");
        PopStack(Ls, &data);
        StackPrint(Ls);
        DestoryStack(Ls);
        system("pause");
        return 0;
    }

--------------------

#### 代码测试结果 ####

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220527/8a13c74ac167462da6f8894e91273b29.png