栈的抽象数据类型定义 第三章栈和队列 ADT Stack[ 数据对象:D={ala1∈ Elemnet,i=1,2n,n>=1 数据关系:R=(<a1a1+1a1a1+1∈D,1=1,2…n 基本操作 nitstack(ss);初始化操作生成一个空栈s Destroystack(&s);释放栈 Clearstack(&s);清空栈 push(sS,x);入栈操作 Pop(ss,se);出栈操作 Getop(s,&e);取栈顶元素函数 Emptystack(ss);置栈空操作 int StackLength(s);求当前栈中元素个数一 第11页
第三章 栈和队列 第11页 ADT Stack{ 数据对象：D={ai|ai∈ElemSet，i=1,2,…,n, n>=1} 数据关系：R={<ai,ai+1>|ai,ai+1 ∈D, i=1,2,…,n} 基本操作： InitStack( &S )；初始化操作生成一个空栈S DestroyStack( &S ); 释放栈 ClearStack( &S ) ；清空栈 Push( &S, x )；入栈操作 Pop( &S, &e )；出栈操作 GetTop( S, &e ) ；取栈顶元素函数 EmptyStack( &S )；置栈空操作 int StackLength( S ); 求当前栈中元素个数 } ⚫ 栈的抽象数据类型定义
第三章栈和队列 的简单应用示例 例3-1输入字符串。用‘#表示退格符,即它使前一个字符无 效;用‘@’表示退行符,以表示此前整行字符均无效。编写行输 入处理过程,内设一个栈来逐行处理从终端输入的字符串。每次从 终端接收一个字符后先作如下判别:如果它既不是退格符也不是退 行符,则将该字符插入栈顶;如果是一个退格符,则从栈顶删去 个字符;如果它是一个退行符,就把字符域清为空栈 比如,若键入 BGE##EGIM#N RAD(AOREAD(A) 则实际有效的是下面两行 BEGIN 一READ(A 第12页
第三章 栈和队列 第12页 ⚫ 栈的简单应用示例 例3-1 输入字符串。用‘# ’表示退格符，即它使前一个字符无 效；用‘ @ ’表示退行符，以表示此前整行字符均无效。编写行输 入处理过程，内设一个栈来逐行处理从终端输入的字符串。每次从 终端接收一个字符后先作如下判别：如果它既不是退格符也不是退 行符，则将该字符插入栈顶；如果是一个退格符，则从栈顶删去一 个字符；如果它是一个退行符，就把字符域清为空栈。 比如，若键入 BGE##EGIM#N RAD(A@•READ(A); 则实际有效的是下面两行 BEGIN •READ(A);
第三章栈和队列 设s为栈。本算法从终端接收一个正文文件并逐行传送至调用过程的数据区 Line Edito[ Initstack(s) h getchar (; //从终端接收一个字符二 while ch ! EOF I while( ch != EoF &&ch !=I\n) switch(ch)[ case#〃:Pop(s,c); break;//若栈非空则退栈 case a′: Clearstack(s); break;//将栈重新设置为空域 default: Push(s, ch)i; //有效字符入栈 ch getchar o) }//继续接收 //将自栈底至栈顶的栈内字符作成一行,并传送至调用过程的数据区 Clearstack(s) if( ch != EOF)ch getchar //继续接收下一行,先接收下一行第一个字符 }算法3.1 第13页
第三章 栈和队列 第13页 //设s为栈。本算法从终端接收一个正文文件并逐行传送至调用过程的数据区 Line_Edit(){ InitStack( S ); ch = getchar()； //从终端接收一个字符 while( ch != EOF ) { while( ch != EOF && ch != ‘\n’ ) { switch(ch){ case ‘#’: Pop(s,c); break; //若栈非空则退栈 case ‘@’: ClearStack(s); break; //将栈重新设置为空域 default: Push(s,ch); break; //有效字符入栈 }； ch = getchar() } //继续接收下一字符 //将自栈底至栈顶的栈内字符作成一行,并传送至调用过程的数据区. ClearStack(s); if( ch != EOF ) ch = getchar() //继续接收下一行，先接收下一行第一个字符 } } 算 法 3.1
第三章栈和队列 栈的表示和实现 顺序栈—栈的顺序存储结构 用一维数组S(1: armax)表示栈 S(1: armax S(1: armax) armax armax op 栈顶 B A 栈底 Top=0 空栈 非空栈 第14页
第三章 栈和队列 第14页 顺序栈——栈的顺序存储结构 用一维数组S(1:arrmax)表示栈。 3 2 1 3 `C` 2 `B` 1 `A` S(1:arrmax) S(1:arrmax) arrmax arrmax Top=0 Top= 空 栈 非空栈 栈顶 栈底 ⚫ 栈的表示和实现
找的表示和实现 第三章栈和队列 栈的ADT表示 const int MAX STACK =1000 struct SastkTpi ElemType Element[MAX STACK]i int fopi } 工 ni tstack( SastkT&s) 刀设定一个空的栈S Status isstackEmpty( SgstkIp s )i ∥若S为空栈,则返回true,否则返回 false status Push( SastkTp &s, ElemTp x )i 若栈S不满,则在栈顶插入X,并返回函数值true,否则栈的状态 不变且返回函数值 false 第15页
第三章 栈和队列 第15页 const int MAX_STACK = 1000; struct SqStkTp{ ElemType Element[MAX_STACK]; int Top; }; InitStack( SqStkTp &S); //设定一个空的栈S Status isStackEmpty( SqStkTp S ); //若S为空栈，则返回true，否则返回false Status Push( SqStkTp &s, ElemTp x ); //若栈S不满，则在栈顶插入x，并返回函数值true，否则栈的状态 不变且返回函数值false 栈的ADT表示 ⚫ 栈的表示和实现