小鲸鱼的梦境
0%

『LeetCode』622 设计循环队列

发表于 分类于 Valine：
本文字数： 5.7k 阅读时长 ≈ 5 分钟

题目

622. 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为"环形缓冲器&"。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

提示：

  • 所有的值都在 0 至 1000 的范围内；
  • 操作数将在 1 至 1000 的范围内；
  • 请不要使用内置的队列库。

标签

设计, 队列, 数组, 链表

相似题目

题解

【设计循环队列】基本数据结构

循环队列

队列是很基本的数据结构，循环队列是其常见的实现方式，需要小心的只有一点，如何判断队列空和队列满，常见的方法有两种：

  • 留一个空位，队头队尾指针重合为空，队头指针在队尾指针前面一个位置为满
  • 用一个变量记录队列中元素数量

实现上其实第二种方法稍微简单一丢丢，第一种方法代码格式更简洁统一一丢丢。

下面代码中, Python, Java, JS 用了第二种方法，C, C++ 用了第一种方法。

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
# Code language: Python
class MyCircularQueue:

    def __init__(self, k: int):
        self.st = [0] * k
        self.top, self.tail, self.size, self.length = -1, 0, 0, k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.top = (self.top + 1) % self.length
        self.st[self.top] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.tail = (self.tail + 1) % self.length
        self.size -= 1
        return True

    def Front(self) -> int:
        return self.st[self.tail] if not self.isEmpty() else -1

    def Rear(self) -> int:
        return self.st[self.top] if not self.isEmpty() else -1

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size >= self.length
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
// Code language: Java
class MyCircularQueue {
    int[] st;
    int top, tail, length, size;
    public MyCircularQueue(int k) {
        st = new int[k];
        top = -1; tail = 0; length = k; size = 0;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        top = (top + 1) % length;
        st[top] = value; ++size;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        tail = (tail + 1) % length;
        --size;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return st[tail];
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        return st[top];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size >= length;
    }
}
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
// Code language: C++
class MyCircularQueue {
public:
    vector<int> st;
    int length, top, tail;
    MyCircularQueue(int k): top(0), tail(0), length(k + 1) {
        st = vector<int>(k + 1, 0);
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        st[top] = value;
        top = (top + 1) % length;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        tail = (tail + 1) % length;
        return true;
    }
    
    int Front() {
        return isEmpty() ? -1 : st[tail];
    }
    
    int Rear() {
        return isEmpty() ? -1 : st[(top + length - 1) % length];
    }
    
    bool isEmpty() {
        return top == tail;
    }
    
    bool isFull() {
        return (top + 1) % length == tail;
    }
};
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
// Code language: C
typedef struct {
    int* st;
    int length, top, tail;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*) malloc(sizeof(MyCircularQueue));
    obj->st = (int*) malloc(sizeof(int) * (k + 1));
    obj->top = 0, obj->tail = 0;
    obj->length = k + 1;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;
    obj->st[obj->top] = value;
    obj->top = (obj->top + 1) % obj->length;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;
    obj->tail = (obj->tail + 1) % obj->length;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    return myCircularQueueIsEmpty(obj) ? -1 : obj->st[obj->tail];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    return myCircularQueueIsEmpty(obj) ? -1 : obj->st[(obj->top + obj->length - 1) % obj->length];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->top == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->top + 1) % obj->length == obj->tail;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->st);
    free(obj);
}
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
/* Code language: JavaScript */
/**
 * @param {number} k
 */
var MyCircularQueue = function(k) {
    this.length = k;this.size = 0;
    this.top = -1; this.tail = 0;
    this.st = new Array(k).fill(0);
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function(value) {
    if (this.isFull())
        return false;
    this.top = (this.top + 1) % this.length;
    this.st[this.top] = value;
    this.size++;
    return true;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function() {
    if (this.isEmpty()) return false;
    this.tail = (this.tail + 1) % this.length;
    this.size--;
    return true;
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function() {
    if (this.isEmpty()) return -1;
    return this.st[this.tail];
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function() {
    if (this.isEmpty()) return -1;
    return this.st[this.top];
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function() {
    return this.size == 0;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function() {
    return this.size >= this.length;
};
  • 时间复杂度: 所有操作均为 \(O(1)\)
  • 空间复杂度: \(O(k)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~