【leetcode】【2022/8/15】641. 设计循环双端队列

问题描述：

• 实现 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 622 设计循环队列是差不多的，只不过添加了头部的添加和删除操作（详细题解可以查看之前的题解，20220802 每日一题）。
  • 解题上也是一样，创建一个 k+1 大小的数组，用两个索引来表示头前和尾后位置，用变量 capacity 记录数组的大小，即 capacity = k+1。
  • 判空可以为判断尾后位置是否紧接着头前位置，判满可以为判断头前和尾后位置是否相等。【注意判空也可以为判断两个位置是否相等，主要是看两个索引的初始化是如何的】
  • 索引减一的操作为 (i-1+capacity)%capacity，索引加一的操作为 (i+1)%capacity。

代码实现：

class MyCircularDeque
{
private:
    vector<int> deq;
    int l;
    int r;
    int cap; // capacity
public:
    // k >= 1
    MyCircularDeque(int k) : deq(k+1), l(0), r(1), cap(k+1) {}
    
    bool insertFront(int value)
    {
        if(isFull()) return false;
        deq[l] = value;
        l = (l-1+cap)%cap;
        return true;
    }
    
    bool insertLast(int value)
    {
        if(isFull()) return false;
        deq[r] = value;
        r = (r+1)%cap;
        return true;
    }
    
    bool deleteFront()
    {
        if(isEmpty()) return false;
        l = (l+1)%cap;
        return true;
    }
    
    bool deleteLast()
    {
        if(isEmpty()) return false;
        r = (r-1+cap)%cap;
        return true;
    }
    
    int getFront()
    {
        if(isEmpty()) return -1;
        return deq[(l+1)%cap];
    }
    
    int getRear()
    {
        if(isEmpty()) return -1;
        return deq[(r-1+cap)%cap];
    }
    
    bool isEmpty()
    {
        return (r-l+cap)%cap == 1;
    }
    
    bool isFull()
    {
        return l == r;
    }
};
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