pascal——栈和队列(tt)

《pascal——栈和队列(tt)》由会员分享，可在线阅读，更多相关《pascal——栈和队列(tt)（30页珍藏版）》请在金锄头文库上搜索。

1、TT概念：栈和队列是两种重要的线性结构。从数据结构角 度看，栈和队列也是线性表，其特殊性在于栈和队列 的基本操作是线性表操作的子集，它们是操作受限的 线性表，因此，可称为限定性的数据结构。但从数据 类型角度看，它们是和线性表大不相同的两类重要的 抽象数据类型。本章除了讨论栈和队列的定义、表示 方法和实现外，还将给出一些应用的例子。目录1 栈2 栈的应用举例3 队列一栈抽象数据类型栈的定义栈(Stack) 是限定仅在表尾进行插入或删除操作 的线性表。因此， 对栈来说，表尾端有其特殊含义 ，称为栈顶(top)，相应地，表头端称为栈底(bottom) 。不含元素的空表称为空栈。假设栈S=(a1，a2

2、，an)，则称a1为栈底元 素，an为栈顶元素。栈中元素按a1，a2，an的 次序进栈，退栈的第一个元素应为栈顶元素。换句 话说，栈的修改是按后进先出的原则进行的(如图 3.1(a)所示)。因此，栈又称为后进先出(Last lnFirstOut)的线性 表(简称LIFO结构)，它的这个特点可用图3.1(b)所示 的铁路调度站形象地表示。图3.1 栈(a)栈的示意图 (b) 用铁路调度站表示栈an出栈进栈出栈进栈 栈顶栈底. .a2 a1栈的基本操作栈的基本操作主要须掌握三点，两个 过程，一个函数。除此之外，还有判空， 初始栈，删除栈，不打算进行讲解，学习 时间长后自然明白。Push(S，x)初

3、始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。Pop(S)初始条件：栈s已存在且非空。操作结果：删除s的栈顶元素，并用e返回其值。GetTop(S)初始条件：栈s已存在且非空。操作结果：返回s的栈顶元素。注：在以后说明中，称插入元素（push）的操 作为入栈，删除栈顶（pop）元素的操作为 出栈。栈的表示和实现和线性表类似，栈也有两种存储表示方法。即顺 序栈和链栈。顺序栈（数组储存方式），即栈的顺序存储结构 是，利用一组地址连续的存储单元依次存放自栈底到 栈顶的数据元素，同时附设指针top指示栈顶元素在顺 序栈中的位置。代码：s为栈、p为指向栈顶的指针Const m=max;Type

4、 Stack=array1m of datatype;Var S:stack; p:integer;基本操作算法描述1.Procedure push(s:stack;x:datatype);BeginIf p=m then write(overflow) else begininc(p);sp:=x;end;End;2.procedure pop(s:stack);BeginIf p=0 then write(underflow) else dec(p);End;3.Function top(s:stack):datatype;BeginIf p=0 then write(none) else

5、 top:=sp;End;二 栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设 计中的有用工具。 1. 数制转换 N N div 8 N十进制数N和其他d进制数的转 1348 168 4换是计算机实现计算的基本问题，其 168 21 0解决方法很多，其中一个简单算法基 21 2 5于下列原理： 2 0 2N=(N div d)*d + N mod d （即Nd=ab，a =(N div d)*d ，b= N mod d ）其中：div为整除运算，mod为求余运算例如：(1348)10=(2504)8，其运算过程如右：Program ex1; type stack=array11

6、0000of integer; var s:stack;p:integer; a,d,r:integer; begin fillchar(s,sizeof(s),0); p:=0; readln(a,d);repeatinc(p);sp:=a mod d;a:=a div d;until a=0; while p0 dobeginwrite(sp);dec(p);end; writeln; end.附：在使用过程递归调用时，实质上就是在使用系统栈 。因此，大多数使用栈的题目可以用递归的方法来做。 以进制转化问题为例，可如此写代码： Program ex1_1; Var a,d:integer;

7、 Procedure change(x:integer); Beginif x=0 then exit;change(x div d);write(x mod d); End; Begin Readln(a,d); Change(a); Writeln; End.2 表达式求值算法 (一般指中缀表达式)(1)表达式的三种形式：中缀表达式：运算符放在两个运算对象中间，如： (2+1)*3；后缀表达式：运算符紧跟在两个操作数之后，实现 无括号和无优先处理，只须从左到右完成计算。如：表达式(2+1)*3表示为后缀表达式为2 1 + 3 *； 8-(3+2*6)/5+4 表示为8326*+5/4*前缀

8、表达式：同后缀表达式一样，不包含括号， 运算符放在两个运算对象的前面，如：* + 2 1 3。注：显然。由于后缀表达式中没有括号，不需判别优 先级，计算严格从左向右进行，故计算一个后缀表达 式要比计算机一个中缀表达式简单得多。 (2)计算后缀表示法的算法思路是：建立一个栈，放操作数从左到右读入表达式，若为数，则将 它转换为数值后入栈；若为运算符，则 从栈中弹出两个数到X、Y中，然后以“X 运算符Y”计算，并将结果入栈。若表达式未读完，就重复。最后栈顶的数值（栈中应只剩栈顶元 素）则为结果。 (3)将中缀表达式转化为后缀表达式的算法： 要将中缀表达式转化为等价的后缀表达式， 须从左至右扫描中缀表

9、达式，并用一个栈存放中 缀表达式的“（”和暂时不能参与计算的运算符。 1、当读到数字直接送至后缀表达式中2、当读到运算符t时，a.将栈中所有优先级高于或等于t的运算 符弹出，送到后缀表达式中； b.t进栈3、读到左括号时总是将它压入栈中4、读到右括号时，将靠近栈顶的第一个左括 号上面的运算符全部依次弹出，送至后缀表达式 后，再丢弃左括号。5、中缀表达式读完后，若栈中还有运算符， 则将栈中运算符全部依次弹出，送至后缀表达式 。练习:1、编号分别为1N的N辆列车进入 一个栈式结构的站台。试给出这N辆列 车开出车站的所有可能次序。如，编号 为14的四辆列车按照push、push、pop 、push、

10、push、pop、pop、pop操作，可 使得开出车站的冷为2431。2、若表达中操作数为非个位数值， 如何实现表达式计算 三 队列队列的定义和栈相反， 队列(Queue)是一种先进先出(First in First Out，缩写为FIFO)的线性表。它只允许在表的 一端进行插入，而在另一端删除元素。这和我们日常 生活中的排队是一致的，最早进入队列的元素最早离 开。在队列中，允许插入的一端叫做队尾(rear)，允许 删除的一端则称为队头(front)。 假设队列为q=(a1，a2，an)，那么，a1就是 队首元素，an则是队尾元素。队列中的元素是按照 a1，a2，an的顺序进入的，退出队列也只

11、能按照 这个次序依次退出，也就是说，只有在 a1，a2， ，an-1都离开队列之后an才能退出队列。队 队 头 尾 图3.8 队列的示意图 。出队列 a1 a2 a3 an 入队列队列在程序设计中也经常出现。一个 最典型的例子就是操作系统中的作业排队 。在允许多道程序运行的计算机系统中， 同时有几个作业运行。如果运行的结果都 需要通过通道输出，那就要按请求输出的 先后次序排队。每当通道传输完毕可以接 受新的输出任务时，队头的作业先从队列 中退出作输出操作。凡是申请输出的作业 都从队尾进入队列。基本操作：与栈相同，队列的基本操作也有很多，主要要求 掌握两个，一过程，一函数。add (Q，e)初始

12、条件：队列Q已存在 。操作结果：插入元素e为Q的新的队尾 元素。 Del(Q)初始条件：队列Q存在且非空。操作结果：返回并删除队首元素。队列的表示与实现 队列也有两种表示方式，即数组表示和链接表示。 同栈一样，队列是利用一组地址连续的存储单元依次存 放自队首到队尾的数据元素，同时设置队首队尾指 针head和tail。Const m=max; Type Queue=array1m of datatype; Var S:queue; h,t:integer;基本操作算法描述 Procedure add(q:queue;x:datatype);Beginqt:=x;if t=m then write

13、ln(overflow ) else inc(t);End;Function del(q:queue);BeginIf h=t then writeln(underflow ) elsebegindel:=qh;inc(h);end;End;3.4.3 循环队列队列的顺序表示和实现和顺序栈相类似，在队列Q的顺序存储结构中， 除了用一组地址连续的存储单元依次存放从队列头到 队列尾的元素之外，尚需附设两个指针front和rear分 别指示队列头元素和队列尾元素的位置。为了描述方 便起见，在此我们约定：初始化建空队列时，令 h=t=1，每当插入新的队列尾元素后，“尾指针增1”； 每当删除队列头元素后

14、，“头指针增1”。因此，在非 空队列中，头指针始终指向队列头元素，而尾指针始 终指向队列尾元素的下一个位置。如图3.12所示。 (a)空队列；(b)J1、J2和J3，相继入队列；(b)J1和J2相继被删除；(d)J4、J5和J6相继插入队列之后J3、 J4被删除。(a) (b) ( c ) (d) 图3.12 头、尾指针和队列中元素之间的关系Q.rear Q.front J1J2J3Q.rearQ.frontJ3Q.frontQ.rearJ5J6Q.frontQ.rear从上述分析可见，如果用户的应 用程序中设有循环队列，则必须为它设 定一个最大队列长度；若用户无法估计 所用队列的最大长度，则宜采用链队列 。 Procedure add(q:queue;x:datatype); Begin If h-t=1 then writeln(overflow ) elsebeginqt:=x;t:=t mod m+1;end; End; Function del(q:queue;):datatype; Begin If h=t then writeln(underflow) els