循环队列的算法设计,给予源代码
时间: 2024-09-11 14:15:25 浏览: 47
Leetcode cookbook算法集+源代码.zip
循环队列是一种使用数组实现的先进先出(FIFO)的队列数据结构。它通过两个指针(通常称为头指针和尾指针)来指示队列中的元素位置,使得数组的末尾和开头相连,形成一个环形结构。当队列尾部的空间被使用完后,它可以“循环”回到数组的开始部分重新使用空间。
循环队列的算法设计通常包括以下几个关键部分:
1. 初始化:创建一个固定大小的数组,以及两个指针 front 和 rear 分别指向队列的头部和尾部。
2. 入队(Enqueue):在 rear 指向的位置添加新元素,并更新 rear 指针。
3. 出队(Dequeue):从 front 指向的位置移除元素,并更新 front 指针。
4. 判断队列是否为空和满的条件:
- 队列为空的条件:`front == rear`
- 队列为满的条件:`(rear + 1) % capacity == front`,其中 `capacity` 是队列的容量。
下面是一个简单的循环队列的 C 语言实现示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_MAX_SIZE 5
typedef struct {
int items[QUEUE_MAX_SIZE];
int front;
int rear;
} CircularQueue;
void initQueue(CircularQueue *q) {
q->front = 0;
q->rear = 0;
}
int isFull(CircularQueue *q) {
return (q->rear + 1) % QUEUE_MAX_SIZE == q->front;
}
int isEmpty(CircularQueue *q) {
return q->front == q->rear;
}
void enqueue(CircularQueue *q, int value) {
if (isFull(q)) {
printf("队列已满,无法添加新元素。\n");
return;
}
q->items[q->rear] = value;
q->rear = (q->rear + 1) % QUEUE_MAX_SIZE;
}
int dequeue(CircularQueue *q) {
if (isEmpty(q)) {
printf("队列为空,无法取出元素。\n");
return -1;
}
int value = q->items[q->front];
q->front = (q->front + 1) % QUEUE_MAX_SIZE;
return value;
}
int main() {
CircularQueue q;
initQueue(&q);
// 入队操作
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
// 出队操作
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
// 继续入队操作
enqueue(&q, 4);
enqueue(&q, 5);
enqueue(&q, 6); // 此时队列为满
return 0;
}
```
阅读全文