Data Structure Tutorial (5th Edition) learning to guide the data Structure Course series of university textbooks(Chinese Edition)

本书是《数据结构教程（第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指向队头元