数据结构考研分类复习真题 第三章 答案[26]

[题目分析] 本题与上面题基本相同现用类C语言给出该双端队列的定义

#define maxsize

typedef struct

{datatype elem[maxsize];

int endend; //end和end取值范围是maxsize

} deque;

[题目分析] 根据队列先进先出和栈后进先出的性质先将非空队列中的元素出队并压入初始为空的栈中这时栈顶元素是队列中最后出队的元素然后将栈中元素出栈依次插入到初始为空的队列中栈中第一个退栈的元素成为队列中第一个元素最后退栈的元素（出队时第一个元素）成了最后入队的元素从而实现了原队列的逆置

void Invert(queue Q)

//Q是一个非空队列本算法利用空栈S和已给的几个栈和队列的ADT函数将队列Q中的元素逆置

{makempty(S); //置空栈

while (!isEmpty(Q)) // 队列Q中元素出队

{value=deQueue(Q); push(Svalue); }// 将出队元素压入栈中

while(!isEmpty(S)) //栈中元素退栈

{value=pop(S); enQueue(Qvalue); }//将出栈元素入队列 Q

}//算法invert 结束

为运算方便设数组下标从开始即数组v[m]设每个循环队列长度（容量）为L则循环队列的个数为n=ém/Lù为了指示每个循环队列的队头和队尾设如下结构类型

typedef struct

{int fr;

}scq;

scq q[n];

（）初始化的核心语句

for(i=;i<=n;i++) q[i]f=q[i]r=(i)*L; //q[i]是全局变量

（）入队 int addq(int i;elemtp x)

//n个循环队列共享数组v[m]和保存各循环队列首尾指针的q[n]已经定义为全局变量数组元素为elemtp类型本过程将元素插入到第i个循环队列中若入队成功返回否则返回队满标记（入队失败）

{ if (i<||i>n) {printf(队列号错误);exit();}

if (q[i]r+)%L+(i)*L==q[i]f) {printf(队满\n);exit();}

q[i]r=(q[i]r+)%L+(i)*L; // 计算入队位置

v[q[i]r]=x; return();//元素x入队

}

（）出队 int deleteq (int i)// n个循环队列共享数组v[m]和保存各循环队列首尾指针的q[n]已经定义为全局变量数组元素为elemtp类型本过程将第i个循环队列出队若出队成功打印出队列元素并返回表示成功若该循环队列为空返回表示出队失败

{if (<||>n) {printf(队列号错误\n);exit();}

if (q[i]r==q[i]f) {printf(队空\n); return();}

q[i]f=(q[i]f+)%L+(i)*L;

printf(出队元素q[i]f); return();

}

（）讨论上述算法假定最后一个循环队列的长度也是L否则要对最后一个循环队列作特殊处理另外未讨论一个循环队列满而相邻循环队列不满时需修改个循环队列首尾指针的情况（即各循环队列长度不等）

n个循环队列共享数组v[m]的示意图如下

第i个循环队列从下标 (i)L 开始到iL为止设每个循环队列均用牺牲一个单元的办法来判断队满即为（q[i]r+）%L+(i)*L=q[i]f时判定为队满

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []