题目描述

设计实现双端队列。

实现 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 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-circular-deque
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

①类似于这种设计题，最初我的思路是全无的，看了闫老师的解答，发现与数据结构课中学习的“循环队列”非常接近。即，开一个数组用来模拟循环队列，设一个头指针hh和一个尾指针tt，头指针表示头部队列元素的位置，尾指针表示尾部队列最后一个元素的下一个位置。当hh == tt时，代表当前队列为空，而当tt == get(hh-1)时（hh的前一个位置即为tt，即最后一个元素的下一个位置又回到了队头，表示循环队列已满），表示队列为满。
②插入队首，先判断队列是否已满，若队列已满则直接返回false，否则hh = get(hh-1)（先找到前一个位置），然后用q[hh] = value即可。而插入队尾是先插入再移位，因尾指针表示最后一个元素的下一个位置。
③删除使用覆盖原则即可，但是删除前需要判断队列是否为空。
④get()函数的作用即将hh和tt都控制在0~k这个范围之内。

代码

class MyCircularDeque {
public:
    vector<int> q;			#Cpp用vector初始化数组
    int hh = 0,tt = 0;

    int get(int x){			#控制hh和tt在0~k之内。
        return (x + q.size()) % q.size();
    }

    MyCircularDeque(int k) {
        q.resize(k+1);		#构造函数将vector的容量resize为k+1，因为需要表示0~k种状态。
    }
    
    bool insertFront(int value) {
        if(isFull())    return false;
        hh = get(hh - 1);
        q[hh] = value;
        return true;
    }
    
    bool insertLast(int value) {
        if(isFull())    return false;
        q[tt] = value;
        tt = get(tt + 1);
        return true;
    }
    
    bool deleteFront() {
        if(isEmpty())   return false;
        hh = get(hh + 1);
        return true;
    }
    
    bool deleteLast() {
        if(isEmpty())   return false;
        tt = get(tt - 1);
        return true;
    }
    
    int getFront() {
        if(isEmpty())   return -1;
        return q[hh];
    }
    
    int getRear() {
        if(isEmpty())   return -1;
        return q[get(tt-1)];
    }
    
    bool isEmpty() {
        return tt == hh;
    }
    
    bool isFull() {
        return tt == get(hh-1);
    }
};

/**
 * 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();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70