pascal-栈和队列

1、栈及其应用一.栈的特点：栈是一种线性表，对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的顶”，另一端则叫做栈的底”,其操作特点是后进先出二.栈的抽象数据定义：1、栈的数组表小一顺序栈s 为栈、p 为指向栈顶的指针typestack=recorddata:array1.mofdatatype;p:0.mend;vars:stack;Constm=max;TypeStack=array1.mofdatatype;VarS:stack;p:0.m;2、栈的链接表示一链式栈bottom当栈的容量无法估计时，可采用链表结构链式栈.链式栈的栈顶在链头.无栈满问题，空间可扩充.进栈(插入)与出栈

2、(删除)都在栈顶处执行.三.栈的基本操作:(1)进栈操作 push(s,x):往栈中推入元素 x 的项目;若 p=m 贝 Uwrite(overflow)否贝 Up:=p+1;sp:=x;(2)出栈操作 pop(s):将栈顶元素中弹出；若 p=0 贝 Uwrite(underflow)否则 p:=p-1;(3)读栈顶元素 top(s,x):把栈顶元素的值读到变量 x 中，栈保持不变;若 p=0 则 write(error)否则 x:=sp;判栈是否为空 sempty(s):这是一个布尔函数，当栈 sp 中没有元素(即 t=0)时,称它为空栈，函数取真值，否则值为假。若 p=0 则 sempty

3、:=true否贝 Usempty:=false;(5)链式栈的进栈、出栈操作进栈：数据元素进栈时，先生成一个新结点 P,置数据域为 X、指针域指向原栈顶结点，typestack=struc;struc=recorddata:stype;link:stack;end;vars:stack;进栈退栈进栈退栈( (压压想一想一( (弹即弹即bottom一栈顶结点指向 P。(在链头插入一个新结点)出栈：先从栈顶取出数据元素至 X,然后把 S 结点指到它的直接后继结点，原 S 结点清空。(在链头删去一个结点)四.栈的应用1、表达式的计算(1)表达式的三种形式：中缀表达式：运算符放在两个运算对象中间，如：

4、(2+1)*3;后缀表达式(逆波兰表示法)：运算符紧跟在两个操作数之后，实现无括号和无优先处理，只须从左到右完成计算。如：表达式(2+1)*3 表示为后缀表达式为 21+3*;8-(3+2*6)/5+4 表示为 8326*+5/4+前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：*+213。(2)表达式的计算(设表达式中的运算对象为个位数)由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多。(3)计算后缀表示法的算法思路是：1、建立一个栈，放操作数2、从左到右读入表达式若为数，则将它转换为数值后入栈若

5、为运算符，则从栈中弹出两个数到 X、Y 中，然后以“X 运算符 Y”计算，并将结果入栈。3、若表达式未读完，就重复 24、最后栈顶的数值则为结果。(4)将中缀表达式转化为后缀表达式的算法要将中缀表达式转化为等价的后缀表达式， 须从左至右扫描中缀表达式， 并用一个栈存放中缀表达式的“(”和暂时不能参与计算的运算符。1、当读到数字直接送至后缀表达式中2、当读到运算符 t 时，a.将栈中所有优先级高于或等于 t 的运算符弹出，送到后缀表达式中；b.t 进栈3、读到左括号时总是将它压入栈中4、读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至后缀表达式后，再丢弃左括号。练习：1、编号

6、分别为 1N 的 N 辆列车进入一个栈式结构的站台。试给出这 N 辆列车开出车站的所有可能次序。如，编号为 14 的四辆列车按照 push、push、pop、push、push、pop、pop、pop操作，可使得开出车站的冷为 2431。程序2、若表达中操作数为非个位数值，如何实现表达式计算。队列1 .队列的特点：队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的头”(front),进行插入的一端叫队列的尾”(rear),其操作特点是先进先出。(FIFO,FirstInFirstOut)do(Ji(X2,dtj-lfront温2 .队列的抽

7、象数据定义：(1)队列的数组表示typequeue=recorddata:array1.mofdatatype;front,rear:1.mend;varq:queue;(2)队列的链接表示一链式队列FfflFfront-C|叵二r|”TG 闪队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front=nil链式队列编码举例typequeue=Astruct;struct=recorddata:datatype;link:queue;end;varfront,rear,q1,q2:queue;循环队列：存储队列的数组(或链表)被当作首尾相接的表处理3 .队列的基本

8、操作：(1)队列的插入 enq(q,x)：在队列 q 中插入一个值为 x 的元素，也称为进队；qrear:=x;若 rear=m 贝 Urear:=1否则 rear:=rear+1;若 rear=front 贝 Uwrite(overflow)(2)队列的删除 deq(q):从队列 q 中删除一个元素，也称为出队；若 rear=front 贝 Uwrite(underflow)否则若 front=m 贝 Ufront:=1 否贝 Ufront:=front+1;(3)读队头元素 front(q,x)：将队列 q 中头部元素的值读到 x 中；若 rear=front 贝 Uwrite(error

9、)否则 x:=qfront;(4)判队列是否为空 qempty(q):这是一个布尔函数，当 q 是空队列时，取真值，否则取假值。若 rear=front 贝 Uqempty:=true否则 qempty:=false;3.队列的应用：例、广义表(是线性表的一种推广；允许构成线性表的元素本身又可以是线性表，则该线性表为广义表。广义表是一个递归定义的表，允许其元素是本身的一个子表)只包括整数和字符型数据的广义表链表表示范“1 一回三卜回土到三五十国囚$二区-|-A表中套表情形下的广义表链表表示二 r 面W匚 3111-HN41.设有一个表，记为 L=(a1,a2,a3,.,an),其中L 表名a1

10、,a2,a3,.,an 表中元素。当 ai 为数值时表示元素，当 ai 为大写字母时，表示另一个表，但不能循环定义。例如，下列的定义是合法的(约定 L 是第一个表的表名)：L=(3.4,3,4,K,8,0,8)K=(15,5,8,P,9,4)P=(4,7,8,9)程序要求：当全部表给出后，示出所有元素的最大元素。思路：(1)可以建立两种队列，一种队列是存放数值的数值队列 Q1,并预定义 Q1AQ1Z条数值队列，另一种队列 Q2 存放字母，表示将要向该字母所对应的子表输入数值队列。(2)根据题目要求，事件队列 Q2 中应先放入字母 L,表示首先输入 L 数值队列的数据。(3)从事件队列 Q2 中

11、取出一个字母， 并将该字母对应的数值队列的数值输入， 如果输入的数据中包含字母，则把字母放入事件队列中，并记录输入的数值中的最大值。(4)重复(3)步骤，直到事件队列中为空。表达式处理程序programbds;constm=50;type定义栈stack=array1.mofchar;stack1=array1.mofreal;vars:stack;s1:stack1;e,a:string;i,l,p,y:integer;x:real;begin中缀表达式 e 转后缀表达式 a,s 为运算符栈，P 为指针read(e);读入一个中缀表达式p:=0;l:=length(e);fori:=1tol

12、dobegincaseeiof0.9:a:=a+ei;若为数字，进入后缀表达式(:beginp:=p+1;sp:=(;end;若为左括号，进栈):begin若为右括号，则左括号前的所有运算符出栈进入后缀表达式，)舍whilesp(dobegina:=a+sp;p:=p-1;end;p:=p-1;end;+,-:begin若为+-号，则左括号前的所有运算符出栈进入后缀表达式，+-号进栈while(sp()and(p0)dobegina:=a+sp;p:=p-1;end;p:=p+1;sp:=ei;end;*,7:begin若为*/号，则左括号前的栈顶的*/出栈进入后缀表达式，*/号进栈while

13、(p0)and(sp=*)or(sp=/)dobegina:=a+sp;p:=p-1;end;p:=p+1;sp:=ei;end;end;caseend;forwhilep0do所有运算符出栈进入后缀表达式begina:=a+sp;p:=p-1;end;writeln(a);计算后缀表达 a 的值，S1 为存放操作数的栈，P 为栈指针l:=length(a);p:=0;fori:=1toldobegincaseaiof0.9:begin是操作数，将操作数转为数值类型数据后进栈p:=p+1;val(ai,x,y);s1p:=x;end;+:begin栈顶的两个操作数出栈，进行加法运算，其结果进栈

14、x:=s1p;p:=p-1;s1p:=s1p+x;end;-:begin栈顶的两个操作数出栈，进行减法运算，其结果进栈x:=s1p;p:=p-1;s1p:=s1p-x;end;*:begin栈顶的两个操作数出栈，进行乘法运算，其结果进栈x:=s1p;p:=p-1;s1p:=s1p*x;end;/:begin栈顶的两个操作数出栈，进行除法运算，其结果进栈x:=s1p;p:=p-1;s1p:=s1p/x;end;end;caseend;forwriteln(s1p:5:2);栈底的结果为最终运算结果end.附：链式栈例子programxx;typestack=Astc;stc=recorddata

15、:integer;link:stack;end;constm=100;vari,x:integer;top:stack;procedurepush(vars:stack;x:integer);varp:stack;beginnew(p);pA.data:=x;pA.link:=s;s:=p;end;procedurepop(vars:stack);varp:stack;beginp：=s;ifsnilthenbeginx:=sA.data;s:=sA.link;dispose(p);endelsewriteln(underflow);end;beginnew(top);top:=nil;for

16、i:=1tomdobeginpush(top,i);end;whiletopnildobeginpop(top);write(x:5);end;end.【题目】【题目】火车调度问题【参考程序】programhcdd;constm=10;typestack=array1.mof0.m;varn,total:integer;ns,out:stack;sprocedureoutput(out:stack);varx:integer;beginforx:=1tondowrite(outx:3);writeln;total:=total+1;定义栈为列车数，total 为总方案数为进站列车栈， out

17、为出站列车序列输出过程end;procedurepush(d,i,p,e:integer;s,out:stack);d 为步数，i 为入口处有多少辆车，p 为进站指针，e 为出站序列指针，s 为站内车辆序列,out 为出站列车序列beginifi0thenbeginsp+1:=n+1-i;第 n+1-i 辆车进站ifd=2*nthenoutput(out)elsepush(d+1,i-1,p+1,e,s,out);end;ifp0thenbegin若站内还有车辆，则出站oute+1:=sp;ifd=2*nthenoutput(out)elsepush(d+1,i,p-1,e+1,s,out)end;end;beginreadln(n);total:=0;push(1,n,0,0,s,out);writeln(total:,total:10);end.【解法 2】用穷举二进制数串的方法完成.vari,n,m,t:integer;a,s,c:array1.1000ofinteger;proceduretest;vart1,t2,k:integer;notok: