数据结构顺序栈

忘是亡心i 2022-05-28 00:37 244阅读 0赞

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

**栈的定义**：只能在表的一端（栈顶）进行插入和删除的线性表。

**逻辑结构**：与线性表相同，仍为一一对应的关系。

**存储结构：**用顺序栈和链栈存储均可，但以顺序栈更为常见。

**运算规则：**只能在栈顶（top）进行运算，且访问节点时只能先进后出（FILO），或后进先出（LIFO）的原则。

**实现方式：**关键是在写压栈和弹栈的函数具体的实现依顺序栈和链栈的不同而不同，基本的操作有压栈，弹栈，读取栈顶元素，建栈，判断栈满，判断栈空等等。

**顺序栈的存储结构：**

#define MAXSIZE 100
    typedef struct 
    {
        SElemType *base;    //栈底
        SElemType *top;     //栈顶
        int stacksize;  //顺序栈的存储容量
    }SqStack;

**顺序栈的初始化：**

顺序栈初始化即为构造一个空栈，第一步为顺序栈分配存储空间，第二部判断是否分配成功，若分配失败错误，成功则继续，第三部栈顶等于栈底表示为空栈，第四部设置顺序栈的存储空间，初始化成功。

Status InitStack(SqStack &S)
    {
        S.base = new SElemType[MAXSIZE];
        if(!S.base)
            return OVERFLOW;
        S.top = S.base;
        S.stacksize = MAXSIZE;
        return OK;
    }

**判断顺序栈是否为空：**

bool StackEmpty(SqStack S)
    {
        if(S.base == S.top)
            return true;
        return false;
    }

**求顺序栈的长度：**

int StackLength(SqStack S)
    {
        return S.top - S.base;
    }

**清空顺序栈：**

Status ClearStack(SqStack &S)
    {
        if(S.base != S.top)
            S.base = S.top;
        return OK;
    }

**销毁顺序栈：**

Status DestroyStack(SqStack &S)
    {
        if(S.base)
        {
            delete S.base;
            S.stacksize = 0;
            S.top = S.base = NULL;
        }
        return OK;
    }

**顺序栈压栈：**

第一步判断顺序栈是否已满，满则返回失败，不满继续，第二步元素e压入栈中，第三部栈顶加一。

Status Push(SqStack &S, SElemType e)
    {
        if(S.top - S.base == MAXSIZE)
            return ERROR;
        *S.top++ = e;   //*S.top = e, S.top++, 先给值，再加一
        return OK;
    }

**顺序栈弹栈：**

第一步判断顺序栈是否为空，空则返回失败，不空继续，第二步栈顶元素减一，再将位于栈顶位置的元素暂时保存到e中。

Status Pop(SqStack &S, SElemType &e)
    {
        if(S.base == S.top)
            return ERROR;
        e = *--S.top;   //--S.top, e = *S.top, 栈顶先减一， 再把值保存到e中
        return OK;
    }

**获取顺序栈栈顶元素：**

第一步判断顺序栈是否空，空则返回失败，不空继续，第二步现取栈顶前一个地址的元素给e。

Status GetStack(SqStack S, SElemType &e)
    {
        if(S.base == S.top)
            return ERROR;
        e = *(S.top - 1);
        return OK;
    }

**代码：**

#include <iostream>
    #include <cstdlib>
    using namespace std;
    #define MAXSIZE 100
    
    //顺序栈的存储结构
    typedef struct
    {
        int *base;  //栈底
        int *top;   //栈顶
        int stacksize;
    }SqStack;
    //顺序栈的初始化
    void InitStack(SqStack &S)
    {
        S.base = new int[MAXSIZE];
        if(!S.base)
            exit(1);
        S.top = S.base;
        S.stacksize = MAXSIZE;
    }
    //压栈
    bool Push(SqStack &S, int e)
    {
        if(S.top - S.base == MAXSIZE)
            return false;
        *S.top++ = e;
        return true;
    }
    //弹栈
    bool Pop(SqStack &S, int &e)
    {
        if(S.base == S.top)
            return false;
        e = *--S.top;
        return true;
    }
    //判断顺序栈是否为空
    bool StackEmpty(SqStack S)
    {
        if(S.base == S.top)
            return true;
        return false;
    }
    //求顺序栈的长度
    int StackLength(SqStack S)
    {
        return S.top - S.base;
    }
    //清空顺序栈
    void ClearStack(SqStack &S)
    {
        if(S.base)
            S.top = S.base;
    }
    //销毁顺序栈
    void DestroyStack(SqStack &S)
    {
        if(S.base)
        {
            delete S.base;
            S.stacksize = 0;
            S.base = S.top = NULL;
        }
    }
    //获取栈顶元素
    bool GetStack(SqStack S, int &e)
    {
        if(S.base == S.top)
            return false;
        e = *(S.top - 1);
        return true;
    }
    //输出顺序栈
    void PrintStack(SqStack S)
    {
        while(S.base != S.top)
            cout << *S.base++ << '\t';
        cout << endl;
    }
    int main()
    {
        SqStack S;
        InitStack(S);
        if(StackEmpty(S))
            cout << "顺序栈为空" << endl;
        else
            cout << "顺序栈不为空" << endl;
        int n;
        cout << "输入元素的个数:";
        cin >> n;
        int e;
        while(n--)
        {
            cin >> e;
            if(Push(S, e))
                ;
            else
                cout << "压栈失败" << endl;
        }
        PrintStack(S);
        cout << "弹出一个数据" << endl;
        if(Pop(S, e))
            ;
        else
            cout << "弹栈失败" << endl;
        cout << "长度为:";
        cout << StackLength(S) << endl;
        if(GetStack(S, e))
            cout << "栈顶元素为:" << e << endl;
        else
            cout << "获取栈顶元素失败" << endl;
        if(StackEmpty(S))
            cout << "栈为空" << endl;
        else
            cout << "栈不为空" << endl;
        cout << "清空栈" << endl;
        ClearStack(S);
        if(StackEmpty(S))
            cout << "栈为空" << endl;
        else
            cout << "栈不为空" << endl;
        cout << "栈长为:";
        cout << StackLength(S) << endl;
        cout << "销毁栈" << endl;
        DestroyStack(S);
        return 0;
    }