链栈的实现 C语言

刺骨的言语ヽ痛彻心扉 2023-03-03 08:50 41阅读 0赞

## [目录][Link 1] ##

## 链栈结构 ##

在链栈的结构体中，我们设置一个存储数据的位置和一个指向下一个结构体的指针。然后我们把这个结构体名字设置为stacknode和一个指向这个结构体的指针。`StackNode *S`和`ListStack S`的效果是一样的。只不过新创一个链的时候用前面那个，ListStack S特殊的用来指向链栈头结点。

typedef struct StackNode{
        ElemType data;
        struct StackNode *next;
    }StackNode,*ListStack;

## 创建链栈 ##

我们使用`ListStack S`特别创建一个头指针。由于我们把头指针传入到初始化函数中，初始化的时候让S指针等于NULL。然后S指针指向的地址就变了，也就是我们在函数中做的操作就没用了。所以我们这个地方就需要用引用。当然，也可以最后把S指针用return返回出来，就不用用引用了。

int InitStack(ListStack &S)
    {
        S=NULL;
        return OK;
    }

## 入栈 ##

链栈的入栈操作很类似于链表的前插入法。首先，我们要注意的就是，S指针一直指向的就是栈顶。我们使用`StackNode *p;`新建一个结点，然后让这个结点指向链栈的原来的栈顶，也就是S指针，这样新创建的结点就入栈了。然后再让S指向新的栈顶p即可。

int Push(ListStack &S,ElemType e)
    {
        StackNode *p;
        p =(StackNode *)malloc(sizeof(StackNode));
        p->data = e;
        p->next = S;
        S = p;
        return OK;
    }

## 遍历链栈中元素 ##

没什么好说的，跟顺序栈差不多。本来想要从栈底向栈底遍历，但是没办法。只能从栈顶开始遍历。

int StackTraverse(ListStack S)
    {
        StackNode *p;
        p=S;
        printf("--------\n");
        while(p)
        {
            printf("e = %d\n",p->data);
            p = p->next;
        }
        printf("--------\n");
        return OK;
    }

## 出栈 ##

出栈需要把原节点存储空间释放，然后S指向S->next就行。

int Pop(ListStack &S,ElemType *e)
    {
        if(S==NULL)
            return ERROR;   //这时是空栈
        *e = S->data;
        StackNode *p;
        p = S;
        S = S->next;
        free(p);
        return OK;
    
    }

## 取栈顶元素 ##

没什么可说的。

int Gettop(ListStack S)
    {
        if(S==NULL)
            return ERROR;
        return S->data;
    }

## 完整代码 ##

#include<stdio.h>
    #include <stdlib.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    
    typedef int ElemType;
    
    typedef struct StackNode{
        ElemType data;
        struct StackNode *next;
    }StackNode,*ListStack;
    
    int InitStack(ListStack &S);
    int Push(ListStack &S,ElemType e);
    int StackTraverse(ListStack S);
    int Pop(ListStack &S,ElemType *e);
    int Gettop(ListStack S);
    
    int main()
    {
        int e;
        int cnt=5;
        ListStack S;
        InitStack(S);
        while(cnt)
        {
            scanf("%d",&e);
            Push(S,e);
            cnt--;
        }
        StackTraverse(S);
        Pop(S,&e);
        printf("e = %d\n",e);
        e = Gettop(S);
        printf("e = %d\n",e);
        return 0;
    }
    
    int InitStack(ListStack &S)
    {
        S=NULL;
        return OK;
    }
    
    int Push(ListStack &S,ElemType e)
    {
        StackNode *p;
        p =(StackNode *)malloc(sizeof(StackNode));
        p->data = e;
        p->next = S;
        S = p;
        return OK;
    }
    
    int StackTraverse(ListStack S)
    {
        StackNode *p;
        p=S;
        printf("--------\n");
        while(p)
        {
            printf("e = %d\n",p->data);
            p = p->next;
        }
        printf("--------\n");
        return OK;
    }
    
    int Pop(ListStack &S,ElemType *e)
    {
        if(S==NULL)
            return ERROR;   //这时是空栈
        *e = S->data;
        StackNode *p;
        p = S;
        S = S->next;
        free(p);
        return OK;
    
    }
    
    int Gettop(ListStack S)
    {
        if(S==NULL)
            return ERROR;
        return S->data;
    }

[Link 1]: https://blog.csdn.net/hpu_yangchen/article/details/107696463