队列的线性表实现

问题：

请设计一个队列，要求满足：
1、初始时队列为空；
2、入队时，允许增加队列占用空间；
3、出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；
4、入队操作和出队操作的时间复杂度始终保持O（1）。
请回答下列问题：
1）该队列是应该选择链式存储结构，还是应选择顺序存储结构？
2）画出队列的初始状态，并给出判断队空和队满的条件
3）画出第一个元素入队后的队列状态。
4）给出入队操作和出队操作的基本过程。

解：

（1）链式存储
（2）

判空：

Q.front = Q.rear

判满：

 Q.front = Q.rear->next

(3) 略。
（4）

入队：

if(Q.front == Q.rear->next){
    s->data = x;

    s->next = Q.rear->next;
    Q.rear->next = s;
    Q.rear = s;
}

出队：

f(Q.front != Q.rear){
    e = Q.front->data;
    Q.front = Q.front->next;
}