《栈和队列的详细讲解》由会员分享，可在线阅读，更多相关《栈和队列的详细讲解（113页珍藏版）》请在金锄头文库上搜索。
1、1,4.1 栈4.2 栈的实现4.3 栈的应用4.4 队列4.5 队列的实现 4.6 队列的应用,栈和队列是运算受限的线性表。,第四章 栈与队列,2,3.1 栈,3.1.1 栈的概念及运算3.1.2 顺序栈3.1.3 链栈,3,3.1.1 栈的概念及运算,栈,限制仅在一端进行插入和删除运算的线性表,栈顶,进行插入、删除的一端,栈底,栈顶,栈底,进栈,退栈,a2,a1,an,.,栈是后进先出表（ LIFO 表）,4,（1）置空栈 createEmptyStack(void)：空栈；（2）判栈空 isEmptytack（st）：这是一个布尔函数。 若st为空栈，则函数值为“真”, 否则为“假”。（
2、3）进栈 push（st，x）：在st的顶部插入(亦称压入） 元素 x。（4）退栈 pop（st）：删除（亦称弹出）栈st的顶部元素。（5）取栈顶 top（st）：取栈st的顶部元素。,栈的五种基本运算,3.1.1 栈的概念及运算,5,3.1.2 顺序栈,栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。,#define MAXNUM 100 /* 栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型* /struct SeqStack /* 顺序栈类型定义 */DataType sMAXNUM;int t; /*栈顶*/；typedef stru
3、ct SeqStack, *PSeqStack;PSeqStack pastack; /*指向顺序栈的指针变量*/,6,注意:,t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号),约定:,1、栈空时，t=-12、栈满时，t=MAXNUM-13、栈顶元素：St4、若t=-1时，执行pop,产生“下溢”5、若t=MAXNUM-1时，执行push,产生“上溢”,7,6 5 4 3 2 1 0-1,A,B,C,D,进栈和退栈,3.1.2 顺序栈,8,3.1.2 顺序栈,（1）置空栈 （2）判栈空 （3）进栈（4）退栈（5）取栈顶,在顺序栈下实现栈的五种基本运算,当程序中同时使用两个栈时，可共享
4、存储空间。,9,1. 置空栈（算法4.1）,PSeqStack createEmptyStack_seq(void) PSeqStack pastack; pastack=malloc(sizeof(struct SeqStack); if(pastack=NULL) printf(“out of space!n”); else pastack-t= -1; return pastack; /*SETNULL*/,10,2. 判栈空（算法4.2）,int isEmptyStack_seq(pastack)PSeqStack pastack; if (pastack-t=0) return FA
5、LSE; else return TRUE; ,11,3. 进栈（算法4.3）,先修改 t 值，再放入数据,t+,st=x,(*pastack).t+,(*pastack).s(*pastack).t=x,push_seq(pastack,x),12,push_seq(pastack,x)PSeqStack pastack; datatype x; if (pastack-t=MAXNUM-1) print(“overflow”);else pastack-t+; pastack-spastack-t=x; /* push_seq */,3. 进栈（算法4.3）,13,4. 退栈（算法4.4）
6、,pop_seq(pastack),修改 t 值,t-,pastack-t - -,14,pop_seq(pastack)PSeqStack pastack; if (pastack-t=-1 ) print(“underflow”); else pastack-t-; /* pop_seq */,4. 退栈（算法4.4）,15,5. 取栈顶元素（算法4.5）,datatype top_seq(pastack)PSeqStack pastack; if (pastack-t=-1 ) print(“stack is empty”); return NULL; else return(pasta
7、ck-spastack-t; /* top_seq */,16,多个栈共享存储空间, .,栈1,栈2,栈1底,栈1顶,栈2底,栈2顶,让多个栈共享存储空间，可以相互调节余缺， 节约存储空间，降低发生上溢的概率。,17,多个栈共享存储空间,多栈共享：采用链栈,Typedef struct datatype sMAXNUM; int top1,top2;DStack;Push(x,i) Pop(i),18,3.1.3 链栈,栈的链式存储结构称为链栈。它是运算受限的单链表。,由于只能在链表头部进行操作，故链栈没有必要象单链表那样需附加头结点。栈顶指针top就是链表的头指针head。,19,typed
8、ef int DataType;struct Node;typedef struct Node *pNode; struct Node /* 单链表结点结构 */ DataType info; pNode link;struct LinkStack/* 链接栈类型定义 */pNode top;/* 指向栈顶结点 */;typedef struct LinkStack *PLinkStack;,3.1.3 链栈,pLinkstack plstack; /*变量声明*/,plstack,top,info,link,栈的链接表示,21,3.1.3 链栈,相当于链表在 top 结点前插入,出栈,相当于
9、链表在将top 结点删除,进栈,22,void push_link( PLinkStack plstack, DataType x )/* 在栈中压入一元素x */PNode p; p = (PNode)malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!n); elsep-info = x;p-link = plstack-top;plstack-top = p;,进栈算法（算法4.8）,23,void pop_link( PLinkStack plstack ) PNode p; if( isEmptySt
10、ack_link( plstack ) )printf( Empty stack pop.n );elsep = plstack-top;plstack-top = plstack-top-link;free(p);,退栈算法（算法4.9）,24,3.2 栈的应用,栈的应用非常之广，只要问题满足LIFO 原则，均可使用栈做数据结构。我们先看几个例子。 例3.1 文字编辑器 例3.2 栈与递归 例3.3 数制转换 例3.4 括号匹配的检验 例3.5 表达式求值,25,例3.1 设计一个简单的文字编辑器，使其具有删除打 错字符的功能。,# 删除前面一个字符 删除前面所有字符* 输入结束,“abc#
11、defg*”,我们用栈来实现这种功能的文字编辑器,每读入一个字符,退栈,置空栈,编辑结束,26,PSeqStack str; /*顺序栈 str 是全程变量*/EDIT( ) /*编辑好的字符串在 str 中*/ char c; str=createEmptyStack(); c=getchar( ); while(c!=*) /*字符*为编辑结束符*/ if (c=#) POP(str); else if (c=) str=createEmptyStack(); else PUSH(str,c); c=getchar( )； /*EDIT*/,例3.1 设计一个简单的文字编辑器，使其具有删除
12、打 错字符的功能。,27,如果一个对象部分的由自己组成，或者是按它自己定义的，则称为递归的。 一个递归定义必须一步比一步简单，最后是有终结的，决不能无限循环下去。在n阶乘的定义中，当n为0时定义为1，它不再用递归来定义，称为递归定义的出口，简称为递归出口。,例3.2 栈与递归,递归的定义,28,例3.2 栈与递归,递归函数的特点：在函数内部可以直接或间接地调用函数自身。如阶乘函数：,阶乘的递归计算（算法4.11 ） int fact (int n) if (n = = 0) return 1;else return(n*fact(n-1); ; r2main( ) int n; scanf(“
13、%dn”,&n); printf(“%8d%8dn”,n,fact(n); r1,3,3,r1,2,r2,1,r2,0,r2,1,1,2,6,30,调用前：（1）为被调用函数的局部变量分配存储区； （活动记录， 数据区）（2）将所有的实参、返回地址传递给被调用函数； 实参和形参的结合，传值。（3）将控制转移到被调用函数入口。调用后返回：（1）保存被调用函数的计算结果；（2）释放被调用函数的存储区；（3）依照被调用函数保存的返回地址将控制转 移到调用函数。,递归函数到非递归函数的转换,函数嵌套调用时，按照“后调用先返回”的原则进行。,int main() int m,n; . first(m,n);1: ,int first(int s, int t) int i; second(i);2: ,int second(int d) intx,y;3: ,
