【LeetCode622】设计循环队列
一、题目
中等题。
提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。
二、思路
使用动态数组以便在运行阶段创建需要大小的数组
循环队列的实现关键在于isFull()和isEmpty()的实现（可以有不同的初始化和方法）。
初始化：front = rear = 0。
（1）队列为空：设当front = rear时队列为空。
普遍区分循环队空和队满的方法：牺牲一个单元来区分两者，即入队时少用一个队列单元，约定“队头指针在队尾指针的下一个位置作为队满的标志”（如下图），这样队满就不会也是front = rear了。
（2）队列为满：当(rear + 1) % capacity = front时队列为满。
（3）入队：入队时先后判断是否队满，判断条件为rear = (rear + 1) % capacity
（4）出队时判断空否，不空则front = (front + 1) % capacity
但是灰常不幸，leetcode上这题的测试用例不给牺牲一个单元哈哈，一怒之下使用vector（动态数组）来模拟循环队列hhh。
三、代码
class MyCircularQueue {
private:
int *data;
int front, rear;
int len;
int num = 0;
public:
vector<int> CircularQueue;
MyCircularQueue(int k) {
CircularQueue.clear();
len = k;
}
//插入元素,要判断是否队满
bool enQueue(int value) {
if(isFull()){
return false;
}else{
CircularQueue.push_back(value);
return true;
}
}
//删除元素
bool deQueue() {
if(isEmpty()){
return false;
}else{
CircularQueue.erase(CircularQueue.begin());
return true;
}
}
int Front() {
if(isEmpty()){
return -1;
}else{
return CircularQueue[0];
}
}
int Rear() {
if(isEmpty()){
return -1;
}else{
return CircularQueue[CircularQueue.size() - 1];
}
}
//判断是否队满
bool isFull() {
if(CircularQueue.size() == len){
return true;
}else{
return false;
}
}
bool isEmpty() {
if(CircularQueue.size() == 0){
return true;
}else{
return false;
}
}
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue* obj = new MyCircularQueue(k);
* bool param_1 = obj->enQueue(value);
* bool param_2 = obj->deQueue();
* int param_3 = obj->Front();
* int param_4 = obj->Rear();
* bool param_5 = obj->isEmpty();
* bool param_6 = 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
- 71
- 72
- 73
- 74
- 75
- 76
但是直接用vector有点偷懒的意思，还是直接用数组的方法试试：
接着刚才的思路牺牲一个位置，所以可以开k+1大小的数组，我们将下标为0的节点作为空节点（牺牲节点），初始化：front = rear = 0，其余步骤和一开始说的一毛一样：
（1）队列为空：设当front = rear时队列为空。
（2）队列为满：当(rear + 1) % capacity = front时队列为满。
（3）入队：入队时先后判断是否队满，判断条件为rear = (rear + 1) % capacity
（4）出队时判断空否，不空则front = (front + 1) % capacity
class MyCircularQueue {
public:
int *queue;
int front = 0, rear = 0;
int maxsize;
MyCircularQueue(int k) {
queue = new int[k + 1];
maxsize = k + 1;
}
bool enQueue(int value) {
if(isFull()){
return false;
}
rear = (rear + 1) % maxsize;
queue[rear] = value;
return true;
}
bool deQueue() {
if(isEmpty()){
return false;
}
front = (front + 1) % maxsize;
return true;
}
int Front() {
if(isEmpty()){
return -1;
}
return queue[(front + 1) % maxsize];
}
int Rear() {
if(isEmpty()){
return -1;
}
return queue[rear];
}
bool isEmpty() {
return front == rear; //都为0时
}
bool isFull() {
return ((rear + 1) % maxsize == front);
}
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue* obj = new MyCircularQueue(k);
* bool param_1 = obj->enQueue(value);
* bool param_2 = obj->deQueue();
* int param_3 = obj->Front();
* int param_4 = obj->Rear();
* bool param_5 = obj->isEmpty();
* bool param_6 = 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
文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。
原文链接：andyguo.blog.csdn.net/article/details/122592782
- 点赞
- 收藏
- 关注作者
评论（0）