沈阳农业大学信息与电气工程学院数据结构课件 第三章.ppt

第三章 栈和队列 第三章 栈和队列 栈和队列是操作受限的线性表 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.1 栈 1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 栈的有关概念、特点及应用 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 例 洗一叠盘子、自动步枪的弹夹、铁路调度、Word取消与重复等。 栈的抽象数据类型的定义见P44 栈的示意图 2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top 顺序栈的类型定义如下 栈的溢出 设S是SqStack类型的指针变量。若栈底位置在向量的底端，即S.base是栈底元素，那么栈顶指针S.top是正向增加的，即进栈时需将S.top加1，退栈时需将s.top 减1。因此，S.top= S.base表示空栈， S.top-S.base =S.stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”。 栈的溢出 当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。 置空栈 判断栈空 Status stackempty(Sqstack S) { return(S.top== S.base); } 进栈 退栈 取栈顶元素 3 链栈 栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： typedef struct stacknode{ datatype data struct stacknode *next }stacknode; 链栈示意图 链栈操作(入栈) Void push(stacknode *p,datatype x) { stacknode *q q=(stacknode*)malloc(sizeof(stacknode)); q–data=x; q–next=p; p=q; } 链栈操作（出栈） Datatype pop(stacknode *p) { datatype x; stacknode *q=p; if(stackempty(p) error(“stack underflow.”); x=q–data; p= p–next; free(q); return x; } 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 数制转换举例 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 数制转换算法