资源描述：
《2 栈、队列和数组》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2讲栈、队列和数组本章主要掌握如下内容：栈和队列的基本概念，栈和队列的顺序存储结构及链式存储结构，栈和队列的应用，特殊矩阵的压缩存储。知识点分析一．栈1．栈的基本概念1）栈的定义：堆栈是一种特殊的线性表，它的操作被限制在某一端，即栈顶。若有一个栈S=（a1,a2,…an）称a1为栈底结点，an为栈顶结点。习惯上称插入结点为入栈(压栈，进栈)，删除结点成为出栈（弹栈）。最先进栈的结点必定最后出栈，最后进栈的结点必定最先出栈，因此，栈是一种具有后进先出特性的数据结构。2）栈的抽象数据定义假设堆栈S有数据对象D＝{ai
2、ai∈ElemSet，i=1
3、,2,3,…,n，n>=0},数据元素之间的关系R＝{
4、ai-1,ai∈D,i=1,2,…,n},约定an为栈顶，ai为栈底。则堆栈S的基本操作如下所示：lInitStack(&S)：其作用是构造一个空栈；lDestoryStack(&S)：其作用是销毁当前的堆栈S；lClearStack(&L)：清空堆栈S，使之成为空栈；lStackLength(L)：返回堆栈S的长度，即堆栈中数据元素的个数；lGetTop(S，&e)：用e返回堆栈S的栈顶元素；（注意不是出栈）lPush(&S,e)：将元素e插入到堆栈中，作为堆栈S的新的
5、栈顶元素；称为入栈、进栈或压栈；lPop(&S,&e)：删除堆栈S的栈顶元素，并将其用e返回其值；称为出栈或弹栈；lStackTraverse(S,visit())：从栈底到栈顶对每个数据元素利用函数visit()访问。可以看出，堆栈S的基本操作同线性表非常相近，不同之处在于堆栈增加了对数据元素的访问限制：线性表允许以任何方式访问其数据元素，而堆栈只允许从栈顶访问数据元素。『经典例题解析』1.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序【答案】B。【解析】略。2.一个栈的输入序列为123…n，若输出序列的第一个元
6、素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i【答案】B。【解析】按照堆栈“后进先出”的特点，n是最后一个入栈的，即n为栈顶元素。若输出的第一个元素为n，则其余所有元素必定仍在堆栈中。第一个输出元素为n，则第二个输出元素为n-1，第i个输出元素为n-i+1，最后一个（第n个）输出元素为1。3.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.234156【答案】C。【解析】考查堆栈“后进先出”的特点。对选项A来说，第一个出
7、栈元素是5，因为6先于5进栈，所以必定在5之后出栈，其余的元素出栈顺序任意；对选项B来说，第一个出栈元素是4，所以5和6两个元素必定在4之后依次出栈；对选项C来说，第一个出栈元素是3，则必有4、5、6三个元素依次在3后面出栈，但是选项C中的顺序是3、4、6、5,这是不符合要求的；对选项D来说，第一个出栈元素是2，则必有3、4、5、6依次在2后面出栈，D也是符合要求的，因此答案选C。总结：这种问题如何解决呢？我们看第一个出栈元素，然后确定先于第一个元素进栈的所有其它元素，这些元素一定在第一个出栈元素之后顺序出栈。如果第一个元素仍然无法判断出来，可
8、继续看后面的元素，依次类推。举例如下：假设第一个出栈的元素是1，则出栈顺序一定是6、5、4、3、2、1，没有其它情况。假设第一个出栈的元素是2，则出栈顺序可能有：213456、231456、234156、234516、234561（可首先把23456写出，然后可将1插到2之后的任意位置）假设第一个出栈的元素是3，则出栈顺序可能有：312456、341256、345126、345612但是314526是不能的。因为3出栈之后，当前栈中仍有4、5、6三个元素，如果下一个是1出栈，则肯定先让2进栈，再让1进栈，然后1出栈，此时栈顶就变成2了，则下一个
9、出栈的只能是2，而不能是4。2．栈的顺序存储结构1）数据定义#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//指当前堆栈可用的最大容量}SqStack;重要说明：lbase始终指向栈底位置，在堆栈操作过程中，base的取值保持不变。如果base==NULL，则说明栈结构不存在；ltop为栈顶指针，其初始值指向栈底，即有：
10、base==top，这也可以看作是栈空的标志。删除栈顶元素时top减1，插入新的元素时top增1，因此，非空栈的栈顶指针始终指向当前栈顶元素的下一个位
