2019 年 408 数据结构 · 第 42 题

请设计一个队列，要求满足：

① 初始时队列为空；

② 入队时，允许增加队列占用空间；

③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；

④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。

请回答下列问题：

(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？

(2) 画出队列的初始状态，并给出判断队空和队满的条件。

(3) 画出第一个元素入队后的队列状态。

(4) 给出入队操作和出队操作的基本过程。