赞
踩
队列都有两个指针,分别指向队头和队尾,用于出队入队
这里使用顺序表来实现队列,设置头元素下标为front,指向队头,尾元素下标为rear,指向队尾的下一个节点。之所以不选择链表,是因为链表不便于查找队尾元素。要用链表实现也可以,但要么需要记录rear的前一个节点,要么就让rear指向队尾,在入队时插入rear->next
想要实现环形队列的难点在于如何实现循环和如何判空和判满
1.实现循环
顺序表采用对rear和front取模的方式,每次出队入队都分别front++和rear++,当front和rear超过队列最大容量capacity时,让他们%capacity,这样就实现了循环
2.判空判满
如果一个可放入n个数据的环形队列的capacity为n的话,一开始front == rear == 0,假设不入队一直出队,当队满时rear又循环到了0下标,此时front == rear == 0仍成立。
这里有两种方法实现判空判满,第一种是设置size位,当size==0为空,size==capacity为满,但是每次更改front和rear时都需要更改size,虽然逻辑简单但是操作繁琐;第二种是多开辟一个位置,当front == rear为空,当(rear+1)%(capacity+1)== front则为满
为什么是(rear+1)%(capacity+1)== front?
首先,rear需要通过+1来判断是否等于front
其次,假设capacity为4,那实际数组空间为5,下标为0,1,2,3,4,当rear==4,此时下标0,1,2,3中都有数据,rear的理论最大值为rear+1 == 5,要使rear+1 == 5 == 0就需要使5%5,如此%的右边就为rear的理论最大值,front同理
- typedef struct {
- int* arr;
- //arr下标
- int front;
- int rear;
- //可存放元素个数
- int capacity;
-
-
- } MyCircularQueue;
-
-
-
- MyCircularQueue* myCircularQueueCreate(int k) {
- //动态开辟结构体
- MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
- //设置容量
- obj->capacity = k;
- //动态开辟结构体中的数组,多开一个空间用于判满
- obj->arr = (int*)malloc(sizeof(int)*(obj->capacity+1));
- obj->front = obj->rear = 0;
-
-
- return obj;
- }
-
-
- bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
- return obj->front == obj->rear;
-
-
- }
-
-
- bool myCircularQueueIsFull(MyCircularQueue* obj) {
- return (obj->rear+1)%(obj->capacity+1) == obj->front;
- }
-
-
- bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
- //当队列不满才插入
- if(!myCircularQueueIsFull(obj)){
- obj->arr[obj->rear] = value;
- obj->rear = (obj->rear+1)%(obj->capacity+1);
- return true;
- }else{
- return false;
- }
- }
-
-
- bool myCircularQueueDeQueue(MyCircularQueue* obj) {
- //当队列不为空才删除
- if(!myCircularQueueIsEmpty(obj)){
- obj->front = (obj->front+1)%(obj->capacity+1);
- return true;
- }else{
- return false;
- }
- }
-
-
- int myCircularQueueFront(MyCircularQueue* obj) {
- //当队列不为空获取,队为空返回-1
- if(!myCircularQueueIsEmpty(obj)){
- return obj->arr[obj->front];
- }else{
- return -1;
- }
- }
-
-
- int myCircularQueueRear(MyCircularQueue* obj) {
- //当队列不为空获取,队为空返回-1
- if(!myCircularQueueIsEmpty(obj)){
- return obj->arr[(obj->rear+obj->capacity)%(obj->capacity+1)];
- }else{
- return -1;
- }
- }
-
-
-
- void myCircularQueueFree(MyCircularQueue* obj) {
- free(obj->arr);
- free(obj);
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。