数据结构链栈

小灰灰 2022-05-28 00:55 217阅读 0赞

做一个豁达而努力的自己。

链栈的存储结构：

typedef struct StackNode
    {
        SElemType data;
        StackNode *next;
    }StackNode, *SLinkStack;

链栈的初始化：

void InitStack(SLinkList &S)
    {
        S = NULL;
    }

判断是否为空：

Status StackEmpty(SLinkList S)
    {
        if(S == NULL)
            return true;
        return false;
    }

压栈：

Status Push(SLinkList &S, SElemType e)
    {
        SLinkList p;
        p = new StackNode;
        if(!p)
            return OVERFLOW;
        cin >> p->data;
        p->next = S;
        S = p;
        return OK;
    }

弹栈：

Status Pop(SLinkList &S, SElemType &e)
    {
        if(S == NULL)
            return ERROR;
        e = S->data;
        SLinkList p;
        p = S;
        S = S->next;
        delete p;
        return OK;
    }

取栈顶元素：

Status GetTop(SLinkList S, SElemType &e)
    {
        if(S == NULL)
            return ERROR;
        e = S->data;
        return OK;
    }

代码：

#include <iostream>
    using namespace std;
    
    //链栈的存储结构
    typedef struct StackNode
    {
        int data;
        StackNode *next;
    }StackNode, *SLinkList;
    //链栈的初始化
    void InitStack(SLinkList &S)
    {
        S = NULL;
    }
    //判断链表是否为空
    bool StackEmpty(SLinkList S)
    {
        if(S == NULL)
            return true;
        return false;
    }
    //压栈
    bool Push(SLinkList &S, int e)
    {
        SLinkList p;
        p = new StackNode;
        if(!p)
            return false;
        p->data = e;
        p->next = S;
        S = p;
        return true;
    }
    //弹栈
    bool Pop(SLinkList &S, int &e)
    {
        SLinkList p;
        if(S == NULL)
            return false;
        e = S->data;
        p = S;
        S = S->next;
        delete p;
        return true;
    }
    //取栈顶元素
    bool GetTop(SLinkList S, int &e)
    {
        if(S == NULL)
            return false;
        e = S->data;
        return true;
    }
    //链栈的销毁
    void DestroyStack(SLinkList &S)
    {
        SLinkList p, q;
        p = S;
        while(p)
        {
            q = p;
            delete q;
            p = p->next;
        }
        S = NULL;
    }
    int main()
    {
        SLinkList S;
        InitStack(S);
        int n;
        int e;
        cout << "输入元素个数:";
        cin >> n;
        while(n--)
        {
            cin >> e;
            if(Push(S, e))
                ;
            else
                cout << "弹栈失败" << endl;
        }
        if(GetTop(S, e))
            cout << "栈顶元素是:" << e << endl;
        else
            cout << "查找栈顶元素失败" << endl;
        if(Pop(S, e))
            cout << "弹栈成功,弹出的元素是:" << e <<endl;
        else
            cout << "弹栈失败" << endl;
        if(StackEmpty(S))
            cout << "栈为空" << endl;
        else
            cout << "栈不为空" <<endl;
        cout << "销毁链栈" << endl;
        DestroyStack(S);
        if(StackEmpty(S))
            cout << "栈为空" << endl;
        else
            cout << "栈不为空" <<endl;
        return 0;
    }