考研系列-数据结构第三章：栈、队列和数组

目录

一、栈（Stack）基本概念

1.栈的定义

2.栈的基本操作

3.常考题型

4.总结

二、栈的实现

1.顺序存储方式实现-顺序栈

(1)顺序栈定义

(2)顺序栈常用操作

①初始化

②进栈操作

③出栈操作

④读取栈顶元素

(3)共享栈

(4)总结

2.栈的链式存储

(1)链栈定义（跟链表一样）

(2)链栈的常用操作

①进栈

②出栈

③查栈内元素

(3)总结

3.栈相关易错习题总结

(1)选择题

(2)简答题

三、栈的应用

1.括号匹配问题

2.表达式求值问题

(1)表达式相关术语

(2)后缀表达式计算

(3)前缀表达式的计算

(4)总结

3.前、中、后缀表达式之间的转换

(1)中缀表达式转后缀表达式

(2)中缀表达式转前缀表达式

4.中缀表达式相关知识点再整理

(1)中缀表达式转后缀表达式的计算过程(用栈来实现)

(2)中缀表达式的计算(用栈来实现)

5.栈在递归中的作用

四、队列Queue

1.队列的定义

2.队列的常见操作

3.队列的顺序实现

(1)代码定义顺序实现

(2)初始化

(3)入队列操作

(4)循环队列（很常考！！！重点重点重点！！！）

①循环队列的入队操作：

②循环队列的出队操作

③判断循环队列是否已满或者已空

(5)总结

4.队列的链式实现

(1)代码定义

(2)初始化

(3)入队操作

(4)出队操作

(5)队列满的判断

(6)总结

5.双端队列

(1)栈、队列、双端队列结构对比

(2)双端队列类型

(3)双端队列的输出合法性（重点题型，易考题！！）

①栈的输出合法序列

②输入受限的双端队列

③输出受限的双端队列

(4)总结

6.队列相关易错习题总结

(1)选择题

(2)简答题

五、队列的应用

1.树的层序遍历

2.图的广度优先遍历

3.队列在操作系统中的应用

4.习题总结

(1)简答题

六、矩阵的压缩存储

1.数组的存储结构

(1)一维数组

(2)二维数组

2.特殊矩阵的存储（不要背公式）

(1)对称矩阵

(2)三角矩阵

(3)三对角矩阵

(4)稀疏矩阵

(5)总结

(6)常见问题

3.易错题总结

(1)选择题

七、本章归纳总结

八、参考

---

一、栈（Stack）基本概念

1.栈的定义

2.栈的基本操作

(1)初始化栈（InitStack）

        InitStack(&S)：初始化栈S，构造一个空栈，并为其分配相应的内存空间。

(2)创建和销毁栈

        CreateStack(&S)：创建栈S（通常包含在初始化过程中）。

        DestroyStack(&S)：销毁栈S，释放栈S所占用的内存空间。

(3)向栈顶添加元素（Push）

        Push(&S, x)：若栈S未满，则将元素x加入栈顶，成为新的栈顶元素。

(4)从栈顶移除元素（Pop）

        Pop(&S, &x)：若栈S非空，则弹出栈顶元素，并使用变量x返回该元素的值。

(5)获取栈顶元素（GetTop）

        GetTop(S, &x)：若栈S非空，则使用变量x返回栈顶元素的值，但不删除该元素。

(6)其他常用操作

        StackEmpty(S)：判断栈S是否为空。若S为空，则返回true，否则返回false。

3.常考题型

        给出一个进栈顺序，问有哪些合法的出栈顺序？

        例如：进栈顺序为a->b->c->d->e，考试的时候一般会出选择题，问选项中哪种出栈顺序不可能出现？

        这里我们给出一个不可能出现的顺序：c->a->b->d->e。（因为c如果第一个出栈，那么栈内元素从栈顶到栈底一定是b、a，b一定会先于a出栈）

        那么一共存在多少种不同的出栈顺序呢？可以采用数学归纳法得到一个公式（不要求掌握，作为知识扩展）：

4.总结

二、栈的实现

1.顺序存储方式实现-顺序栈

        顺序栈的考察是栈结构的重点，需要关注栈的先进后出特性以及一些重要操作，并学会使用栈解决实际问题

        👇🏻👇🏻👇🏻一些顺序栈相关C++代码实现可以参考下面文章👇🏻👇🏻👇🏻

栈相关代码-CSDN博客文章浏览阅读48次。【代码】栈相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235803

(1)顺序栈定义

使用静态数组定义顺序栈，注意题目中栈顶指针的指向，有的题会将栈顶指针指向栈顶元素，有的会指向距离栈顶最近的空元素位置。

(2)顺序栈常用操作

栈顶元素的指向直接关系到进栈、出栈的代码实现，这个选择题一定要看清楚，这个在下面的④读取栈顶元素时有体现。

①初始化

注意初始化情况时，一般top栈顶指针指向-1

②进栈操作

③出栈操作

注意：只是在逻辑上删除了这个数据

④读取栈顶元素

注意审题：栈顶指向的是栈顶元素还是空位置！！！！

(3)共享栈

两个栈共享一块内存空间，两个栈顶指针的增加方向是相对的，注意栈满时的条件。

(4)总结

2.栈的链式存储

链式存储本质上就是单链表加了操作限制

(1)链栈定义（跟链表一样）

(2)链栈的常用操作

①进栈

②出栈

③查栈内元素

从链头开始遍历，寻找目标元素。

(3)总结

3.栈相关易错习题总结

(1)选择题

问题：

解答：

        注意这里的元素是指data！！！

问题：

解答：

        注意与C语言的命名规则相结合，并且还要输入顺序，判断合法的输出结构

问题：

解答：

(2)简答题

问题：

解答：

三、栈的应用

1.括号匹配问题

注意下面的流程图，好好理解：

代码也需要掌握，因为在复试的时候很有可能出符号匹配相关的题目

2.表达式求值问题

这块知识点非常重要，也很抽象、容易忘，跟着王道的视频课好好学习并理解，多做几个练习，下面是对主要过程进行总结，如果知识点有点遗忘或看不懂，一定要及时回顾一下视频课！！

中缀表达式转后缀和前缀表达式可以对比着来记忆；

前缀表达式和后缀表达式的计算也可以对比记忆，效果更好。

(1)表达式相关术语

(2)后缀表达式计算

（手算和机算都要掌握，这块容易出题）

(3)前缀表达式的计算

着重注意一下机算过程，手算的时候也可以按照这个过程来求值

(4)总结

3.前、中、后缀表达式之间的转换

(1)中缀表达式转后缀表达式

注意左优先原则

(2)中缀表达式转前缀表达式

中缀转后缀和中缀转前缀对比：

4.中缀表达式相关知识点再整理

说明：这块内容和前面有重叠，但是是对中缀表达式相关知识点的汇总和拓展，其中中缀表达式求值问题是使用了中缀转后缀+后缀表达式求值两个算法结合实现的

(1)中缀表达式转后缀表达式的计算过程(用栈来实现)

(2)中缀表达式的计算(用栈来实现)

5.栈在递归中的作用

四、队列Queue

         队列的顺序实现是队列结构考察的重点，需要关注队列先进先出的特性以及一些重要操作，并学会使用队列解决实际问题

        👇🏻👇🏻👇🏻一些队列相关C++代码实现可以参考下面文章👇🏻👇🏻👇🏻队列相关代码-CSDN博客文章浏览阅读52次。【代码】队列相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235830        接下来介绍详细知识点归纳：

1.队列的定义

2.队列的常见操作

        (1)初始化队列(InitQueue(&Q))：构造一个空队列Q。

        (2)销毁队列 (DestroyQueue(&Q))：销毁并释放队列Q所占用的内存空间。

       (3)入队(EnQueue(&Q, x))：若队列Q未满，将元素x加入队列，使之成为新的队尾元素。

        (4)出队(DeQueue(&Q, &x))：若队列Q非空，删除队头元素，并用变量x返回其值。

        (5)读队头元素(GetHead(Q, &x))：若队列Q非空，则将队头元素的值赋给变量x。该操作不删除队头元素。

        (6)判断队列空(QueueEmpty(Q))：判断队列Q是否为空。若队列Q为空，返回true；否则返回false。

        队列的使用场景中，大多只访问队头元素，而其他元素则按照先入先出的原则进行管理和处理。队列的这些基本操作确保了数据结构的正确性和有效性，是实现各种队列相关算法和应用的基础。

3.队列的顺序实现

(1)代码定义顺序实现

(2)初始化

//初始化队列
void InitQueue(SeqQueue &Q){
    Q.rear=0;
    Q.front=0;
    //Q.rear==Q.front时队列为空
}

(3)入队列操作

//入队操作
bool EnQueue(SeqQueue &Q,int elem){
    if((Q.rear+1)%MaxSize==Q.front){//判断队列满
        return false;
    }else{
        Q.data[Q.rear]=elem;
        Q.rear=(Q.rear+1)%MaxSize;
        return true;
    }
}

(4)循环队列（很常考！！！重点重点重点！！！）

        这部分最重要的就是掌握判断什么时候队列满和队列空，这块真题里面经常考察，需要对题目里面定义的队列满、空的条件理解清楚。

        下面对常见的循环队列情况进行总结：

①循环队列的入队操作：

②循环队列的出队操作

③判断循环队列是否已满或者已空

当题目中说：队尾指针指向队尾元素时的情况：

(5)总结

4.队列的链式实现

(1)代码定义

//链式队列的定义
typedef struct{
    LNode *front,*rear;//队头指针和队尾指针
}LinkQueue;
 
//初始化链式队列
void InitLinkQueue(LinkQueue &Q){
    LNode *p=(LNode *)malloc(sizeof(LNode));
    Q.front=p;
    Q.rear=p;
}

(2)初始化

初始化：定义头指针和尾指针

(3)入队操作

队尾指针rear后插，并更新队尾指针

(4)出队操作

队头指针处删除结点，并可能更新头结点指针

(5)队列满的判断

队列的链式实现不会出现队列满的情况，除非内存不足。

(6)总结

5.双端队列

(1)栈、队列、双端队列结构对比

(2)双端队列类型

(3)双端队列的输出合法性（重点题型，易考题！！）

①栈的输出合法序列

        绿色标注的是合法输出序列：

②输入受限的双端队列

        绿色标注的是合法输出序列：

③输出受限的双端队列

        绿色标注的是合法输出序列：

(4)总结

6.队列相关易错习题总结

(1)选择题

问题：重要，多看几遍，一定牢牢记住

解答：

问题：重要，多看几遍，一定牢牢记住

解答：

问题：

解答：

问题：

解答：

注意D选项和C选项的区别，严谨

问题：

解答：

这里，头指针并不一定在链尾，可能在链内，所以寻找尾指针可能需要O(n)复杂度

问题：

解答：

(2)简答题

问题：

解答：

五、队列的应用

其中 1.树的层序遍历 和 2.图的广度优先遍历 在后续的树、图章节详细介绍。

1.树的层序遍历

2.图的广度优先遍历

3.队列在操作系统中的应用

4.习题总结

(1)简答题

问题：注意算法思想

解答：

六、矩阵的压缩存储

        矩阵作为线性代数中的一个核心概念，广泛应用于各个领域，但其存储方式并非总是最优的。因此，对于大型矩阵或者具有特殊结构的矩阵，压缩存储成为了提高效率的关键。

        矩阵的压缩存储主要关注于如何在不损失信息的前提下，尽可能地减少存储空间的使用。这种存储方式通常针对具有特殊结构或性质的矩阵。

        对于稀疏矩阵元素的存储同样是矩阵存储的重要议题：

        稀疏矩阵是一种元素大部分为零的矩阵。对于这类矩阵，存储非零元素的位置和值往往比存储所有元素更为高效。

1.数组的存储结构

(1)一维数组

(2)二维数组

※注意行优先和列优先存储逻辑上和物理上的对应关系

行优先存储：

列优先存储：

2.特殊矩阵的存储（不要背公式）

        这部分不要背公式，要自己多去推导一下，这块需要灵活应对。考试的时候一般来说不会考具体公式，会问你第几行第几列的元素存在数组中什么位置，或者反过来问。

(1)对称矩阵

行优先存储：

列优先存储：

(2)三角矩阵

下三角矩阵：

上三角矩阵：

(3)三对角矩阵

(4)稀疏矩阵

①顺序存储

②十字链表法

（注意结点中各部分的含义，理解记忆，很重要！！2024年考试真题刚考过）

(5)总结

(6)常见问题

3.易错题总结

(1)选择题

问题：

解答：

问题：

解答：

        看准B数组下标是从哪里开始的

七、本章归纳总结

八、参考

        📚课件来源：王道考研

        📚课本及题目：《2024数据结构考研复习指导-王道论坛》

---

欢迎大家交流学习，如有错误请批评指正！

下一章：字符串

考研系列-数据结构第四章：字符串-CSDN博客文章浏览阅读628次。本文是408考研付费专栏系列-数据结构字符串章节，本文详细地总结了字符串的基本概念，总结了顺序存储和链式存储的结构，还对模式匹配算法（主要是kmp算法的next数组计算）进行了详细归纳总结，对考研复习有比较好的参考意义。https://blog.csdn.net/hehe_soft_engineer/article/details/139637627

---