资源描述：
《数据结构(C语言版)朱昌杰》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章栈和队列本章知识要点：栈和队列的基本概念栈和队列的顺序存储结构和链式存储结构栈和队列的应用3.1栈栈是一种特殊的线性表，它的逻辑结构和存储结构与线性表相同，其特殊性体现在“运算受限”，即无论往表中插入元素还是删除表中已有元素，都被限制在线性表的一端进行。一般将表尾作为操作端，如图3.1所示。图3.1操作仅在表一端进行3.1.1栈的定义栈是限制在表的一端进行插入和删除操作的线性表。能够进行操作的一端是浮动端，称为栈顶，通常用一个“栈顶指针”指示，它的位置会随着操作而发生变化；与此相对，表的另一端是固定端，称为栈底。如同线性表可以为空表一样，当栈中没有元素时称为空栈。往栈中插入元素的操
2、作称为入栈，删除栈中元素的操作称为出栈。如图3.2表示了一个栈。图3.2栈的示意图根据栈的运算特性，所有操作都只在栈顶进行。如果将数据元素按照a1,a2,a3,…,an的顺序依次入栈，则此时a1在栈底，an在栈顶，如图3.2所示。当要取出数据时，则必须按an,an−1,…,a1的顺序进行。由此可知，an作为栈顶元素总是最后入栈的，而最先出栈；a1作为栈底元素总是最先入栈的，而最后出栈。栈按照这种后进先出(LIFO，LastInFirstOut)或者先进后出(FILO，FirstInLastOut)的原则来组织数据的，因此，它也被称为46数据结构（C语言版）后进先出或先进后出的线性表。基于栈的特
3、性，栈的抽象数据类型定义如下：ADTStack{数据对象D：D＝{ai
4、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系R：R＝{
5、ai-1,ai∈D,i=2,…,n}约定an端为栈顶，a1端为栈底。基本操作P：InitStack(S)操作结果：构造一个空栈SStackEmpty(S)初始条件：栈S已存在操作结果：若栈S为空栈,则返回TRUE,否则返回FALSEStackFull(S)初始条件：栈S已存在操作结果：若栈S满,则返回TRUE,否则返回FALSEGetTop(S,e)初始条件：栈S已存在操作结果：若栈S非空,用e返回S的栈顶元素Push(S,e)初始条件
6、：栈S已存在操作结果：若栈S不满,插入元素e为新的栈顶元素Pop(S,e)初始条件：栈S已存在且非空操作结果：若栈S非空,删除S的栈顶元素,并用e返回其值}ADTStack3.1.2栈的顺序存储结构采用顺序存储结构的栈称为顺序栈，它需要一段连续的存储空间来存储栈中元素。1.顺序栈的类型定义类似于顺序表的定义，通常用预先设定的足够大的一维数组来存放数据。由于栈顶会随着插入和删除操作而发生变化，用整型变量top作为栈顶指针指示栈顶的当前位置。栈底位置固定不变，可以设置在数组的任意端，一般将数组的下标端作为栈底。顺序栈的类型描述如下：#defineMAXSIZE100typedefstruct{El
7、emtypedata[MAXSIZE];inttop;}SqStack;在顺序栈中，用于指示栈顶的当前位置的top是整型，它的实质是栈顶元素在数组中的下标。栈顶指针top直接反映出栈的当前状态：空栈时，栈顶指针top为−1；栈满时，栈顶指针top为MAXSIZE−1；入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。第3章栈和队列47图3.3所示为MAXSIZE为6的顺序栈中数据元素和栈顶指针top的变化情况。其中，图3.3(a)表示空栈；图3.3(b)表示元素a进栈，top指示的是当前栈顶的位置；图3.3(c)表示b、c、d、e、f依次进栈后栈满的情况；元素f、e、d依次出栈后的情况如
8、图3.3(d)所示，top为当前栈顶元素c的位置；图3.3(e)表示元素c、b、a继续出栈又重新回到空栈状态。图3.3栈顶指针top与栈中数据元素的关系2.顺序栈的算法实现（1）初始化栈（置栈空）初始化栈主要是分配存储空间，并将栈顶指针置为−1。intInitStack(SqStack*s){//创建一个空栈由指针s指向if((s=(SqStack*)malloc(sizeof(SqStack)))==NULL)returnERROR;s->top=-1;returnOK;}（2）判栈空intStackEmpty(SqStack*s)//判栈为空栈时返回值为真,反之为假{return(s-
9、>top==-1?TRUE:FALSE);}（3）判栈满intStackFull(SqStack*s)//判栈为满栈时返回值为真,反之为假{return(s->top==MAXSIZE-1?TRUE:FALSE);}（4）进栈进栈时应首先判栈满，若栈不满则将栈顶指针top上移，存入元素。intPush(SqStack*s,Elemtypee){//将元素e插入到栈中,作为新栈顶if(Stac
