解答：

⑴ 该队列应选择链式存储结构。由于入队时，允许增加队列占用空间，出队后，整个队列所占用的空间只增不减，链式存储方便开辟新的空间。出队元素所占用的空间可重复使用，所以构造成循环链表。只需要维护队头指针和队尾指针，同时每个结点维护属性 key记录该结点的关键字，就能保证入队操作和出队操作的时间复杂度始终保持为 O(1) 。

方法一： Q.front 指向结点存储队列中的关键字。

⑵ 设队列 Q 头指针为 Q.front ，队尾指针为 Q.rear 。

初始状态： Q.front 和 Q.rear 均指向一个空结点。如图(a)所示。

判断队空 IS-EMPTY 伪代码如下：

IS-EMPTY(Q)
    if Q.front == Q.rear
        return TRUE
    else return FALSE

判断队满 IS-FULL 伪代码如下：

IS-FULL(Q)
    if Q.front == Q.rear->next
        return TRUE
    else return FALSE

⑶ 第一个元素 1 入队后：如图(b)所示。

⑷ 入队操作和出队操作的基本过程：

入队操作 ENQUEUE 伪代码如下：

ENQUEUE(Q, x)
    Q.rear.key = x   // 加入x
    if IS-FULL(Q) == TRUE    // 如果队满，需要增加新空结点
        create a new node p
        Q.rear->next = p
        p->next = Q.front
    Q.rear = Q.rear->next

第二个元素 2 入队后：如图(c)所示。

出队操作 DEQUEUE 伪代码如下：

DEQUEUE(Q)
    if IS-EMPTY(Q) == TRUE
        error "queue is empty"    // 如果队空，报错
    else    
        p = Q.front
        Q.front = Q.front->next;
        return p.key;

队头元素 1 出队后：如图(d)所示。

方法二： Q.rear 指向结点存储队列中的关键字。

⑵ 设队列 Q 头指针为 Q.front ，队尾指针为 Q.rear 。

初始状态： Q.front 和 Q.rear 均指向一个空结点。如图(a)所示。

判断队空 IS-EMPTY 伪代码如下：

IS-EMPTY(Q)
    if Q.front == Q.rear
        return TRUE
    else return FALSE

判断队满 IS-FULL 伪代码如下：

IS-FULL(Q)
    if Q.front == Q.rear->next
        return TRUE
    else return FALSE

⑶ 第一个元素 1 入队后：如图(b)所示。

⑷ 入队操作和出队操作的基本过程：

入队操作 ENQUEUE 伪代码如下：

ENQUEUE(Q, x)
    if IS-FULL(Q) == TRUE    // 如果队满，需要增加新空结点
        create a new node p
        Q.rear->next = p
        p->next = Q.front
    Q.rear = Q.rear->next
    Q.rear.key = x   // 加入x

第二个元素 2 入队后：如图(c)所示。

出队操作 DEQUEUE 伪代码如下：

DEQUEUE(Q)
    if IS-EMPTY(Q) == TRUE
        error "queue is empty"    // 如果队空，报错
    else    
        Q.front = Q.front->next;
        return Q.front.key;

队头元素 1 出队后：如图(d)所示。