安徽农业大学计算机科学与技术课件

1、* 栈栈* 栈的应用栈的应用* 队列队列* 队列的应用队列的应用 3.1.1 3.1.1 栈的定义及基本运算栈的定义及基本运算 栈栈(Stack)(Stack)是限制在表的一端进行插入和删除运算的是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶线性表，通常称插入、删除的这一端为栈顶(Top)(Top)，另一，另一端为栈底端为栈底(Bottom)(Bottom)。当表中没有元素时称为空栈。当表中没有元素时称为空栈。假设栈假设栈S=(a1S=(a1，a2a2，a3a3，an)an)，则，则a1a1称为栈底称为栈底元素，元素，anan为栈顶元素。栈中元素按为栈顶元素。栈中元

2、素按a1a1，a2a2，a3a3，anan的次序进栈，退栈的第一个的次序进栈，退栈的第一个元素应为栈顶元素。即，栈的修改元素应为栈顶元素。即，栈的修改是按后进先出的原则进行的。因此，栈是按后进先出的原则进行的。因此，栈称为后进先出表（称为后进先出表（LIFOLIFO）。 3.1.2 3.1.2 顺序栈顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固性表。因此，可用数组来实现顺序

3、栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而一个端点；栈顶位置是随着进栈和退栈操作而 变化的，故需用一个整型变量变化的，故需用一个整型变量toptop来指示当前来指示当前 栈顶的位置，通常称栈顶的位置，通常称toptop为栈顶指针。为栈顶指针。 因此，顺序栈的类型定义只需将顺序表因此，顺序栈的类型定义只需将顺序表 的类型定义中的长度属性改为的类型定义中的长度属性改为toptop即可即可。顺序栈的类型定义如下：顺序栈的类型定义如下： # define StackSize 100 t

4、ypedef char datatype; typedef struct datatype datastacksize; int top; seqstack; top6 5 4 3 2 1 0-1例、例、一叠书或一叠盘子。一叠书或一叠盘子。 栈的抽象数据类型的定义如下：栈的抽象数据类型的定义如下： a n a n-1 a2 a1栈顶栈顶 栈底栈底栈栈s=(a1,a2,s=(a1,a2,an),an) 设设S是是SeqStack类型的指针变量。若栈底位置在向量类型的指针变量。若栈底位置在向量的低端，即的低端，即sdata0是栈底元素，那么栈顶指针是栈底元素，那么栈顶指针stop是正向增加的，即进

5、栈时需将是正向增加的，即进栈时需将stop加加1，退栈时需将，退栈时需将stop 减减1。因此，。因此，stoptop =stacksize-1表示栈满。当栈满时再做进栈运算必定产生表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称空间溢出，简称“上溢上溢”;当栈空时再做退栈运算也将产当栈空时再做退栈运算也将产生溢出，简称生溢出，简称“下溢下溢”。上溢是一种出错状态，应该设。上溢是一种出错状态，应该设法避免法避免 之；下溢则可能是正常现象，因为栈在之；下溢则可能是正常现象，因为栈在 程序中使用时，其初态或终态都是程序中使用时，其初态或终态都是 空栈，所以下溢常常用来作为程序控制空栈，所以下溢

6、常常用来作为程序控制 转移的条件。转移的条件。 void initstack ( seqstack *s ) s top = 0; int stackempty ( seqstack *s ) return ( s top = 0 ); int stackfull ( seqstack *s ) return ( s top = stacksize - 1 ); void push ( seqstack *s，datatype x ) if ( stackfull (s) ) error ( “stack overflow” ); s data +stop = x; datatype pop

7、( seqstack *s ) if ( stackempty (s) ) error ( “stack underflow” ); x = s data top; s top -; return (x) /return(sdatastop-); Datatype gettop ( seqstack *s ) if ( stackempty (s) ) error ( “stack is empty” ); return s data s top ; 例：例：对于一个栈，给出输入项对于一个栈，给出输入项A A、B B、C C，如果输入项序列，如果输入项序列由由ABCABC组成，试给出所有可能的

8、输出序列。组成，试给出所有可能的输出序列。 A进进 A出出 B进进 B出出 C进进 C出出 ABC A进进 A出出 B进进 C进进 C出出 B出出 ACB A进进 B进进 B出出 A出出 C进进 C出出 BAC A进进 B进进 B出出 C进进 C出出 A出出 BCA A进进 B进进 C进进 C出出 B出出 A出出 CBA 不可能产生输出序列不可能产生输出序列CAB 3.1.3 3.1.3 链栈链栈 栈的链式存储结构称为链栈，它的运算是受限的栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行

9、操作，故链表没有必要像单由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下：链栈的类型说明如下：栈的链接存储结构栈的链接存储结构链栈的结点定义链栈的结点定义 typedef int datatype; typedef struct node datatype data; struct node *next; linkstack; 栈的链接表示栈的链接表示 链式栈链式栈 链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行 链式栈的栈顶

10、在链头链式栈的栈顶在链头 适合于多栈操作适合于多栈操作linkstack *PUSHLSTACK ( linkstack *top, datatype x ) linkstack *p; p malloc ( sizeof ( linkstack ) ); p - data x; p - next top; top = p; return p; linkstack *POPLSTACK ( linkstack *top, datatype datap ) linkstack *p; if ( top = NULL ) printf( “under flown” ); return NULL;

11、else *datap top - data; p top; top top - next; free ( p ); return top; 3.2 3.2 栈的应用举例栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。为程序设计中常用的工具。以下是几个栈应用的例子。 十进制十进制N N和其它进制数的转换是计算机实现和其它进制数的转换是计算机实现 计算的基本问题计算的基本问题, ,其解决方法很多其解决方法很多, ,其中一个其中一个 简单算法基于下列原理简单算法基于下列原理: : N =( n d

12、iv d ) N =( n div d ) * * d + n mod d d + n mod d ( ( 其中其中:div:div为整除运算为整除运算,mod,mod为求余运算为求余运算) )栈的应用举例栈的应用举例-数制转换数制转换例如例如 ( (1348)1348)1010=(2504)=(2504)8 8，其运算过程如下其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) initstack ( s ); scanf ( “ % ” , n); while( n ) push ( s

13、 , n % 8 ); n = n / 8; while( ! Stackempty ( s ) pop ( s , e ); printf ( “ % d ” , e ); seqstack s ;EDIT( ) char c ; SETNULL ( & s ) ; c getchar ( ); while ( c ! = * ) if ( c = = # ) POP ( & s ) ; else if ( c = = ) SETNULL ( & s ) ; else PUSH ( & s , c ) ; c getchar ( ) ; 栈栈的的应应用用举举例例文文字字编编辑辑器器栈的应用举

14、例表达式计算栈的应用举例表达式计算中缀表达式：中缀表达式：A + ( B C / D) E后缀表达式：后缀表达式：ABCD/E+后缀表达式特点后缀表达式特点1、与相应的中缀表达式中的操作数次序相同、与相应的中缀表达式中的操作数次序相同2、没有括号、没有括号后缀表达式的处理过程后缀表达式的处理过程操作顺序操作顺序后缀表达式后缀表达式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T4中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式()#(#=当前运算符当前运算符栈顶运算符栈顶运算符1 1、如为操作数，直接输出到（链表）队列；、如为操作数，

15、直接输出到（链表）队列；2 2、如当前运算符高于栈顶运算符，入栈；、如当前运算符高于栈顶运算符，入栈；3 3、如当前运算符低于栈顶运算符，栈顶运算符退栈，并输、如当前运算符低于栈顶运算符，栈顶运算符退栈，并输出到（链表）队列，当前运算符再与栈顶运算符比较；出到（链表）队列，当前运算符再与栈顶运算符比较；4 4、如当前运算符等于栈顶运算符，且栈顶运算、如当前运算符等于栈顶运算符，且栈顶运算符为符为“（”，当前运算符为，当前运算符为“）”，则栈顶运算符，则栈顶运算符退栈，继续读下一符号；退栈，继续读下一符号；5 5、如当前运算符等于栈顶运算符，、如当前运算符等于栈顶运算符，且栈顶运算符为且栈顶运算

16、符为“# #”，当前运算符也为，当前运算符也为“# #”，则栈顶运算符退栈，比较结束；则栈顶运算符退栈，比较结束；步骤步骤中缀表达式中缀表达式STACK输出输出1A(BCD)E#2(BCD)E#A3(BCD)E# A4BCD)E# (A5CD)E# (AB6CD)E# +(AB7D)E# (ABC8D)E# (/ABC9)E# (/ABCD10)E# # (ABCD/11)E# # (ABCD/ 12E# # ABCD/ 13E# # ABCD/ 14# # ABCD/ E15# # +ABCD/ E 16# #ABCD/ E 出出口口入口入口迷迷宫宫求求解解 栈的应用栈的应用 过程的嵌套调用

17、过程的嵌套调用r主程序主程序srrrs子过程子过程1rst子过程子过程2rst子过程子过程3例例: : 递归过程及其实现递归过程及其实现 递归：函数直接或间接的调用自身叫递归：函数直接或间接的调用自身叫递归递归 实现：建立递归工作栈实现：建立递归工作栈#include int Multiply( int M,int N ) int Result; if ( N = 1 ) Result = M; Else Result = M + Multiply(M,N-1); return Result; int main (void) int NumA = 13; int NumB = 4; int P

18、roduct; Product = multiply(NumA,NumB); Printf(“%d * %d = %d”,NumA,NumB,Product); return 1; 运行结果：运行结果： 13 * 4 = 52程序流程：程序流程：Multiply(13,4)M = 13N = 4N != 1Result =13 + Multiply(13,3)return ResultM = 13N = 3N != 1Result =13 + Multiply(13,2)return ResultM = 13N = 2N != 1Result =13 + Multiply(13,1)retur

19、n ResultM = 13N = 1N = 1Result =13return Result52392613从以上的例子中，我们可以归纳出几个解递归问题的步骤：步骤1：了解题意是否适合用递归来解题。步骤2：决定递归结束条件(Stopping Cases)。步骤3：决定递归执行部分(Recursive Step)。 3.3 3.3 队列队列 队列的定义及特点队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表的另一端进行删除的线性表 队尾队尾(rear)(rear)允许插入的一端允许插入的一端 队头队头(front)

20、(front)允许删除的一端允许删除的一端 队列特点：先进先出队列特点：先进先出 ( ( FIFO ) )a1 a2 a3.an 入队入队出队出队frontrear队列队列Q=(a1,a2,an) 双端队列双端队列入队入队出队出队入队入队a1 a2 a3.an 端端1 1端端2 2出队出队 链队列链队列 结点定义结点定义typedef struct node int data; struct node *link;JD;头结点头结点 .front队头队头队尾队尾rear设队首、队尾指针设队首、队尾指针front和和rear,front指向头结点，指向头结点，rear指向队尾指向队尾frontr

21、earx入入队队xfrontreary入入队队xyfrontrearx出出队队xyfront rear空队空队front reary出出队队 入队算法入队算法 出队算法出队算法JD *ldcr ( JD *rear , int x ) JD *p; p = ( JD *) malloc ( sizeof ( JD ); p - data = x; p - link = NULL; rear - link = p; rear = p; return ( p );int ldsc ( JD *front , JD *rear ) JD *s; int x; if ( front = = rear

22、) return ( - 1 ); s = front - link; front - link = s - link; if ( s - link = = NULL) rear = front; x = s - data; free ( s ); return ( x ); 队列的顺序存储结构队列的顺序存储结构 实现：用一维数组实现实现：用一维数组实现sqMfront=0rear=0123450队空队空123450frontJ1,J2,J3入队入队J1J2J3rearrear123450J4,J5,J6入队入队J4J5J6front设两个指针设两个指针front,rear,约定：约定：rear指示队尾元素指示队尾元素下一位置下一位置；front指示队头元素指示队头元素；初值初值front=rear=0空队列条件：空队列条件：front=rear入队列：入队列：sq+rear=x;出队列：出队列：x=sq+front;rearrearfrontJ1,J2,J3出队出队frontfrontrear123450J1J2J3front 存在问题存在问题设数组维数为设数组维数为M，则：则： 当当front=0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出 当当front 0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢