本题重点:
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; else return false; }
3. isFull(): 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) { if((obj->rear + 1) % (obj->k + 1) == obj->front) return true; else return 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; else return obj->a[obj->front]; }
7. Rear: 获取队尾元素。
如果队列为空,返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return 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; else return false; } bool myCircularQueueIsFull(MyCircularQueue* obj) { if((obj->rear + 1) % (obj->k + 1) == obj->front) return true; else return 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; else return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[(obj->rear + (obj->k + 1) - 1) % (obj->k + 1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }