用360云盘做网站,简洁个人博客网站模板,邯郸网站制作公司,谁分享一个免费网站2021本题重点#xff1a;
1. 选择合适的数据结构
2. 针对选择的数据结构判断“空”和“满”
这两点是不分先后次序的#xff0c;在思考时应该被综合起来。事实上#xff0c;无论我们选择链表还是数组#xff0c;最终都能实现题中描述的“循环队列”的功能#xff0c;只不过… 本题重点
1. 选择合适的数据结构
2. 针对选择的数据结构判断“空”和“满”
这两点是不分先后次序的在思考时应该被综合起来。事实上无论我们选择链表还是数组最终都能实现题中描述的“循环队列”的功能只不过选择不同结构时我们面临和需要解决的问题不同。 一、思路
1. 数组实现队列。定义变量 front 标识队头变量 rear 标识队尾。 数组设计循环队列的好处 1. 找队尾元素方便使用链表实现时需要找尾。 2. 循环实现方便通过控制下标即可完成循环。 2. 初始时front rear 0每次插入一个元素rear向后走一位。
3. 判断“空” 和 “满”。如果 front 和 rear 下标相同队列为空还是满 4. 理解rear 1% k 1 front 。 若队列已满则rear 的下一个位置为 front。 此外每一次插入数据 或者 删除数据 后都要进行取模操作 防止 front 和 rear 走出实际数组的范围造成数组越界。 二、功能模块实现
1. MyCircularQueue(k): 设置队列长度为 k
typedef struct {int* a; // 指向的空间用来存储元素int front;int rear;int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-front obj-rear 0;obj-k k;obj-a (int*)malloc(sizeof(int) * (k 1));// 多创建1个空位// 该位置不用来存储元素仅用于判断队列“空”和“满”return obj;
}
2. isEmpty(): 检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-rear obj-front)return true;elsereturn false;
}
3. isFull(): 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj-rear 1) % (obj-k 1) obj-front)return true;elsereturn false;
}
4. enQueue(value): 向循环队列插入一个元素。
如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj-a[obj-rear] value;obj-rear;obj-rear % obj-k 1;return true;}
}
5. deQueue(): 从循环队列中删除一个元素。
如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj-front;obj-front % obj-k 1;return true;}
} 6. Front: 从队首获取元素。
如果队列为空返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[obj-front];
}
7. Rear: 获取队尾元素。
如果队列为空返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[(obj-rear (obj-k 1) - 1) % (obj-k 1)];
}
8. QueueFree: 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
} 三、所有代码
typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-front obj-rear 0;obj-k k;obj-a (int*)malloc(sizeof(int) * (k 1));return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-rear obj-front)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj-rear 1) % (obj-k 1) obj-front)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj-a[obj-rear] value;obj-rear;obj-rear % obj-k 1;return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj-front;obj-front % obj-k 1;return true;}
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[obj-front];
} int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[(obj-rear (obj-k 1) - 1) % (obj-k 1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
