设计循环队列
点击链接答题
思路:
循环队列,空间固定。
这里我们可以用数组来实现循环队列。
如何判断队列是否为满?
多申请一块空间
(rear+1)%(k+1) == front
如何判断队列是否为空?
rear == front
代码:
//定义循环队列的结构
typedef struct {int* arr;//定义数组int front;//定义头int rear;//定义尾int capacity;//定义一个变量保存数组空间大小
} MyCircularQueue;//循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {//定义一个指针,动态申请一块空间,指向循环队列MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//底层数组申请k+1个整型空间pst->arr = (int*)malloc(sizeof(int)*(k+1));pst->front = pst->rear = 0;pst->capacity = k;//把k保存起来return pst;//返回指向循环队列的指针
}//判断队列是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {//(rear+1)%(k+1) == front 就满了return (obj->rear+1)%(obj->capacity+1) == obj->front;
}//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了就不能插入数据if(myCircularQueueIsFull(obj)){return false;//说明插入失败}//队列没满,可以插入数据obj->arr[obj->rear++] = value;//插入一个数据rear++obj->rear %= obj->capacity + 1;//如果rear跑到队尾了,就通过取余回到队头return true;//说明插入成功
}//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空if(myCircularQueueIsEmpty(obj)){return false;//表示删除失败}//队列不为空obj->front++;obj->front %= obj->capacity + 1;//如果front跑到队尾了,就通过取余回到队头return true;//表示删除成功
}//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {//如果队列为空if(myCircularQueueIsEmpty(obj)){return -1;//如果队列为空,返回 -1 }//如果队列不为空return obj->arr[obj->front];
}//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//如果队列为空if(myCircularQueueIsEmpty(obj)){return -1;//如果队列为空,返回 -1 }//如果队列不为空int prev = obj->rear-1;//prev是rear前一个位置if(obj->rear == 0){prev = obj->capacity;//如果rear是处在arr[0],那么prev在arr[k]}return obj->arr[prev];
}//循环队列的销毁
//就是顺序表的销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);obj = NULL;
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/
循环队列的概念与结构
实际中还有一种特殊的队列叫循环队列,环形队列首尾相连成环,环形队列可以使用数组实现,也可以使用循环链表实现
思考:队列满的情况下,为什么 Q.rear 不存储数据?
为了能使用
Q.rear = Q.front
来区别是队空还是队满,我们常常认为出现左图时的情况即为队满的情况此时:
rear+1=front