中。
类似本题叙述的其它题的解答：
（1） 该题同上面题本质相同，只有叙述不同，请参考上题答案。
8. 设结点结构为(data,link)，试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleteq过程,要求它们的时间复杂性都是O(l)（不计new和dispose时间）
【东南大学 1996 二 （10分）】
8、[题目分析]本题要求用链接结构实现一个队列，我们可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O（1），因此我们用只设尾指针的循环链表来实现队列。
（1） PROC addq(VAR p:linkedlist,x:elemtp);
//p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法是入队操作。
new(s); //申请新结点。假设有内存空间，否则系统给出出错信息。 s↑.data:=x; s↑.link:=p↑.link;//将s结点入队。
p↑.link:=s; p:=s; //尾指针p移至新的队尾。 ENDP;
（2） PROC deleq(VAR p:linkedlist,VAR x:elemtp);
// p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息。 IF （p↑.link=p）THEN[writeln(“空队列”);return(0);]//带头结点的循环队列。 ELSE[s:=p↑.link↑.link; //找到队头元素。 p↑.link↑.link:=s↑.link; //删队头元素。 x:=s↑.data; //返回出队元素。
IF (p=s) THEN p:=p↑.link; //队列中只有一个结点，出队后成为空队列。
dispose(s); //回收出队元素所占存储空间。 ]
ENDP;
[算法讨论]上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队列。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。
9. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图所示（编者略），请写出相应的入队列和出队列算法。【西安电子科技大学 1999计应用 六 （10分）】
9、本题与上题本质上相同，现用类C语言编写入队和出队算法。 （1）void EnQueue (LinkedList rear, ElemType x)
// rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。 { s= (LinkedList) malloc (sizeof(LNode)); //申请结点空间 s->data=x; s->next=rear->next; //将s结点链入队尾
rear->next=s; rear=s; //rear指向新队尾 }
（2）void DeQueue (LinkedList rear)
// rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队
头元素；否则给出出错信息。
{ if (rear->next==rear) { printf(“队空\\n”); exit(0);} s=rear->next->next; //s指向队头元素， rear->next->next=s->next; //队头元素出队。 printf (“出队元素是”，s->data);
if (s==rear) rear=rear->next; //空队列 free(s); }
10. 如果允许在循环队列的两端都可以进行插入和删除操作。要求： （1）写出循环队列的类型定义；
（2）写出“从队尾删除”和“从队头插入”的算法。【北方交通大学 1994 三 （12分）】 10、[题目分析] 用一维数组 v[0..M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。
（1）#define M 队列可能达到的最大长度
typedef struct
{ elemtp data[M]; int front,rear; } cycqueue;
（2）elemtp delqueue ( cycqueue Q)
//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，
否则给出出错信息。 { if (Q.front==Q.rear) {printf(“队列空”); exit(0);} Q.rear=(Q.rear-1+M)%M; //修改队尾指针。 return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。
}//从队尾删除算法结束
void enqueue (cycqueue Q, elemtp x)
// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if (Q.rear==(Q.front-1+M)%M) {printf(“队满”; exit(0);) Q.data[Q.front]=x; //x 入队列
Q.front=(Q.front-1+M)%M; //修改队头指针。 }// 结束从队头插入算法。
11. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。【山东科技大学 2002 一、2 （6分）】 11、参见9。
12. 双端队列（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分）】 12、[题目分析] 双端队列示意图如下（设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 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);//删除失败 ]//结束在end2端删除。 ENDC;//结束CASE语句 ENDF;//结束delete
[算法讨论]请注意下标运算。(i+1) MOD maxsize容易理解，考虑到i-1可能为负的情况，所以求下个i时用了(i-1+maxsize) MOD maxsize。
13. 一个双端队列deque是限定在两端end1，end2都可进行插入和删除的线性表。队空条件是end1=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端i（i=1，2）的插入enq和删除deq操作的实现。 （1） 当队满时，最多只能有一个元素空间可以是空的。 （2） 在做两端的插入和删除时，队列中其它元素一律不动。【清华大学 1999 六（12分）】 13、[题目分析] 本题与上面12题基本相同，现用类C语言给出该双端队列的定义。
#define maxsize 32 typedef struct
{datatype elem[maxsize];
int end1,end2; //end1和end2取值范围是0..maxsize-1 } deque;
14. 已知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分）】 14、[题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。 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 结束
15. 将n个队列顺序映射到数组v[l..m]中，每一队列在v中表示为一循环队列。试画出其示意图并写出对应这种表示的addq和deleteq过程。【东南大学 1993 二（20分）】
15、为运算方便，设数组下标从0开始，即数组v[0..m-1]。设每个循环队列长度（容量）为L，则循环队列的个数为n=?m/L?。为了指示每个循环队列的队头和队尾，设如下结构类型
typedef struct {int f,r; }scq; scq q[n];
（1）初始化的核心语句
for(i=1;i<=n;i++) q[i].f=q[i].r=(i-1)*L; //q[i]是全局变量 （2）入队 int addq(int i;elemtp x)
//n个循环队列共享数组v[0..m-1]和保存各循环队列首尾指针的q[n]已经定义为全局变量，数组元素为elemtp类型，本过程将元素插入到第i个循环队列中。若入队成功，返回1，否则返回队满标记0（入队失败）。
{ if (i<1||i>n) {printf(“队列号错误”);exit(0);}
if (q[i].r+1)%L+(i-1)*L==q[i].f) {printf(“队满\\n”);exit(0);} q[i].r=(q[i].r+1)%L+(i-1)*L; // 计算入队位置 v[q[i].r]=x; return(1);//元素x入队 }
（3）出队 int deleteq (int i)