第三章栈和队列A(NEW)

1、1. 定义定义与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)关系关系。用用或或存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在运算，且访问结点时依照运算，且访问结点时依照（LIFOLIFO）或）或（FILOFILO）的原则。）的原则。关键是编写关键是编写和和函数，具体实现依顺函数，具体实现依顺序栈或链栈的存储结构有别而不同。序栈或链栈的存储结构有别而不同。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构限定只能在表的限定只能在表的进行插入和删除运算的进行插入和删除运算的线性表。线性表。即栈顶即栈顶基本操作有：基本操作有：建

2、栈、判断栈满或栈空、入栈、出栈、建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。读栈顶元素值，等等。3.1 栈3.1.1 栈的基本概念栈的基本概念u 栈：限制仅在表尾进行插入和删除操作的线性表栈：限制仅在表尾进行插入和删除操作的线性表u 栈的操作特性：按先进后出栈的操作特性：按先进后出(F I L O )或后进先出或后进先出(I)的原则的原则 栈顶栈顶(top)：允许插入和删除的一端。：允许插入和删除的一端。 约定约定top始终指向栈顶位置。始终指向栈顶位置。 栈底栈底(bottom): 不允许插入和删除的一端。不允许插入和删除的一端。 入栈顺序：入栈顺序：e0 e1 e2 en-2 e

3、n-1 出栈顺序：出栈顺序：en-1 en-2 e2 e1 e0en-1e0e1en-2 进栈（Push） 出栈（Pop）栈顶 top栈底bottom 例例1 一个栈的输入序列为一个栈的输入序列为1,2,3，若在，若在入栈的过程中入栈的过程中允许出栈允许出栈，则可能得到的出栈序列是什么？，则可能得到的出栈序列是什么？答：答： 可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，

4、2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5 5种可能性。种可能性。例例2 2：一个栈的输入序列是一个栈的输入序列是12345，若在，若在入栈的入栈的过程中允许出栈过程中允许出栈，则栈的输出序列则栈的输出序列43512可能实可能实现吗现吗？12345的输出呢？的输出呢？答：答：4351243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不能实现；顺序不能实现；12345123

5、45的输出可以实现，每压入一数便立即弹出即可。的输出可以实现，每压入一数便立即弹出即可。 例例3：设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、）、D）可以，）可以， B）、）、C）不行。）不行。讨论：有无通用的判别原则？讨论：有无通用的判别原则？有！若输入序列是有！若输入序列是 ,P,Pj jP Pk kP Pi i (P(Pj jPPk kPM)上溢 else stop+top+=e;Push (B);Push (C);Push (D)

6、;toptoptoptop低地址低地址LPush (A);高地址高地址MBCD顺序栈出栈操作顺序栈出栈操作例如从栈中取出例如从栈中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD核心语句：核心语句：Pop ( );顺序栈出栈函数顺序栈出栈函数POP()POP()status Pop( )status Pop( ) if(top=L) if(top=L) 下溢下溢 else e=selse e=s-top-top; ; return(e); return(e); Pop ( );Printf( Pop () );173.1.3 栈的链式存储结构栈的链式

7、存储结构ls栈顶栈顶栈底栈底data next（栈顶指针）（栈顶指针）链栈的类型定义：链栈的类型定义：typedef struct stnod DataType data; /*存储结点数据存储结点数据*/ struct stnode *next ; /*指针域指针域*/LinkStack;18栈的基本运算算法：栈的基本运算算法： (1)初始化栈运算初始化栈运算功能：创建一个带头结点的链栈，头结点指针功能：创建一个带头结点的链栈，头结点指针ls； 用用ls-next=NULL标识栈为空栈。标识栈为空栈。 void InitStack(LinkStack *&ls) ls=(LinkStack

8、*)malloc(sizeof(LinkStack); ls-next=NULL; 19(2) 判断栈空运算判断栈空运算功能：若栈为空则返回值功能：若栈为空则返回值1，否则返，否则返 回值回值0。int StackEmpty(LinkStack *ls) if(ls-next=NULL) return 1; else return 0;20 (3) 进栈运算进栈运算 void Push(LinkStack *ls, DataType x) LinkStack *p; p=(LinkStack*)malloc(Sizeof(LinkStack); p-data=x; p-next=ls-next; ls-next=p; 21(4)出栈运算出栈运算功能功能: 将栈顶结点的将栈顶结点的data域值赋给域值赋给x, 然后删除该栈顶结点。然后删除该栈顶结点。 int Pop(LinkStack *ls，DataType &x) LinkStack *p; if(ls-next=NULL) /*栈空，下溢出栈空，下溢出*/ return 0; else p=ls-next; x=p-data; ls-next=p-next; free(p); return 1; 22(5)取栈顶元素运算算法取栈顶