队列练习之Example003-如果允许在循环队列的两端都可以进行插入和删除操作，分别写出从队尾删除和从队头插入的算法

如果允许在循环队列的两端都可以进行插入和删除操作，要求：

• 写出循环队列的类型定义。
• 分别写出从队尾删除和从队头插入的算法。

本题实际考查的是双端队列的代码实现。具体可参考：双端队列。

注意：

• 约定队头指针指向队头元素；队尾指针指向队尾元素的下一位置。
• 有些书中给出的代码实现，是约定的队头指针指向队头元素的前一位置，队尾指针指向队尾元素，具体根据实际情况来即可。

略。

核心代码：

typedef struct {
    
    int data[MAXSIZE];
    
    int front;
    
    int back;
} DoubleEndedQueue;


int pushFront(DoubleEndedQueue *deque, int ele) {
    // 0.参数校验，如果队满则不能入队
    if (isFull(*deque)) {
        return 0;
    }

    // 1.将元素插入到队列的头部
    // 1.1 由于队头指针指向队列的队头元素，所以先修改队头指针。新元素应该插入到原队头元素的前面，所以要队头指针减一，因为是循环队列，所以要对 MAXSIZE 取余
    deque->front = (deque->front - 1 + MAXSIZE) % MAXSIZE;
    // 1.2 再对队头指针所指向的位置进行赋值
    deque->data[deque->front] = ele;
    // 1.3 返回 1 表示入队成功
    return 1;
}


int popBack(DoubleEndedQueue *deque, int *ele) {
    // 0.参数校验，如果队空则不能出队
    if (isEmpty(*deque)) {
        return 0;
    }
    // 1.从队尾将元素出队
    // 1.1 由于队尾指针指向队尾元素的下一个位置，所以先修改队尾指针，将其减一，但由于是循环队列，所以要对 MAXSIZE 取余
    deque->back = (deque->back - 1 + MAXSIZE) % MAXSIZE;
    // 1.2 然后取出当前队尾指针所指向的元素，就是待出队的元素
    *ele = deque->data[deque->back];
    // 1.3 返回 1 表示出队成功
    return 1;
}

完整代码请参考：DoubleEndedQueue.c。

核心代码：

public class DoubleEndedQueue {

    
    private Queue deque;

    
    public void pushFront(int ele) throws Exception {
        // 0.参数校验，如果队满则不能入队
        if (isFull()) {
            throw new Exception("队满则不能入队！");
        }
        // 1.将元素插入到队列的头部
        // 1.1 由于队头指针指向队列的队头元素，所以先修改队头指针。新元素应该插入到原队头元素的前面，所以要队头指针减一，因为是循环队列，所以要对 MAXSIZE 取余
        deque.front = (deque.front - 1 + MAXSIZE) % MAXSIZE;
        // 1.2 再对队头指针所指向的位置进行赋值
        deque.data[deque.front] = ele;
    }

    
    public int popBack() throws Exception {
        // 0.参数校验，如果队空则不能出队
        if (isEmpty()) {
            throw new Exception("队空则不能出队！");
        }

        // 1.从队尾将元素出队
        // 1.1 由于队尾指针指向队尾元素的下一个位置，所以先修改队尾指针，将其减一，但由于是循环队列，所以要对 MAXSIZE 取余
        deque.back = (deque.back - 1 + MAXSIZE) % MAXSIZE;
        // 1.2 然后取出当前队尾指针所指向的元素，就是待出队的元素
        return deque.data[deque.back];
    }
}


class Queue {
    
    int[] data;
    
    int front;
    
    int back;
}

完整代码请参考：DoubleEndedQueue.java。

测试代码请参考：DoubleEndedQueueTest.java。