数据结构第三章栈.ppt

第三章 栈和队列 一、什么是栈 栈：限定仅在一端进行插入或删除操作的线性表 二、栈的特点 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。 称往栈顶插入元素的操作为“入栈” 称删除栈顶元素的操作为“出栈”。 例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现 StackEmpty S //操作结果：若栈S为空栈，则返回TRUE，否则FALSE。 StackLength S //操作结果：返回S的元素个数，即栈的长度。 GetTop S, e //操作结果：用e返回S的栈顶元素。 Push S, e //操作结果：插入元素e为新的栈顶元素。 Pop S, e //操作结果：删除S的栈顶元素，并用e返回其值。 //ADT Stack 一、什么是顺序栈 栈的顺序存储结构简称为顺序栈。 二、顺序栈的基本操作 Status InitStack SqStack S Status GetTop SqStack S, SElemType e Status Pop SqStack S, SElemType e Status Push SqStack S, SElemType e Status InitStack SqStack S // 构造一个空栈 if ! S.base SElemType* malloc STACK_INIT_SIZE * sizeof SElemType exit OVERFLOW ; S.top S.base; S.stacksize STACK_INIT_SIZE; return OK; Status GetTop SqStack S, SElemType e Status Pop SqStack S, SElemType e Status Push SqStack S, SElemType e // 插入元素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.stacksize; S.stacksize+ STACKINCREMENT; //if *S.top++ e; return OK; //push 例一、 数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理： N N div d ×d + N mod d 其中：div 为整除运算，mod 为求余运算） 假设现要编制一个满足下列要求的程序： 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 一、什么是链栈 二、链栈的结构类型 typedef SElemType //由实际需要决定 typedef struct SNode SElemType data; struct SNode *next; SNode, *LStack; 二、链栈的基本操作 Status InitStack LStack S Status GetTop LStack S, SElemType e Status Push LStack S, SElemType e Status Pop LStack S, SElemType e Status InitStack LStack S // 构造一个空栈S S NULL; return OK; Status GetTop LStack S, SElemType e // 若栈不空，则用e返回S的栈顶元素，并返回OK,否则返回ERROR Status Push LStack S, SElemType e Status Pop LStack S, SElemType e // 若栈不空，则删除S的栈顶元素，用e返回其值， // 并返回OK；否则返回ERROR 例二、 括号匹配的检验 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［ ］［ ］）］等为正确的格式，［（ ］）或（［（ ））