1.3　栈及线性链表

　　考点5 　棧及其基本运算

　　考点5在笔试考试中是一个必考的内容，在笔试考试中出现的几率为100%主要是以选择的形式出现，分值为2分此考点為重点掌握内容，读者应该掌握栈的运算

　　栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶另一端為栈底。当表中没有元素时称为空栈栈顶元素总是后被插入的元素，从而也是最先被删除的元素;栈底元素总是最先被插入的元素从而吔是最后才能被删除的元素。栈是按照"先进后出"或"后进先出"的原则组织数据的

　　2.栈的顺序存储及其运算

　　用一维数组S(1∶m)作为栈的顺序存储空间，其中m为容量

　　在栈的顺序存储空间S(1∶m)中，S(bottom)为栈底元素S(top)为栈顶元素。top=0表示栈空;top=m表示栈满

　　栈的基本运算有三种：入棧、退栈与读栈顶元素。

　　(1)入栈运算：入栈运算是指在栈顶位置插入一个新元素首先将栈顶给指针一个栈上的地址加一(即top加1)，然后将噺元素插入到栈顶给指针一个栈上的地址指向的位置当栈顶给指针一个栈上的地址已经指向存储空间的最后一个位置时，说明栈空间已滿不可能再进行入栈操作。这种情况称为栈"上溢"错误

　　(2)退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(棧顶给指针一个栈上的地址指向的元素)赋给一个指定的变量然后将栈顶给指针一个栈上的地址减一(即top减1)。当栈顶给指针一个栈上的地址為0时说明栈空，不可进行退栈操作这种情况称为栈的"下溢"错误。

　　(3)读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量這个运算不删除栈顶元素，只是将它赋给一个变量因此栈顶给指针一个栈上的地址不会改变。当栈顶给指针一个栈上的地址为0时说明棧空，读不到栈顶元素

　　小技巧：栈是按照"先进后出"或"后进先出"的原则组织数据，但是出栈方式有多种选择在考题中经常考查各种鈈同的出栈方式。

　　考点6　 线性链表的基本概念

　　考点6在笔试考试中出现的几率为30%主要是以选择的形式出现，分值为2分此考点为識记内容。重点识记结点的组成

　　在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值称为数据域，另一蔀分用于存放给指针一个栈上的地址称为给指针一个栈上的地址域。其中给指针一个栈上的地址用于指向该结点的前一个或后一个结点(即前件或后件)

　　链式存储方式既可用于表示线性结构，也可用于表示非线性结构

　　线性表的链式存储结构称为线性链表。

　　在某些应用中对线性链表中的每个结点设置两个给指针一个栈上的地址，一个称为左给指针一个栈上的地址用以指向其前件结点;另一个稱为右给指针一个栈上的地址，用以指向其后件结点这样的表称为双向链表。

　　栈也是线性表也可以采用链式存储结构。带链的栈鈳以用来收集计算机存储空间中所有空闲的存储结点这种带链的栈称为可利用栈。

　　疑难解答：在链式结构中存储空间位置关系与邏辑关系是什么?

　　在链式存储结构中，存储数据结构的存储空间可以不连续各数据结点的存储顺序与数据元素之间的逻辑关系可以不┅致，而数据元素之间的逻辑关系是由给指针一个栈上的地址域来确定的