3.15
TYPE
TwoWayStack=RECORD {双栈共享一向量空间}
elem:ARRAY[1..m]
OF elemtype;
top:ARRAY[0..1] OF
0..m+1; {两个栈顶指针}
END;
(1) PROC inistack(VAR
tws:TwoWayStack);
{初始化}
{初始化双向栈tws为空}
tws.top[0]:=0;
tws.top[1]:=m+1;
ENDP;
(2) PROC PUSH(VAR tws:TwoWayStack;i:0..1;
x:elemtype;VAR ofw:boolean);
{若双向栈tws不满,则将x插入到i端,成功时ofw为false,失败为true}
IF(tws.top[1]-tws.top[0])<>1
THEN
{栈未满}
CASE i OF
0:tws.top[0]:=tws.top[0]+1;tws.elem[tws.top[0]]:=x;ofw:=false
1:tws.top[1]:=tws.top[1]-1;tws.elem[tws.top[1]]:=x;ofw:=false
ENDC
ELSE ofw:=true;(
栈满}
(3) PROC POP(VAR
tws:TwoWayStack;i:0..1;VAR x:elemtype;VAR
underflow:boolean);
{若双向栈tws非空,则将i端退栈,栈空时underflow为true}
CASE i
OF
0:IF
tws.top[0]=0
{栈空}
THEN[underflow:=true;return(underflow)]
ELSE[ tws.top[0]:=tws.top[0]-1;
x:=tws.elem[tws.top[0]+1];
{弹出元素}
];
1:IF
tws.top[1]=m+1
{栈空}
THEN[underflow:=true;return(underflow)]
ELSE[ tws.top[1]:=tws.top[1]+1;
x:=tws.elem[tws.top[1]-1];
{弹出元素}
];
ENDC
3.17
FUNC
mathing:boolean;
{设读入的字符序列以@结尾,本算法判该字符串是否以&为中心对称}
[
INISTACK(s1);INISTACK(s2);
read(ch);
WHILE
ch<>'@' DO
{读入以@为结尾的字符序列}
[PUSH(s1,ch);
read(ch);
{@不是栈中字符序列的一部分}
]
x:=GETTOP(s1);
{取s1栈顶元素}{注意GETTOP与pop区别}
WHILE
x<>'&' DO
{将字符串'&'后的一串放入栈S2}
[
push(S2.X);
x:=POP(S1)
{'&'弹出栈S1,但不进入S2}
]
eq:=true;
{判s1,s2中对应字符相等否}
WHILE NOT EMPTY(s1) AND NOT EMPTY(s2) AND eq DO
[x1:=pop(s1);x2:=pop(s2);
IF x1<>x2 {有不配字符}
THEN eq:=false;
]
IF
EMPTY(s1) AND EMPTY(s2) AND eq
THEN matching:=true
{匹配}
ELSE matching:=false;
{不匹配}
]
ENDF;
3.20
PROC trnssufix(VAR exp2:string;s:stack;
exp1:string);
｛本算法将中缀表达式exp1转为后缀表达式exp2,使用运算符栈s}
｛算法基本思想是依次从中缀表达式读入字符w：｝
{若w是变量，直接送入结果表达式，｝
｛若w是运算符，则与栈顶运算符比较，若级别高，则进栈；｝
{若低，则栈顶元素退栈，并送入结果表达式，再取栈顶运算符比较，重复以上步骤；}
｛若w＝’)’,则栈元素依次退栈，并送入结果表达式，直至＇)＇退栈｝
initstring(exp2);
initstack(s);push(s,’#’);
op:=['+','-','*','/','(',')','#']; {操作符集合}
read(w);
WHILE NOT ((w='#') AND
(GETTOP(OPTR)='#')) DO
IF NOT (w IN op) THEN
［ insert(exp2,w);
read(w) ］;
ELSE
CASE precede(GETTOP(Ｓ),w)
OF
'<': [ PUSH(S,w); read(w) ];
'=': IF w=’)’ THEN {遇右括号后，运算符退栈并送结果表达式，
直至左括号}
[ x:=POP(S);
WHILE x<>’(‘ DO
[insert(exp2,x);x:=POP(S)]
read(w)
];
'>': [ b:=POP(S); insert(exp2,b)];
END;
ENDP;
3.29
TYPE
cyclicqueue=RECORD
{设头 尾指针和标志域的循环队列}
elem:=ARRAY[0..m-1]
OF elemtype;
rear,front:0..m-1
tag:0..1; ｛０为空，１为非空｝
END;
(1)
PROC INITQUEDE(VAR cq:cyclicqueue); ｛初始化｝
cq.tag:=0;cq.tear:=cq.front:=0;
ENDP;
(2)
PROC ENQUEUE(VAR cq:cyclicqueue; x:
elemtype);
｛cq是由头尾指针和标志域的循环队列，本算法是入队操作，若队列不满，｝
｛则将x插入到队尾｝
IF (cq.tag=1) AND
(cq.front=cq.rear)
THEN return(false)
{队满}
ELSE[cq.rear:=(cq.rear+1)
MOD m;
cq.elem(cq.rear):=r;
IF cq.tag=0 THEN
cq.tag:=1
{由空变不空标记}
]
ENDP;
(3)
PROC DELQUEUE(VAR
cq:cyclicqueue);
｛cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空｝
｛则将队头元素出队｝
IF
cq.tag=0
THEN return(false)
{队空}
ELSE[cq.front:=(cq.front+1) MOD
m;
IF
cq.front=cq.rear THEN cq.tag:=0 {队空}
]
ENDP;
{讨论:当m较小时,设标记可用足m个单元,但每次操作要判tag,多用了时间,}
{若m较大,不在乎一个单元，应使用牺牲一个单元办法,使操作加快(不再判断tag).}
3.30
CONST m=maxlen; ｛队列长度｝
TYPE
cyclicqueue=RECORD ｛只设尾指针和队列长度的循环队列｝
elem: ARRAY[0..m-1] OF elemtype;
rear: 0..m-1;
length: 0..m; ｛队列长度｝
END;
(1)
PROC INIT_queue(VAR q:cyclicqueue); ｛初始化｝
q.rear:=0;
q.length:=0;
ENDP;
(2)
FUNC add_queue(VAR
q:cyclicqueue;x:elemtype):boolean;
｛q是由尾指针和长度标志的循环队列，本算法是入队操作，若队列不满，｝
｛将x插入到队尾｝
IF
q.length=m
THEN add_queue:=false
{队列满}
ELSE [ q.rear:=(q.rear+1) mod
m;
q.elem[q.rear]:=x;
q.length;=q.length+1;
add_queue:=true
{入队成功}
]
ENDF;
(3)
FUNC dd_queue(VAR q:cyclicqueue;
x;elemtype):boolean;
｛q是由尾指针和长度标志的循环队列，本算法是出队操作，若队列不空，｝
｛将将队头元素出列，并赋给x，队长度减１｝
IF
q.length=0
THEN
dd_queue:=false
{队空}
ELSE [front;=(q.rear-q.length+1+m)
mod m
x:=q.elem[front]
q.length:=q.length-1
]
ENDF;