第三章栈和队列

1、第三章栈和队列 从数据结构的角度看: 它们和线性表相同，从数据类型的角度看: 它们和线性表不同栈按“后进先出”，队列按“先进先出”3.1 栈的类型定义一、 栈的定义及基本运算1定义：ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。2基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEm

2、pty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S, &e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S, e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S, &e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。 ADT Stack 二栈的存储表示和基本操作的实现1 顺序栈/ 顺序栈#define STACK_INIT_SIZE 100#define STACKINCRE

3、MENT 10#include common.htypedef int SElemType;/accroding problem SelemTypetypedef struct SElemType *base; SElemType *top; int stacksize;SqStack;（1）栈的初始化Status InitStack(SqStack &S) S.base=(SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=ST

4、ACK_INIT_SIZE; return OK;（2）判空int StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE;（3）入栈Status Push(SqStack &S,SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType *) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S

5、.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push_SqStack(4)出栈Status Pop (SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*(-S.top); return OK;/Pop_SqStack（5）得到栈顶元素Status GetTop (SqStack S,SElemType &e) if(S.top=S.base) return ERROR; e=*(S.top-1); return OK;(6)求元素个数int St

6、ackLength(SqStack S) int len=0; SElemType e; while(!StackEmpty (S) Pop_SqStack(S,e); len+; return len;2 链栈/链栈#include common.htypedef int SElemType;typedef struct Node SElemType data; struct Node *next; StackNode,*LinkStack;(1)初始化LinkStack InitStack() return NULL;/Init_LinkStack（2）判空int StackEmpty(L

7、inkStack top)if(top=NULL) return TRUE;else return FALSE;（3）入栈Status Push (LinkStack &top,SElemType e) StackNode *s; s=(StackNode *) malloc(sizeof(StackNode);s-data=e; s-next=top; top=s; return OK;（4）出栈Status Pop (LinkStack &top,SElemType &x) StackNode *p; if(top=NULL) return ERROR; x=top-data; p=top

8、; top=top-next; free(p); return OK;（5）得到栈顶元素 Status GetTop(LinkStack s, Selemtype &e) if(s=NULL) return ERROR; e=s-data; return OK; 3.2 栈的应用举例例1,A BC顺序入栈，出栈的方式有：ABC ACB BAC BCA CBA CBAn个字符顺序入栈，出栈的方式有：例2 数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N = (N div d)d + N mod d (其中：div 为整除运算，m

9、od 为求余运算）例如：（1348)10 = (2504)8 ，其运算过程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2 假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。void conversion () / 对于输入的任意一个非负十进制整数，打印输出/ 与其等值的八进制数Ini

10、tStack(S); / 构造空栈scanf (%d,N);while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion 这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。例2、 括号

11、匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（）或（ ）等为正确的格式，（ ）或（ ）或 ( )均为不正确的格式。检验括号是否匹配的方法可用期待的急迫程度这个概念来描述。例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8int AllBrackets_Test(char *str) SqStack s; char *p,c; InitStack(s); for(p=str;p;p+) if(*p=(|*p=|*p=) Push (s,*p); else if(*p=)|*p=|*p=) if(StackEmpty(s) return FALSE; P

12、op (s,c); if(*p=)&c!=() return FALSE; if(*p=&c!=) return FALSE; if(*p=&c!=) return FALSE; if(!StackEmpty(s) return FALSE; return TRUE;例3 字符串（回文数）对称问题int symmetry(char *str) SqStack s; char *c=str,t; int i=0,j; while(*c+!=0) i+; j=0; c=str; InitStack (s); while(ji/2) Push (s,*c); c+; j+; if(i%2!=0)c+

13、; while(*c!=0) Pop (s,t); if(t=*c) c+; else return FALSE; return TRUE;int Palindrome(char *str)/huiwen zifu char a,*c; LinkStack S; S=InitStack(); c=str; while(*c!=0) Push(S,*c); c+; c=str; while(!StackEmpty(S) Pop(S,a); if(a!=*c) return FALSE; c+; return TRUE;/PaLindrome例4、 表达式求值限于二元运算符的表达式定义:表达式 :

14、= (操作数) + (运算符) + (操作数)操作数 := 简单变量 | 表达式简单变量 : = 标识符 | 无符号整数在计算机中，表达式可以有三种不同的标识方法(以运算符所在不同位置命名)设 Exp = S1 + OP + S2则称 OP + S1 + S2 为表达式的前缀表示法 称 S1 + OP + S2 为表达式的中缀表示法 称 S1 + S2 + OP 为表达式的后缀表示法 结论: 操作数之间的相对次序不变; 运算符的相对次序不同; 中缀式丢失了括弧信息，致使运算的次序不确定; 前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式; 后缀式的运算规

15、则为: 运算符在式中出现的顺序恰为表达式的运算顺序; 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式; 如何从后缀式求值？先找运算符，后找操作数，如何从原表达式求得后缀式？ 分析 “原表达式” 和 “后缀式”中的运算符:每个运算符的运算次序要由它之后的一个运算符来定，若当前运算符的优先数小，则暂不进行; 否则立即进行。 从原表达式求得后缀式的规律为：设立操作数栈; 设表达式的结束符为“#”,予设运算符栈的栈底为“#”， 若当前字符是操作数，则直接发送给后缀式; 若当前运算符的优先数高于栈顶运算符，则进栈; 否则，退出栈顶运算符发送给后缀式; “(”对它之前后的运算符起隔离作用，

16、“)”可视为自相应左括弧开始的表达式的结束符。 算法描述如下：void transform(char suffix, char exp ) / 从合法的表达式字符串exp求得其相应的后缀式InitStack(S); Push(S, # );p = exp; ch = *p;while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); / 直接发送给后缀式else switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c

17、); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / defult / switch / elseif ( ch!= # ) p+; ch = *p; / while / CrtExptree表达式求值的规则:设立运算符栈和操作数栈; 设表达式的结束符为“#”,予设运算符栈的栈底为“#”，若当前字符是操作数，则进操作数栈; 若当前运算符的优先数高于栈顶运算符，则进栈; 否则，退出栈顶运算

18、符作相应运算; “(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。 算法描述如下:OperandType EvaluateExpression() / 算术表达式求值的算符优先算法。设OPTR和OPND/ 分别为运算符栈和运算数栈，OP为运算符集合。InitStack (OPTR); Push (OPTR, #);initStack (OPND); c = getchar();while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是运算符则进栈else s

19、witch (precede(GetTop(OPTR), c) case # / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch / whilereturn GetTop(OPND); / EvaluateExpression/ 逆波兰表达式#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include common1.h#include typedef char ElemT

20、ypeC;typedef double ElemTypeN;typedef struct ElemTypeC *base; ElemTypeC *top; int stacksize;OpcStack;typedef struct ElemTypeN *base; ElemTypeN *top; int stacksize;OpnStack;Status Init_OpcStack(OpcStack &S) S.base=(ElemTypeC *) malloc(STACK_INIT_SIZE*sizeof(ElemTypeC); if(!S.base) exit(OVERFLO); S.to

21、p=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status GetTop_OpcStack(OpcStack S,ElemTypeC &e) if(S.top=S.base) return ERROR; e=*(S.top-1); return OK;Status Push_OpcStack(OpcStack &S,ElemTypeC e) if(S.top-S.base=S.stacksize) S.base=(ElemTypeC *) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(E

22、lemTypeC); if(!S.base) exit(OVERFLO); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push_SqStackStatus Pop_OpcStack(OpcStack &S,ElemTypeC &e) if(S.top=S.base) return ERROR; e=*(-S.top); return OK;/Pop_SqStackint Empt_OpcStack(OpcStack S) if(S.top=S.base) return TRUE; e

23、lse return FALSE;Status Init_OpnStack(OpnStack &S) S.base=(ElemTypeN *) malloc(STACK_INIT_SIZE*sizeof(ElemTypeN); if(!S.base) exit(OVERFLO); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status GetTop_OpnStack(OpnStack S,ElemTypeN &e) if(S.top=S.base) return ERROR; e=*(S.top-1); return OK;Sta

24、tus Push_OpnStack(OpnStack &S,ElemTypeN e) if(S.top-S.base=S.stacksize) S.base=(ElemTypeN *) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemTypeN); if(!S.base) exit(OVERFLO); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push_SqStackStatus Pop_OpnStack(OpnStack

25、 &S,ElemTypeN &e) if(S.top=S.base) return ERROR; e=*(-S.top); return OK;/Pop_SqStackint Empt_OpnStack(OpnStack S) if(S.top=S.base) return TRUE; else return FALSE;int Precede(char c,char ch) static char opc8=#,(,+,-,),*,/,; static int opn8=-1,0,1,1,2,2,2,3; int i,j,k; k=0; while(c!=opck) k+; i=k; k=0

26、; while(ch!=opck) k+; j=k; if(opni=opnj)return 1; elsereturn 0;void Transform(char suffix,char exp) OpcStack s; char *p,ch,c; int k; Init_OpcStack(s); Push_OpcStack(s,#); p=exp; ch=*p; k=0; while(!Empt_OpcStack(s) if(ch=0&ch=0&ch=9) Push_OpnStack(opn,ch-0);else Pop_OpnStack(opn,b); Pop_OpnStack(opn,

27、a); switch(ch) case +:a+=b;break; case -:a-=b;break; case *:a*=b;break; case /:a/=b;break; case :a=pow(a,b); Push_OpnStack(opn,a); ch=suffixi+; /while Pop_OpnStack(opn,a); return a;/evalutionint main() char exp20,suffix20; gets(exp); Transform(suffix,exp); puts(suffix); printf(%.2fn,Evalution(suffix

28、); return OK;例5、 迷宫求解 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。假设迷宫如下图所示: 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置可通，则纳入当前路径，并继续朝“

29、下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。 求迷宫中一条从入口到出口的路径的算法可简单描述如下： 设定当前位置的初值为入口位置；do 若当前位置可通

30、， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则结束； / 求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空）； 在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经

31、纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。/迷宫问题#define M 8#define N 6#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include common.h#define MAXSIZE 100int mazeM+2N+2;typedef struct int x; int y; item;item move4;typedef struct int x,y,d; SElemType;typedef struct SElemType *base; SElemType *top; int stacks

32、ize; SqStack;int path(SqStack &S) SElemType temp; int x,y,d,i,j; temp.x=1; temp.y=1; temp.d=-1; InitStack(S); Push (S,temp); while(!StackEmpty(S) Pop (S,temp); x=temp.x; y=temp.y; d=temp.d+1; while(d4) i=x+moved.x; j=y+moved.y; if(mazeij=0) temp.x=x; temp.y=y; temp.d=d; Push (S,temp); x=i; y=j; maze

33、xy=-1; if(x=M&y=N) return OK; else d=0; else d+; return 0;Status Crea_Maze() int i,j; for(i=0;iM+2;i+) mazei0=1; mazeiN+1=1; for(j=0;jN+2;j+) maze0j=1; mazeM+1j=1; / randomize(); for(i=1;iM+1;i+) for(j=1;jN+1;j+) mazeij=random(2); maze11=0; mazeMN=0; for(i=0;iM+2;i+) for(j=0;j0) Push(s,i);i-; t=1; w

34、hile(!StackEmpty(s) Pop(s,i);t=t*i; return t;三、背包问题（1） 递归实现#include common.h#define M 100int wwM;int knap(int t,int n) int k; if(t=0) k=TRUE; else if(t0&n1) k=FALSE;else if(knap(t-wwn,n-1)=TRUE) printf(%4d,wwn); k=TRUE; else k=knap(t,n-1); return k;void main() int i,j,n,t; printf(input n and tn); sc

35、anf(%d%d,&n,&t); printf(input weight f everythingn); for(i=1;i=n;i+)scanf(%d,&wwi); printf(nhave solution ? %sn,knap(t,n)?TRUE:FALSE);（2）背包问题的栈的实现非递归实现void Prin_KnapSack(SqStack s,int w) int i; while(!StackEmpty(s) Pop (s,i); printf(%4d,wi); printf(n);void KnapSack()/背包问题 SqStack s; int i,n,T,k=0,w6

36、; scanf(%d%d,&n,&T); for(i=0;i0&k=0) Push (s,k); T-=wk; k+; if(T=0) Prin_KnapSack(s,w); if(!StackEmpty(s) Pop (s,k); T+=wk; k+; while(!(StackEmpty (s)&k=n);例7：除了上面的例子以外，根据栈的后进先出的特点，栈还广泛的应用在树的遍历的非递归实现、AOV网的拓扑排序、AOE网的关键路径等，将在后面叙述。3.4 队列一、队列的定义和基本运算1 定义插入在队尾进行，允许删除的一端叫对头ADT Queue 数据对象：Dai | aiElemSet,

37、i=1,2,.,n, n0数据关系：R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头，an 端为队列尾。2基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q, &e)初始

38、条件：Q为非空队列。操作结果：用e返回Q的队头元素。EnQueue(&Q, e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q, &e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。 ADT Queue 二 队列类型的实现1链队列链式映象#include common.htypedef int QElemType;typedef struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr;typedef struct QNode *front,*rear; Link

39、Queue;（1）初始化Status InitQueue(LinkQueue &Q) /有头结点 QNode *p; p=(QNode *) malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-next=NULL; Q.front=Q.rear=p; return OK; （2）判空int QueueEmpty(LinkQueue Q) if(Q.front=Q.rear) return TRUE; else return FALSE; （3） 统计元素个数int QueueLength(LinkQueue Q) int i=0; QElemType e; While(!QueueEmpty(Q) i+; DeQueue(Q,e); return i; （4）入队Status EnQueue(LinkQueue &Q,QElemType e) QNode *p; p=(QNode *)malloc(sizeof(QNode); p-data=e;