题目链接：https://leetcode.cn/problems/design-circular-deque/

题目难度：中等

题意

设计实现双端队列。

实现 MyCircularDeque 类:

  • MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
  • boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
  • boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
  • boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
  • boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
  • int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
  • int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
  • boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
  • boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4

提示：

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次

题解：数组模拟

参考前段时间的每日一题：622. 设计循环队列

定义几个变量：n（表示最多能够容纳的元素个数），front（表示队头），rear（表示队尾）。同时定义一个数组用来模拟双端循环队列的情况。

  • 对于队头的移动，可以用$(front-1+n)\%n$表示
  • 对于队尾的移动，可以用$(rear+1)\%n$表示
  • 判断队列是否为空，只需要判断front和rear是否相等即可
  • 判断队列是否已满，只需要判断$(rear+1)\%n == front$即可

【感觉智商受到了碾压，居然debug了半小时，看官方题解，才发现自己的思路简直太拉胯了】

C++代码

class MyCircularDeque {
public:
    int queue_arr[1005];
    int n,front,rear;  //n表示最多能够容纳的元素数量
    MyCircularDeque(int k) {
        n=k+1;front=rear=0;
        for(int i=0;i<n;i++) queue_arr[i]=-1;
    }
  
    bool insertFront(int value) {
        if(isFull()) return false;
        front = (front-1+n)%n;
        queue_arr[front]=value;
        return true;
    }
  
    bool insertLast(int value) {
        if(isFull()) return false;
        queue_arr[rear]=value;
        rear = (rear+1)%n;
        return true;
    }
  
    bool deleteFront() {
        if(isEmpty()) return false;
        front = (front+1)%n;
        return true;
    }
  
    bool deleteLast() {
        if(isEmpty()) return false;
        rear = (rear-1+n)%n;
        return true;
    }
  
    int getFront() {
        if(isEmpty()) return -1;
        return queue_arr[front];
    }
  
    int getRear() {
        if(isEmpty()) return -1;
        return queue_arr[(rear-1+n)%n];
    }
  
    bool isEmpty() {
        if(front == rear) return true;
        return false;
    }
  
    bool isFull() {
        if((rear+1)%n == front) return true;
        return false;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */