【数据结构】带头节点的链栈的表示和实现

缺乏、安全感 2021-11-29 15:24 270阅读 0赞

#include<iostream>
    using namespace std;
    typedef struct SNode {
        int data;
        struct SNode *next;
    }SNode, *LinkStack;
    
    bool InitLStack(LinkStack &LS) {
        LS = new SNode;
        LS->next = NULL;
        if (LS)
            return true;
        return false;
    }
    
    bool LStackEmpty(LinkStack LS) {
        if (LS->next == NULL) {
            cout<<"LinkStack is empty"<<endl;
            return true;
        }
        return false;
    }
    
    bool Push(LinkStack &LS, int data) {
        if (!LS)
            return false;
        SNode *s, *top;
        top = new SNode;
        top->data = data;
        top->next = NULL;
        if (LS->next == NULL) {
            LS->next = top;
            return true;
        }
        s = LS->next;
        top->next = s;
        LS->next = top;
        return true;
    }
    
    bool Pop(LinkStack &LS, int &data) {
        if (LStackEmpty(LS))
            return false;
        SNode *top = LS->next;
        data = top->data;
        LS->next = top->next;
        delete top;
        return true;
    }
    
    bool GetTop(LinkStack LS, int &data) {
        if (!LStackEmpty(LS))
            return false;
        data = LS->next->data;
        return true;
    }
    
    void PrintLStack(LinkStack LS) {
        if (LStackEmpty(LS))
            return;
        SNode *s = LS->next;
        cout<<"LinkStack :";
        while (s) {
            cout<<s->data<<" ";
            s = s->next;
        }
        cout<<endl<<endl;
    }
    
    int main() {
        LinkStack LS;
        InitLStack(LS);
        cout<<"Init LinkStack"<<endl;
        for (int i=1; i<9; i++)
            Push(LS, i*i);
        PrintLStack(LS);
    
        while (!LStackEmpty(LS)) {
            int top;
            Pop(LS, top);
            cout<<"After pop "<<top<<endl;
            PrintLStack(LS);
        }
        return 0;
    }

// 测试结果
    Init LinkStack
    LinkStack :64 49 36 25 16 9 4 1
    
    After pop 64
    LinkStack :49 36 25 16 9 4 1
    
    After pop 49
    LinkStack :36 25 16 9 4 1
    
    After pop 36
    LinkStack :25 16 9 4 1
    
    After pop 25
    LinkStack :16 9 4 1
    
    After pop 16
    LinkStack :9 4 1
    
    After pop 9
    LinkStack :4 1
    
    After pop 4
    LinkStack :1
    
    After pop 1
    LinkStack is empty
    LinkStack is empty