数据结构整理——第三章栈和队列_mooc数据结构与算法第三章栈与队列答案中缀表达式-CSDN博客

本文链接：https://blog.csdn.net/mooe1011/article/details/88089325

本文是关于数据结构中栈和队列的整理，涵盖了栈和队列的基本概念、操作、应用，如括号匹配、迷宫求解、矩阵压缩存储和广义表。同时介绍了栈和队列在缓冲区、广度优先搜索等场景中的使用，并提供了相关代码示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

考研时个人整理的，参考王道、严蔚敏等数据结构。

上一章——线性表：https://blog.csdn.net/mooe1011/article/details/88036093

下一章——树：https://blog.csdn.net/mooe1011/article/details/88089462

1. 栈

初始化S.top=-1,栈顶元素S.data[S.top]
注如果栈顶指针为S.top=0，则进栈S.data[S.top++]=x，出栈x=S.data[–S.top]，相应栈空栈满条件也会变化
共享栈 topl(左边)=-1,topr(右边)=MaxSize为空；当topr-topl=1为满
链式栈Lhead指向栈顶元素
链式入队，相当于头插法，p->next=Lhead->next;Lhead->next=p;
n个不同元素进栈，出栈序列为(卡特兰数): $\dfrac{(2n)!}{(n+1)!n!}$
代码

    顺序栈
    #define MaxSize 50
    typedef struct {
        int data[MaxSize];
        int top;
    }SqStack;  //与顺序表差不多
    
    链式栈
    typedef struct LinkNode{
        int data;
        struct LinkNode *next;
    }*Listack;

检查越界
1. 栈满if(S.top==MaxSize-1)
2. 栈空if(S.top==-1)
进出栈
1. 进栈 S.data[++S.top]=x; (先加)
2. 出栈 x=S.data[S.top–]; (后减)
判断栈序列是否合法

    int Judge (char A[]){
        int i=j=k=0;
        while(A[i]!='\0'){
            switch(A[i]){
                case 'I':j++;break;  //I代表入栈，O代表出栈，IOOO非法，IIOO合法
                case 'O':k++;
                if (k>j){
                    printf("非法\n");exit(0);
                }
            }
            i++;
        }
        if (j!=k){
            printf("非法\n");
            return false;
        } else {
            printf("合法\n");