数据结构
2019-42
请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④入队操作和出队操作的时间复杂度始终保持为 O(1)。请回答下列问题：
(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？
(2) 画出队列的初始状态，并给出判断队空和队满的条件。
(3) 画出第一个元素入队后的队列状态。
(4) 给出入队操作和出队操作的基本过程。
答案
（1）选择链式存储结构，用单向循环链表保存队列，设置队头指针 front 和队尾指针 rear。
（2）初始时只建立一个空闲结点，front 和 rear 均指向该结点。
- 队空：
front == rear - 队满：
front == rear->next
（3）第一个元素入队后，将元素写入 rear 所指结点，再令 rear = rear->next。
（4）基本操作：
入队 EnQueue(e)：
if (front == rear->next) { // 队满
在 rear 后插入一个新的空闲结点;
}
rear->data = e;
rear = rear->next;
return;
出队 DeQueue(e)：
if (front == rear) { // 队空
return ERROR;
}
e = front->data;
front = front->next;
return OK;入队、出队的时间复杂度均为 O(1)。