【数据结构】顺序栈的表示和实现

蔚落 2021-11-29 05:48 295阅读 0赞

#include<iostream>
    using namespace std;
    const int MAXSIZE = 100;
    typedef struct Stack{
        int data[MAXSIZE];
        int top;
    }Stack;
    
    void InitStack(Stack &S) {
        S.top = -1;
    }
    
    bool StackEmpty(Stack S) {
        if (S.top == -1)
            return true;
        return false;
    }
    
    bool Push(Stack &S, int data) {
        if (S.top == MAXSIZE-1)
            return false;
        S.data[++S.top] = data;
        return true;
    }
    
    bool Pop(Stack &S, int &data) {
        if (S.top == -1)
            return false;
        data = S.data[S.top--];
        return true;
    }
    
    bool GetTop(Stack S, int &data) {
        if (S.top == -1)
            return false;
        data = S.data[S.top];
        return true;
    }
    
    void PrintStack(Stack S) {
        if (StackEmpty(S)) {
            cout<<"Stack is empty"<<endl;
            return;
        }
        cout<<"Stack :";
        while (S.top != -1) {
            cout<<S.data[S.top]<<" ";
            S.top--;
        }
        cout<<endl<<endl;
    }
    
    int main() {
        Stack S;
        InitStack(S);
        cout<<"Init Stack"<<endl;
        for (int i=1; i<9; i++)
            Push(S, i*i);
        PrintStack(S);
    
        while (!StackEmpty(S)) {
            int top;
            Pop(S, top);
            cout<<"After pop "<<top<<endl;
            PrintStack(S);
        }
        return 0;
    }

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