文章目录

• 概述
• 重点/难点/要点
• 知识点整理
• 练习

概述

栈和队列是常用的基本数据结构，不仅直接用于描述问题，而且作为辅助数据结构大量用于算法实现中。从数据元素间的逻辑关系看，栈和队列是线性结构；从操作方式和操作集合看，栈和队列与线性表有很多不同，有各自的特殊性，但都是操作受限的线性表。本章知识点的组织结构如下图所示：

重点/难点/要点

本章的重点是：

栈和队列的操作特性；

栈和队列基本操作的实现。

本章的难点是：

循环队列的存储方法；

循环队列中队空和队满的判定条件。

栈学习要点：
对于栈要抓住一条明线：栈的逻辑结构→栈的存储结构→栈的实现。
对于栈的逻辑结构，要从栈的定义入手，在与线性表的定义和操作比较的基础上，得出栈的操作特性，最后给出栈的抽象数据类型定义。
对于栈的存储结构要把握两条支线：顺序栈和链栈，栈的存储结构及实现都与线性表类似，本质上是线性表的简化。
对于栈的主要抓住以下三条暗线。

顺序栈和顺序表的比较：将顺序栈与顺序表的存储方法进行比较，将顺序栈的算法实现与顺序表的算法实现进行比较。

链栈和单链表的比较：将链栈与单链表的存储方法进行比较，将链栈的算法实现与单链表的算法实现进行比较。

顺序栈和链栈的比较；将顺序栈与链栈的存储方法进行比较，将顺序栈和链栈的算法实现进行比较。

队列学习要点：
对于队列的教学要抓住一条明线：队列的逻辑结构→队列的存储结构→队列的实现。
对于队列的逻辑结构，要从队列的定义出发，在与线性表的定义和操作比较的基础上，得出队列的操作特性，最后给出队列的抽象数据类型定义。
对于队列的存储结构要把握两条支线：循环队列和链队列，队列的存储结构及实现与线性表类似，本质上是线性表的简化。
队列的暗线与栈的暗线类似，此外，还要把握以下两条暗线。

栈和队列的比较：将二者的操作特性进行比较，将二者的存储结构进行比较，将二者的基本操作及其实现进行比较，在不断比较的过程中加深对栈和队列的理解。

循环队列的引入过程：不要直接引入循环队列存储方法，而要贯彻提出问题、分析问题、解决问题的方式逐渐引入循环队列，一方面训练逻辑思维能力，另一方面也体现了存储结构的灵活性。

知识点整理

栈是限定仅在表尾进行插入和删除操作的线性表。栈中元素除了具有线性关系外，还具有后进先出的特性。

栈的顺序存储结构称为顺序栈，顺序栈本质上是顺序表的简化。通常把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在数组中的位置。

实现顺序栈基本操作的算法的时间复杂度均为O(1)。

栈的链接存储结构称为链栈，通常用单链表表示，并且不用附加头结点。

链栈的插入和删除操作只需处理栈顶即开始结点的情况，其时间复杂度均为O(1)。

队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。队列中的元素除了具有线性关系外，还具有先进先出特性。

顺序队列会出现假溢出问题，解决的办法是用首尾相接的顺序存储结构，称为循环队列。在循环队列中，凡是涉及队头或队尾指针的修改都需要将其求模。

在循环队列中，队空的判定条件是：队头指针=队尾指针；在浪费一个存储单元的情况下，队满的判定条件是：（队尾指针+1）%数组长度=队头指针。

队列的链接存储结构称为链队列。链队列通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。

链队列基本操作的实现本质上也是单链表操作的简化，插入只考虑在链队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均为O(1)。

练习

栈
在栈满的情况下不能做进栈操作，否则将产生上溢，因此对于入栈操作首先要判断是否栈满。（×）
栈结构只允许在栈顶进行存取操作，所有基本操作的时间复杂度均是O(1)。（√）
三个元素按a、b、c的次序进栈，且每个元素只允许进一次栈，则出栈序列一定是abc。（×）
在顺序栈的类定义中，成员变量top是指针类型。（×）
设top表示栈顶元素所在下标，顺序栈的栈空条件是（B），栈满条件是（D）。
A.top=0 B.top=-1 C.top=StackSize D.top=StackSize-1
链栈附设头结点不会使插入、删除等基本操作更加方便。（√）
在链栈中执行入栈操作需要修改两个指针，同单链表的插入操作一样，修改指针有先后顺序。（√）
在顺序栈和链栈中，语句“top- -；”实现将top指向当前栈顶元素的下一个元素。（×）

队列
有三个元素按a、b、c的顺序入队，每个元素只能入队一次，则出队序列只能是abc。（√）
在顺序队列中，入队操作和出队操作的时间复杂度均是O(1)。（×）
由于队列的单向移动性，顺序队列一定会发生假溢出现象。（×）
由于队列只允许在线性表的两端执行存取操作，所有基本操作的时间复杂度均为O(1)。（√）
设存储循环队列的数组长度为m，则(rear+1)%m实现将rear的值在循环意义下加1。（√）
在链队列中附设头结点，能够使入队和出队操作更加方便。（√）
在循环队列中，设front指向队头元素的前一个位置，则当前的队头元素是（C）。
A.data[front] B.data[++front] C.data[(front+1)%m] D.data[front++]
在链队列中，出队操作在队头执行，与rear指针无关。（B）（要判空）
若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为4和2，则从队列中删除一个元素，再增加两个元素后，rear的值是（0），front的值是（3）。

参考资料：《数据结构（从概念到C++实现）》清华大学出版社，王红梅

总结

以上是生活随笔为你收集整理的栈和队列学习要点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。