题4

题4

题目

【2019 统考真题】请设计一个队列，要求满足:
① 初始时队列为空；
② 入队时，允许增加队列占用空间；
③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
④ 入队操作和出队操作的时间复杂度始终保持为 。
请回答下列问题：
⑴ 该队列是应选择链式存储结构，还是应选择顺序存储结构？
⑵ 画出队列的初始状态，并给出判断队空和队满的条件。
⑶ 画出第一个元素入队后的队列状态。
⑷ 给出入队操作和出队操作的基本过程。

分析

为了让出入队实现O(1)，因为只需要操作队列的头和尾，如果要是顺序的数组存储，我们对于第三个条件出队元素的空间可以重复使用显然是不可能的，因为本质上数组是静态的指针，我们只是把指针往后移动了一个单位，虽然队列的相对位置一直没有变，但是这个队列在存储空间中的绝对位置还是在变化的,以前用过的空间不能被重复利用，如果用链表的话，我们对空间的管理可以更灵活。

解

1. 顺序存储无法满足要求②的队列占用空间随着入队操作而增加。
   根据要求来分析:
   要求 ①容易满足;
   链式存储方便开辟新空间, 要求②容易满足;
   对于要求③, 出队后的结点并不真正释放, 用队头指针指向新的队头结点, 新元素入队时, 有空余结点则无须开辟新空间, 赋值到队尾后的第一个空结点即可, 然后用队尾指针指向新的队尾结点, 这就需要设计成一个首尾相接的循环单链表, 类似于循环队列的思想。
   设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为 ,要求④可以满足。

因此, 采用链式存储结构 (两段式单向循环链表), 队头指针为 front, 队尾指针为 rear。

2. 该循环链式队列的实现可以参考循环队列, 不同之处在于循环链式队列可以方便地增加空间, 出队的结点可以循环利用, 入队时空间不够也可以动态增加。同样, 循环链式队列也要区分队满和队空的情况, 这里参考循环队列牺牲一个单元来判断。初始时, 创建只有一个空闲结点的循环单链表, 头指针 front 和尾指针 rear 均指向空闲结点, 如下图所示。

队空的判定条件: front == rear。

队满的判定条件: front == rear→next。

3. 插入第一个元素后的状态如下图所示。

4. 操作的基本过程如下:

入队操作：

if (front == rear->next) { // 队满
    // 在 rear 后面插入一个新的空闲结点
    // 入队元素保存到rear所指结点中
    rear = rear->next;
    return;
}

出队操作：

if (front == rear) { // 队空
    // 出队失败，返回
    return;
}
// 取 front 所指结点中的元素e
e = front->data;
front = front->next;
return e;