发布时间 : 星期日 文章数据结构练习 - 第三章 - 栈和队列更新完毕开始阅读54472da1561252d381eb6e7f
}∥算法结束
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
4．请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 【上海交通大学1999 二(12分)】 【厦门大学2005 六(15分)】
[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。S2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。
(1) int enqueue(stack s1,ElemType x)
∥s1是容量为n的栈，栈中元素类型是ElemType。本算法将x入栈，若入栈成功返回1，否则返回0
{if(top1==n && !Sempty(s2)) ∥top1是栈s1的栈顶指针，是全局变量 {printf(“栈满”);return(0);} ∥s1满s2非空,这时s1不能再入栈 if(top1==n && Sempty(s2)) ∥若s2为空，先将s1退栈,元素再压栈到s2
{while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);}
PUSH(s1,x); return(1); ∥x入栈，实现了队列元素的入队 }
void dequeue(stack s2,s1)
∥s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队 {if(!Sempty(s2)) ∥栈s2不空，则直接出队 {POP(s2,x); printf(“出队元素为”,x); } else ∥处理s2空栈
if(Sempty(s1)) {printf(“队列空”);exit(0);}∥若输入栈也为空，则判定队空
else ∥先将栈s1倒入s2中，再作出队操作 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);} POP(s2,x); ∥s2退栈相当队列出队 printf(“出队元素”，x); }
}∥结束算法dequue int queue_empty()
∥本算法判用栈s1和s2模拟的队列是否为空
{if(Sempty(s1) && Sempty(s2)) return(1);∥队列空 else return(0); ∥队列不空
17
}
[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。
5．编程：假设以数组Q[m]存放循环队列中的元素，同时以rear 和 length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue), 插入(enqueue)和删除(dlqueue)元素的操作。
【天津大学2002一.5(10分)】
6. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。【山东科技大学 2002 一.2 （6分）】
7. 双端队列（duque）是一个可以在任一端进行插入和删除的线性表。现采用一个一维数组作为双端队列的数据存储结构，使用类PASCAL语言描述如下： CONST maxsize=32; {数组中可容纳的元素个数} TYPE duque=RECORD
elem: ARRAY[0..MAXSIZE-1] OF datatype; {环形队列的存放数组} end1,end2:0..MAXSIZE; {环形数组的两端} END;
试编写两个算法add(Qu:duque;x:datatype;tag:0..1)和delete（Qu:duque; var x:datatype; tag:0..1）用以在此双端队列的任一端进行插入和删除。当tag=0时在左端endl端操作，当tag=1时在右端end2端操作。【清华大学 1998 二（10分）】
[题目分析] 双端队列示意图如下（设maxsize =12） 0 1 2 3 4 5 6 7 8 9 10 11 ↑ ↑
end1 end2
用上述一维数组作存储结构，把它看作首尾相接的循环队列。可以在任一端（end1或end2）进行插入或删除。初始状态end1+1=end2被认为是队空状态；end1=end2被认为是队满状态。（左端队列）end1指向队尾元素的前一位置。End2指向（右端队列）队尾元素的后一位置。入队时判队满，出队（删除）时判队空。删除一个元素时，首先查找该元素，然后，从队尾将该元素前的元素依次向后或向前（视end1端或end2端而异）移动。
FUNC add (Qu:deque; var x:datatype;tag 0..1):integer;
∥在双端队列Qu中插入元素x，若插入成功，返回插入元素在Qu中的下标；插入失败返回-1
∥tag=0表示在end1端插入；tag=1表示在end2端插入
IF Qu.end1=Qu.end2 THEN [writeln(“队满”);return(-1);] CASE tag OF
0: ∥在end1端插入
[Qu.end1:=x; ∥插入x
18
Qu.end1:=(Qu.end1-1) MOD maxsize; ∥修改end1
RETURN(Qu.end1+1) MOD maxsize); ∥返回插入元素的下标 1: ∥在end2端插入 [Qu.end2:=x;
Qu.end2:=(Qu.end2+1) MOD maxsize; RETURN(Qu.end2-1) MOD maxsize); ]
ENDC; ∥结束CASE语句 ENDF; ∥结束算法add
FUNC delete (Qu: deque; VAR x:datatype; tag:0..1):integer; ∥本算法在双端队列Qu中删除元素x，tag=0时从end1端删除，tag=1时从end2端删除
∥删除成功返回1，否则返回0
IF (Qu.end1+1) MOD maxsize=Qu.end2 THEN [writeln(“队空”);return(0);] CASE tag OF
0: ∥从end1端删除
[i:=(Qu.end1+1) MOD maxsize; ∥i是end1端最后插入的元素下标 WHILE(i<>Qu.end2) AND (Qu.elem[i]<>x) DO
i=(i+1) MOD maxsize;∥查找被删除元素x的位置 IF (Qu.elem[i]=x) AND (i<>Qu.end2) THEN [ j:=I;
WHILE((j-1+maxsize) MOD maxsize <>Qu.end1) DO
[Qu.elem[j]:=Qu.elem[(j-1+maxsize) MOD maxsize]; j:=(j-1+maxsize) MOD maxsize; ]∥移动元素，覆盖达到删除
Qu.end1:=(Qu.end1+1) MOD maxsize; ∥修改end1指针 RETURN(1); ]
ELSE RETURN(0);
]∥结束从end1端删除。 1: ∥从end2端删除
[i:=(Qu.end2-1+maxsize) MOD maxsize; ∥i是end2端最后插入的元素下标。 WHILE(i<>Qu.end1) AND (Qu.elem[i]<>x) DO
i=(i-1+maxsize) MOD maxsize;∥查找被删除元素x的下标 IF (Qu.elem[i]=x) AND (i<>Qu.end1) THEN ∥被删除元素找到 [ j:=I;
WHILE((j+1) MOD maxsize <>Qu.end2) DO
[Qu.elem[j]:=Qu.elem[(j+1) MOD maxsize]; j:=(j+1) MOD maxsize; ]∥移动元素，覆盖达到删除
Qu.end2:=(Qu.end2-1+maxsize) MOD maxsize; ∥修改end2指针 RETURN(1);∥返回删除成功的信息 ]
ELSE RETURN(0);∥删除失败
19
]∥结束在end2端删除 ENDC;∥结束CASE语句 ENDF;∥结束delete
[算法讨论]请注意下标运算。(i+1) MOD maxsize容易理解，考虑到i-1可能为负的情况，所以求下个i时用了(i-1+maxsize) MOD maxsize。
8. 已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：
makeEmpty(s:stack); 置空栈
push(s:stack;value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈，返回栈顶值 isEmpty(s:stack):Boolean; 判栈空否 队列的 ADT函数有：
enQueue(q:queue:value:datatype); 元素value进队 deQueue(q:queue):datatype; 出队列，返回队头值
isEmpty(q:queue):boolean; 判队列空否 【清华大学 2000 六（12分）】
[题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。 Void Invert(queue Q)
∥Q是一个非空队列，本算法利用空栈S和已给的几个栈和队列的ADT函数，将队列Q中的元素逆置
{makempty(S); ∥置空栈
while(!isEmpty(Q)) ∥ 队列Q中元素出队 {value=deQueue(Q); push(S,value); }∥ 将出队元素压入栈中 while(!isEmpty(S)) ∥栈中元素退栈
{value=pop(S); enQueue(Q,value); } ∥将出栈元素入队列 Q }∥算法invert 结束
9. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。 将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。
写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五（15分）】 [题目分析] 求两个正整数m和n的最大公因子，本题叙述的运算方法叫辗转相除法，也称欧几里德定理。其函数定义为： gcd(m,n)= int gcd (int m,n)
∥求正整数m和n的最大公因子的递归算法