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

目录

一、栈（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.顺序存储方式实现-顺序栈

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

        

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/730792