设结点结构为（data link) 试用一个全局指针p和某种链接结构实现一个队列 画出示意图 并给出入队a
结构,结点,示意图
已帮助 人
设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleteq过程，要求它们的时间复杂性都是O(1)(不计new和dispose时间)。【东南大学1996二(10分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：由于队列的先进先出性质所以链队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针P”且要求入队和出队操作的时间复杂度是O(1)因此我们用带头结点只设尾指针的循环链表来实现队列。入队核心语句段如下： s=new(Lnode)； ／／申请结点空间 s一>data=x； s一>next=p一>next；P一>next=s； ／／将S结点链入队尾 p=s； ／／P指向新队尾 出队的核心语句段如下： if(p->next==p) {cout$amp;由于队列的先进先出性质,所以链队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针P”,且要求入队和出队操作的时间复杂度是O(1),因此我们用带头结点只设尾指针的循环链表来实现队列。入队核心语句段如下：s=new(Lnode)；／／申请结点空间s一>data=x；s一>next=p一>next；P一>next=s；／／将S结点链入队尾p=s；／／P指向新队尾出队的核心语句段如下：if(p->next==p){cout$amp;;$lt;”队空”>;$lt;”队空”