526互联

数据结构：栈与队列-详解顺序栈

发布时间 2023-10-23 16:01:32作者: 日月同珲

《详解顺序栈》

目录：

  1. 顺序栈的定义及其特点
  2. 顺序栈的实现
  3. 完整Demo
  4. 运行截图
  5. 小结
  6. 参考文献

一、顺序栈的定义及其特点

　　顺序栈指的是用顺序表实现的栈存储结构，栈存储结构存取数据元素必须遵守 "先进后出" 的原则。顺序表和栈存储数据的方式高度相似，只不过栈对数据的存取过程有特殊的限制，而顺序表没有。例如，我们使用顺序表（用 a 数组表示）存储 {1,2,3,4}，存储状态如图 1 所示：

图 1 顺序表存储 {1,2,3,4}


　　使用栈存储结构存储 {1,2,3,4}，存储状态如图 2 所示： 

图 2 栈结构存储 {1,2,3,4}


　　对比图 1 和图 2 不难看出，用顺序表模拟栈结构很简单，只要将数据从数组下标为 0 的位置依次存储即可。栈中存取元素，必须遵循“先进后出”的原则，因此若想将图 1 中存储的元素 1 从栈中取出，需依次先将元素 4、元素 3 和元素 2 从栈中取出，最后才能取出元素 1。

　　顺序表模拟入栈和出栈的实现思路：定义一个实时记录栈顶位置的变量（假设命名为 top），初始状态下栈内无任何元素，整个栈是"空栈"，top 的值为 -1。一旦有数据元素进栈，则 top 就做 +1 操作；反之，如果数据元素出栈，top 就做 -1 操作。

二、顺序栈的实现　

　　1.结构体定义

　　　　本次顺序栈的代码中定义了用于存储数据的堆空间，栈顶指针，最大容量，以及用于撤销操作的缓存数组；buffer[0]存储操作时的top位置，用于区分入栈与出栈操作。buffer[1]存储操作的数据。

　　

typedef struct{
    
    DataType* data;//堆空间 
    int maxSize;//最大容量 
    int top;//栈顶指针 
    DataType buffer[2];
    
}SequenceStack;

　　2.初始化

　　　　初始化时使用MaxSzie（最大容量）* 单个DataType长度申请内存空间，同时将buffer数组（撤销数据）与top（栈顶指针）初始化为-1。在初始化异常时打印error.h中对应的错误信息并返回相应错误码。

/**
 * @brief 顺序栈初始化
 *
 * @param S 顺序栈指针
 * @param MaxSize 最大容量
 *
 * @return 状态码：0为成功
 **/
int initSequenceStack(SequenceStack* S, int MaxSize) {

    S->data = (DataType*)malloc(sizeof(DataType) * MaxSize);

    if (!S->data) {
        printf("%s", errorHint[0]);
        return errorCode[0];
    }
    S->maxSize = MaxSize;
    S->top = -1;
    S->buffer[0] = -1;
    S->buffer[1] = -1;

    return 0;
}

　　3.打印

　　　　打印前进行顺序栈判空，为空则抛出异常。反之则从栈底开始将栈打印。

/**
 * @brief 打印顺序栈
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：0为成功
 **/
int printSequenceStack(SequenceStack* S) {

    if (isEmptySequenceStack(S)) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    } else {
        printf("当前顺序栈为：");
        for (int i = 0; i <= S->top; i++) {
            printf("%d", S->data[i]);
        }
        printf("\n\n");
    }

    return 0;
}

　　4.入栈

　　　　入栈前进行顺序栈判满，已满则抛出异常。反之则移动top+1（栈顶指针）将数据入栈，同时将入栈位置与入栈数据更新到缓存数组。

/**
 * @brief 顺序栈入栈
 *
 * @param S 顺序栈指针
 * @param x
 *
 * @return 状态码：0为成功
 **/
int pushSequenceStack(SequenceStack* S, DataType x) {
    if (isFullSequenceStack(S)) {
        printf("%s", errorHint[1]);
        return errorCode[1];
    } else {
        S->top++;
        S->data[S->top] = x;
        S->buffer[0] = S->top;
        S->buffer[1] = x;
    }
    return 0;
}

　　5.出栈

　　　　出栈前进行顺序栈判空，为空则抛出异常。反之则将出栈位置与出栈数据更新至缓存数组，并移动top-1。

/**
 * @brief 顺序栈出栈
 *
 * @param S 顺序栈指针
 * @param x
 *
 * @return 状态码：0为成功
 **/
int popSequenceStack(SequenceStack* S, DataType* x) {//出栈
    if (isEmptySequenceStack(S)) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    } else {
        S->buffer[0] = S->top;
        S->buffer[1] = S->data[S->top];
        *x =  S->data[S->top];
        S->top--;
    }
    return 0;
}

　　6.获取栈顶元素

　　　　获取前进行顺序栈判空，为空则抛出异常。反之则将传入的DataType指针指向栈顶数据。

/**
 * @brief 获取栈顶元素
 *
 * @param S 顺序栈指针
 * @param x
 *
 * @return 状态码：0为成功
 **/
int getSequenceStack(SequenceStack* S, DataType* x) {
    if (isEmptySequenceStack(S)) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    } else {
        *x = S->data[S->top];
    }
    return 0;
}

　　7.获取栈顶元素

　　　　使用free()函数释放内存。

/**
 * @brief 顺序栈销毁
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：0为成功
 **/
int destroySequenceStack(SequenceStack* S) {
    free(S->data);
    return 0;
}

　　8.撤销操作

　　　　撤销操作通过buffer数组实现，先判断buffer[0]的值，如果为-1代表无可撤销操作，打印错误信息并返回错误码。如果不等于-1，则将其与当前栈顶指针做比较，大于栈顶指针则上一步为出栈操作，调用入栈函数，将buffer[1]存储的数据重新入栈。小于则相反，调用出栈操作将栈顶元素出栈。

/**
 * @brief 撤销操作
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：0为成功
 **/
int revocationSequenceStack(SequenceStack* S) {

    if ((S->buffer[0]) == -1) {
        printf(errorHint[3]);
        return errorCode[3];
    } else {
        if (S->buffer[0] > S->top) {
            if (pushSequenceStack(S, S->buffer[1]) == 0) {
                printf("操作已撤销！\n\n");
            }
        } else {
            if (popSequenceStack(S, &S->buffer[1]) == 0) {
                printf("操作已撤销！\n\n");
            }
        }
    }

    return 0;
}

　　9.十进制转二进制实现

　　　　本次转换并没有使用递归，而是通过栈“先进后出，后进先出”的特性实现的。初始化栈后，使用循环将十进制数不断向二取余，直至为0，同时将余数进栈。而后再次通过循环不断出栈并打印，直至栈空，至此转换便已完成。最后一定不要忘了销毁栈。

int conversion(int decimalism) {

    SequenceStack S;
    int binary;

    initSequenceStack(&S, 32);

    while (decimalism) {
        pushSequenceStack(&S, decimalism % 2);
        decimalism /= 2;
    }

    while (!isEmptySequenceStack(&S)) {
        popSequenceStack(&S, &binary);
        printf("%d", binary);
    }
    printf("\n"); 

    destroySequenceStack(&S);

    return 0;
}

　　10.后缀表达式运算

　　　　后缀表达式的实现原理很简单，逐个判断字符串中的字符，为数字0~9则入栈，为运算符则出栈两个元素并运算，最后将结果再入栈，直至只剩栈底元素，将其打印即为结果。

int expression() {
    SequenceStack S;
    int i;
    int op1, op2;
    int x;

    char exp[20]; /*后缀表达式*/

    initSequenceStack(&S, 10);

    printf("请输入一个后缀表达式(eg. 56+):");
    scanf("%s", exp);

    for (i = 0; i < (int) strlen(exp); i++) {
        switch (exp[i]) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                /*入栈*/
                pushSequenceStack(&S, exp[i] - 48);
                break;
            case '+':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 + op2;
                pushSequenceStack(&S, x);
                break;

            case '-':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 - op2;
                pushSequenceStack(&S, x);
                break;
            case '*':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 * op2;
                pushSequenceStack(&S, x);
                break;
            case '/':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 / op2;
                pushSequenceStack(&S, x);
                break;
        }
    }
    popSequenceStack(&S, &x);
    printf("计算结果为：%s = %d\n", exp, x);
    destroySequenceStack(&S);

    return 0;
}

 

三、完整Demo

　　welcome.h（欢迎字符图案）：

char *welcome[] = {
    "                                    \n",
    "                                             4&(\n",
    "                                           ` ~&&\\yM#1\n",
    "                                            ,_'Q!!NMW&\n",
    "                                            WCb 7N@4D Q%,,\n",
    "                                            PM'*MDk#M0p,\n",
    "                                                ]@J0&e~~4r' ,+bQEQ\n",
    "                                                 F8I&#'   _&B$$bW#&$\n",
    "                                                  &0A1   L#DE&E~!Q&Q,\n",
    "                                     _=,        ,#0RN1  _T@0$'   ZN$Q.   grNq5\n",
    "                                     ^ 'd     ,0K0pK^  g*Q0g'    #Q4p&,/g9X*&#,_/ (q\n",
    "                                      TA1   ,sDQWh4^  x&NM0` _   #FQ#K#fA#   `*K#XWP~-\n",
    "                                       ^&p,wNMM0qD: /HE#EN' ..#g)~ '@NG0Qx,    `=X*\n",
    "                                      '  '43$'hEk##m0D04f_g  ~^ ~   `-00**0\n",
    "                                               =0#ONq2W0BF^#, _            p,,\n",
    "                                                 `  ^''~    ~b''        **R3`\n",
    "                                                          ow,F         +#F~'\n",
    "                                                          /-9!          `\\ \n",
    "                                                           R\n"
    };
View Code

　　sequenceStack.h（结构与函数声明）：

/*
    sequenceStack.h 顺序栈 
*/
typedef int DataType;

typedef struct{
    
    DataType* data;//堆空间 
    int maxSize;//最大容量 
    int top;//栈顶指针 
    DataType buffer[2];
    
}SequenceStack;

int initSequenceStack(SequenceStack* S, int MaxSize); //初始化

int printSequenceStack(SequenceStack* S);//打印 

int pushSequenceStack(SequenceStack *S, DataType x);//入栈 

int popSequenceStack(SequenceStack *S, DataType *x);//出栈 

int getSequenceStack(SequenceStack *S, DataType *x);//获取栈顶元素 

int isEmptySequenceStack(SequenceStack *S);//栈判空 

int isFullSequenceStack(SequenceStack *S);//栈判满 

int destroySequenceStack(SequenceStack *S);//销毁 

int revocationSequenceStack(SequenceStack *S);//撤销
View Code

　　sequenceStack.c（函数实现）：

#include <stdio.h>
#include <malloc.h>
#include "sequenceStack.h"
#include "error.h"

/**
 * @brief 顺序栈初始化
 *
 * @param S 顺序栈指针
 * @param MaxSize 最大容量
 *
 * @return 状态码：0为成功
 **/
int initSequenceStack(SequenceStack* S, int MaxSize) {

    S->data = (DataType*)malloc(sizeof(DataType) * MaxSize);

    if (!S->data) {
        printf("%s", errorHint[0]);
        return errorCode[0];
    }
    S->maxSize = MaxSize;
    S->top = -1;
//    S->buffer[0] = -1;
//    S->buffer[1] = -1;

    return 0;
}

/**
 * @brief 打印顺序栈
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：0为成功
 **/
int printSequenceStack(SequenceStack* S) {

    if (isEmptySequenceStack(S)) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    } else {
        printf("当前顺序栈为：");
        for (int i = 0; i <= S->top; i++) {
            printf("%d", S->data[i]);
        }
        printf("\n\n");
    }

    return 0;
}

/**
 * @brief 顺序栈入栈
 *
 * @param S 顺序栈指针
 * @param x
 *
 * @return 状态码：0为成功
 **/
int pushSequenceStack(SequenceStack* S, DataType x) {
    if (isFullSequenceStack(S)) {
        printf("%s", errorHint[1]);
        return errorCode[1];
    } else {
        S->top++;
        S->data[S->top] = x;
        S->buffer[0] = S->top;
        S->buffer[1] = x;
    }
    return 0;
}

/**
 * @brief 顺序栈出栈
 *
 * @param S 顺序栈指针
 * @param x
 *
 * @return 状态码：0为成功
 **/
int popSequenceStack(SequenceStack* S, DataType* x) {//出栈
    if (isEmptySequenceStack(S)) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    } else {
        S->buffer[0] = S->top;
        S->buffer[1] = S->data[S->top];
        *x =  S->data[S->top];
        S->top--;
    }
    return 0;
}

/**
 * @brief 获取栈顶元素
 *
 * @param S 顺序栈指针
 * @param x
 *
 * @return 状态码：0为成功
 **/
int getSequenceStack(SequenceStack* S, DataType* x) {
    if (isEmptySequenceStack(S)) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    } else {
        *x = S->data[S->top];
    }
    return 0;
}

/**
 * @brief 顺序栈判空
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：1为空
 **/
int isEmptySequenceStack(SequenceStack* S) {
    return S->top == -1 ? 1 : 0;
}

/**
 * @brief 顺序栈判满
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：1为满
 **/
int isFullSequenceStack(SequenceStack* S) {
    return S->top == S->maxSize - 1 ? 1 : 0;
}

/**
 * @brief 顺序栈销毁
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：0为成功
 **/
int destroySequenceStack(SequenceStack* S) {
    free(S->data);
    return 0;
}

/**
 * @brief 撤销操作
 *
 * @param S 顺序栈指针
 *
 * @return 状态码：0为成功
 **/
int revocationSequenceStack(SequenceStack* S) {

    if ((S->buffer[0]) == -1) {
        printf(errorHint[3]);
        return errorCode[3];
    } else {
        if (S->buffer[0] > S->top) {
            if (pushSequenceStack(S, S->buffer[1]) == 0) {
                printf("操作已撤销！\n\n");
            }
        } else {
            if (popSequenceStack(S, &S->buffer[1]) == 0) {
                printf("操作已撤销！\n\n");
            }
        }
    }

    return 0;
}
View Code

　　main.c（主函数）：

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "welcome.h"
#include "sequenceStack.c"

/*十进制转换为二进制*/
int conversion(int decimalism);
/*后缀表达式*/
int expression();

int main(int argc, char *argv[]) {

    for (int i = 0; i < 19; i++) {
        printf("%s", welcome[i]);
        for (int j = 0; j <= 100000000; j++) {
            for (int m; m <= 100000000; m++) {
                ;
            }
        }
    }

    int operate;
    int maxSize;
    char verify;
    DataType data;
    SequenceStack S;
//    PolynomialList* pa, pb, sum;

    printf("\n\n本应用程序为数据结构-顺序栈演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n");
    do {
        printf("<----------------------------------------------------顺序栈演示程序--------------------------------------------------->\n");
        printf("0. 退出程序\n");
        printf("1. 初始化顺序栈\n");
        printf("2. 打印顺序栈\n");
        printf("3. 入栈\n");
        printf("4. 出栈\n");
        printf("5. 撤销\n");
        printf("6. 十进制转换\n");
        printf("7. 后缀表达式运算\n");
        printf("8. 帮助\n");
        printf("请输入操作选项(0~8,0为退出)：");
        scanf("%d", &operate);

        switch (operate) {
            case 1:
                printf("请输入顺序栈最大容量：");
                scanf("%d", &maxSize);
//                getchar();
                if (!initSequenceStack(&S, maxSize)) {
                    printf("初始化完成\n\n");
                }
                break;
            case 2:
                printSequenceStack(&S);
                break;
            case 3:
                printf("请输入入栈数据：");
                scanf("%d", &data);
                if (!pushSequenceStack(&S, data)) {
                    printf("入栈成功！\n\n");
                }
                break;
            case 4:
                while (1) {
                    printf("出栈操作无法完全恢复是否要出栈？(y/n)：");
                    getchar();
                    scanf("%c", &verify);
                    if (verify == 89 || verify == 121) {
                        if (!popSequenceStack(&S, &data)) {
                            printf("出栈成功！\n\n");
                        }
                        break;
                    } else if (verify == 78 || verify == 110) {
                        printf("出栈操作已取消\n\n");
                        break;
                    }
                }

                break;
            case 5:
                revocationSequenceStack(&S);
                break;
            case 6:
                printf("请输入需要转换的十进制整数：");
                scanf("%d", &data);
                conversion(data);
                break;
            case 7:
                expression();
                break;
            case 8:
                printf("本应用程序为数据结构-顺序栈演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n");
                break;
            case 0:
                return 0;
                break;
        }

    } while (operate != 0);

    return 0;
}

int conversion(int decimalism) {

    SequenceStack S;
    int binary;

    initSequenceStack(&S, 32);

    while (decimalism) {
        pushSequenceStack(&S, decimalism % 2);
        decimalism /= 2;
    }

    while (!isEmptySequenceStack(&S)) {
        popSequenceStack(&S, &binary);
        printf("%d", binary);
    }
    printf("\n"); 

    destroySequenceStack(&S);

    return 0;
}

int expression() {
    SequenceStack S;
    int i;
    int op1, op2;
    int x;

    char exp[20]; /*后缀表达式*/

    initSequenceStack(&S, 10);

    printf("请输入一个后缀表达式(eg. 56+):");
    scanf("%s", exp);

    for (i = 0; i < (int) strlen(exp); i++) {
        switch (exp[i]) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                /*入栈*/
                pushSequenceStack(&S, exp[i] - 48);
                break;
            case '+':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 + op2;
                pushSequenceStack(&S, x);
                break;

            case '-':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 - op2;
                pushSequenceStack(&S, x);
                break;
            case '*':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 * op2;
                pushSequenceStack(&S, x);
                break;
            case '/':
                popSequenceStack(&S, &op1);
                popSequenceStack(&S, &op2);
                x = op1 / op2;
                pushSequenceStack(&S, x);
                break;
        }
    }
    popSequenceStack(&S, &x);
    printf("计算结果为：%s = %d\n", exp, x);
    destroySequenceStack(&S);

    return 0;
}
View Code

　　error.h（错误信息）：

int errorCode[] = {100001, 100002, 100003, 100004, 100005};

char* errorHint[] = {
    "ERROR[100001]：申请内存错误，初始化失败！\n\n",
    "ERROR[100002]：顺序栈已满！\n\n",
    "ERROR[100003]：顺序栈为空！\n\n",
    "ERROR[100004]：无可撤销操作！\n\n",
    "ERROR[100005]：申请内存错误，结点创建失败！\n\n",
};
View Code

 

四、运行截图

　　

 

五、小结

　　栈其实在我的日常开发中接触较多，Android中的任务栈则是最经典的例子。在理解的同时活用栈的特性是比较重要的。本周内容个人觉得比较简单，所以总结并不多。

　　每周闲篇：本周虽然同样忙碌，但已经好上不少了，最要紧的活数据已经接通（虽然写法不太规范），下周完善收尾再优化一下即可~

六、参考文献

　　王海艳等.《数据结构（C语言）》第二版[M].北京:人民邮电出版社,2020:10~14.