数据结构课件.ppt

第4章 栈和队列 主要学习内容： 1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数。 2. 栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。 3. 算术表达式的中缀表示和后缀表示，以及相互转换的规则。 4. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名。 5. 队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。 4.1 栈 4.2 算术表达式的计算 4.3 栈与递归 4 .4 队列 4.1 栈 一、栈的定义 只允许在表的一端进行插入和删除的线性表。 栈又称为后进先出表 基本概念 栈顶、栈顶元素、栈底、进栈（入栈）、出栈（退栈） 二、栈的抽象数据类型 InitStack(S) 初始化栈 ClearStack(S) 清空栈 StackEmpty(S) 对栈判空 Peek(S) 返回栈顶元素，不移动栈顶指针 Push(S,item) 入栈 Pop(S,item) 出栈（删除栈顶元素并返回） StackFull(S) 对栈判满 三、栈的顺序存储结构 struct Stack{ ElemType stack[StackMaxSize]; int top; }; 顺序栈栈空条件：top==－1 顺序栈栈满条件：top==StackMaxSize －1 顺序栈栈顶元素：S.stack[S.top] 四、栈的链接存储结构 与线性表的链接存储结构相同 链栈栈空条件：HS==NULL 链栈栈顶元素：HS-data 五、顺序栈的操作实现 1、初始化栈InitStack：O(1) S.top=-1; 2、清空ClearStack ：O(1) S.top=-1; 3、判空StackEmpty ：O(1) return S.top==-1; 4、读取栈顶元素Peek ：O(1) return S.stack[S.top]; 五、顺序栈的操作实现 5、入栈 Push（注意操作顺序） ：O(1) S.top++; S.stack[S.top]=item; 6、出栈Pop （注意操作顺序） ：O(1) ElemType temp=S.stack[S.top]; S.top--; return temp; 7、判满StackFull ：O(1) return S.top==StackMaxSize-1; 六、链栈的操作实现 1、初始化栈InitStack ：O(1) HS=NULL; 2、清空ClearStack ：O(n) LNode * cp,* np; cp=HS; while(cp!=NULL){ np=cp-next; delete cp; cp=np;} HS=NULL; 六、链栈的操作实现 3、判空StackEmpty ：O(1) return HS==NULL; 4、读取栈顶元素Peek ：O(1) return HS-data; 5、入栈 Push ：O(1) LNode * newptr=new LNode; newptr-data=item; newptr-next=HS; HS=newptr; 六、链栈的操作实现 6、出栈Pop ：O(1) LNode * p=HS; HS=HS-next; ElemType temp=p-data; delete p; return temp; 4.2 算术表达式的计算 一、算术表达式的两种表示 1、中缀表示 1）定义：双目运算符出现在两个操作数中间 2）规则： 优先级：( )、*/、+- 同级从左向右 2、后缀表示 1)定义：运算符放在两个运算对象的后面 2）特点：不存在括号，不存在优先级 二、中缀表达式转换为后缀表达式： 把每个运算符都移到它的两个运算对象的后面，然后删掉所有的括号 例：P131例题 练习：P161填空题T15、T16 练习：2005年1月填空题 三、算法（略） 4.3 栈与递归 一、递归：在函数中直接或间接地调用该函数本身 二、执行递归函数是通过栈来实现的 4.4 队列 一、队列的定义 队列：仅允许在表的一端进行插入，在表的另一端进入删除的线性表 队列又称为先进先出表 基本概念： 队首、队尾、进队（入队）、离队（出队） 二、队列的抽象数据类型 InitQueue(Q) 初始化队列