数据结构教程学习指导

各章中除给出本章练习题的参考答案外，还总结了本章的知识体系结构，并补充了大量的练习题并予以解析。附录中给出了几份近年来本科生、研究生数据结构考试试题及参考答案。书中列出了全部的练习题，因此自成一体，可以脱离主教材单独使用。

　　本书是《数据结构教程（第5版）》（李春葆等编著，清华大学出版社出版）的配套学习指导书。两书章节一一对应，内容包括绪论、线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序和文件。各章中除给出本章练习题的参考答案以外还总结了本章的知识体系结构，并补充了大量的练习题且予以解析，因此自成一体，可以脱离主教材单独使用。

　　本书适合高等院校计算机和相关专业的本科生及研究生使用。

第3章栈和队列








3.1本章知识体系
1. 知识结构图



本章的知识结构如图3.1所示。



图3.1第3章知识结构图


2. 基本知识点
(1) 栈、队列和线性表的异同。
(2) 顺序栈的基本运算算法设计。
(3) 链栈的基本运算算法设计。
(4) 顺序队的基本运算算法设计。
(5) 环形队列和非环形队列的特点。
(6) 链队的基本运算算法设计。
(7) 利用栈/队列求解复杂的应用问题。
3. 要点归纳
(1) 栈和队列的共同点是它们的数据元素都呈线性关系，且只允许在端点处插入和删除元素。
(2) 栈是一种“后进先出”的数据结构，只能在同一端进行元素的插入和删除。
(3) 栈可以采用顺序栈和链栈两类存储结构。
(4) n个不同元素的进栈顺序和出栈顺序不一定相同。
(5) 在顺序栈中通常用栈顶指针指向当前栈顶的元素。
(6) 在顺序栈中用数组data［0..MaxSize-1］存放栈中元素，只能将一端作为栈底，另一端作为栈顶，通常的做法是将data［0］端作为栈底，data［MaxSize-1］端作为栈顶。用户也可以将data［MaxSize-1］端作为栈底，data［0］端作为栈顶，但不能将中间位置作为栈底或者栈顶。
(7) 初始时栈顶指针top设置为-1，栈空的条件为top=-1，栈满的条件为top=MaxSize-1，元素x的进栈操作是top++; data［top］=x，出栈操作是x=data［top］; top--。这是经典做法，但不是唯一的方法，如果初始时top设置为0，可以设置栈空的条件为top=0，栈满的条件为top=MaxSize，元素x的进栈操作是data［top］=x; top++，出栈操作是top--; x=data［top］。
(8) 在顺序栈或链栈中，进栈和出栈操作不涉及栈中元素的移动。
(9) 在链栈中，由于每个结点是单独分配的，通常不考虑上溢出问题。
(10) 无论是顺序栈还是链栈，进栈和出栈运算的时间复杂度均为O(1)。
(11) 队列是一种“先进先出”的数据结构，只能从一端插入元素，从另一端删除元素。
(12) 队列可以采用顺序队和链队两类存储结构。
(13) n个元素进队的顺序和出队顺序总是一致的。
(14) 在顺序队中的元素个数可以由队头指针和队尾指针计算出来。
(15) 环形队列也是一种顺序队，是通过逻辑方法使其首尾相连的，解决非环形队列的假溢出现象。
(16) 在环形队列中，队头指针f指向队头元素的前一个位置，队尾指针r指向队尾元素，这是一种经典做法，但不是唯一的方法，也可以让队头指针f指向队头元素。
(17) 无论是顺序队还是链队，进队和出队运算的时间复杂度均为O(1)。
(18) 在实际应用中，一般栈和队列都是用来存放临时数据的，如果先保存的元素先处理，应该采用队列； 如果后保存的元素先处理，应该采用栈。

3.2教材中的练习题及参考答案
1. 有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中以元素C、D最先出栈(即C第一个且D第二个出栈)的次序有哪几个？
答： 要使C第一个且D第二个出栈，应是A进栈，B进栈，C进栈，C出栈，D进栈，D出栈，之后可以有以下几种情况：
(1) B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE；
(2) B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA；
(3) E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。
所以可能的次序有CDBAE、CDBEA、CDEBA。
2. 在一个算法中需要建立多个栈(假设3个栈或以上)时可以选用以下3种方案之一，试问这些方案相比各有什么优缺点？
(1) 分别用多个顺序存储空间建立多个独立的顺序栈。
(2) 多个栈共享一个顺序存储空间。
(3) 分别建立多个独立的链栈。
答： (1) 优点是每个栈仅用一个顺序存储空间时操作简单； 缺点是分配空间小了容易产生溢出，分配空间大了容易造成浪费，各栈不能共享空间。
(2) 优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出； 缺点是当一个栈满时要向左、右查询有无空闲单元，如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时要查询空闲单元、移动元素和修改栈底、栈顶指针，这一过程计算复杂且十分耗时。
(3) 优点是多个链栈一般不考虑栈的溢出； 缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。
3. 在以下几种存储结构中哪个最适合用作链栈？
(1) 带头结点的单链表。
(2) 不带头结点的循环单链表。
(3) 带头结点的双链表。
答： 栈中元素之间的逻辑关系属线性关系，可以采用单链表、循环单链表和双链表之一来存储，而栈的主要运算是进栈和出栈。
当采用(1)时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。
当采用(2)时，前端作为栈顶，当进栈和出栈时首结点都发生变化，还需要找到尾结点，通过修改其next域使其变为循环单链表，算法的时间复杂度为O(n)。
当采用(3)时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。
但单链表和双链表相比，其存储密度更高，所以本题中最适合用作链栈的是带头结点的单链表。
4. 简述以下算法的功能(假设ElemType为int类型)。

　　前言

　　本书是《数据结构教程(第5版)》（清华大学出版社，以下简称为《教程》）的配套学习指导书。全书分为12章，第1章为绪论；第2章为线性表；第3章为栈和队列；第4章为串；第5章为递归；第6章为数组和广义表；第7章为树和二叉树；第8章为图；第9章为查找；第10章为内排序；第11章为外排序；第12章为文件。本书各章次与《教程》的章次相对应。附录A给出了两份本科生期末考试试题及参考答案，附录B给出了两份研究生入学考试（单考）数据结构部分试题及参考答案，附录C给出了两份全国计算机学科专业考研题数据结构部分试题及参考答案。

　　每章包括以下内容。

　　本章知识体系：高度概括本章知识结构图、基本知识点和要点归纳。

　　教材中的练习题及参考答案：给出了《教程》中对应章节练习题的参考答案。

　　补充练习题及参考答案：列出了大量相关的练习题，并按单项选择题、填空题、判断题、简答题和算法分析题或算法设计题分类，同时给出了这些题目的参考答案。其中许多题目是多年来全国各高校计算机专业的数据结构考研题。

　　书中列出了全部的练习题题目，因此自成一体，可以脱离《教程》单独使用。

　　由于水平所限，尽管编者不遗余力，仍可能存在错误和不足之处，敬请教师和同学们批评指正。

　　编者

　　2017年1月