LeetCode | 622. 设计循环队列
思路：
- 我们这里有一个思路：
- 插入数据，bank往后走
- 删除数据，front往前走
- 再插入数据，就循环了
- 那上面这个方法可行吗？
怎么判断满，怎么判断空？
这样是不是比较难
- 我们下面有一个好的方法，就是
多开一个空间
下面是我们的结构体的定义
typedef struct { int* a; int front; int back; int k; } MyCircularQueue;
初始化
- 这里的初始化就是给a空间开了
k+1个大小
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = (int*)malloc(sizeof(int) * k + 1); obj->front = obj->back = 0; obj->k = k; return obj; }
判空
- 我们这里先来看判空
- 当我们的头尾相等了就说明是空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->back; }
判满
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back + 1) % (obj->k + 1) == obj->front; }
入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->back] = value; obj->back++; obj->back %= (obj->k+1); return true; }
出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front %= (obj->k+1); return true; }
取队头
- 这里很简单直接取对头，但是要判断是否为空，空了就不能取了~~
int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; }
取队尾
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; //可以这样写 //if(obj->back == 0) //return obj->a[obj->k]; //else //return obj->a[obj->back-1]; return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]; }
销毁队列
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
完整的代码实现
typedef struct { int* a; int front; int back; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = (int*)malloc(sizeof(int)*(k+1)); obj->front = obj->back = 0; obj->k = k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->back; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1)%(obj->k+1) == obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->back] = value; obj->back++; obj->back %= (obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; ++obj->front; obj->front %= (obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
