5.2 队列
先入先出规则的线性数据结构
5.2.1 队列常用操作
push()
、pop()
、peek()
5.2.2 队列实现
1. 基于链表的实现
/* 基于链表实现的队列 */
typedef struct {
ListNode *front, *rear;
int queSize;
} LinkedListQueue;
/* 构造函数 */
LinkedListQueue *newLinkedListQueue() {
LinkedListQueue *queue = (LinkedListQueue *)malloc(sizeof(LinkedListQueue));
queue->front = NULL;
queue->rear = NULL;
queue->queSize = 0;
return queue;
}
/* 析构函数 */
void delLinkedListQueue(LinkedListQueue *queue) {
// 释放所有节点
while (queue->front != NULL) {
ListNode *tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
}
// 释放 queue 结构体
free(queue);
}
/* 获取队列的长度 */
int size(LinkedListQueue *queue) {
return queue->queSize;
}
/* 判断队列是否为空 */
bool empty(LinkedListQueue *queue) {
return (size(queue) == 0);
}
/* 入队 */
void push(LinkedListQueue *queue, int num) {
// 尾节点处添加 node
ListNode *node = newListNode(num);
// 如果队列为空,则令头、尾节点都指向该节点
if (queue->front == NULL) {
queue->front = node;
queue->rear = node;
}
// 如果队列不为空,则将该节点添加到尾节点后
else {
queue->rear->next = node;
queue->rear = node;
}
queue->queSize++;
}
/* 访问队首元素 */
int peek(LinkedListQueue *queue) {
assert(size(queue) && queue->front);
return queue->front->val;
}
/* 出队 */
int pop(LinkedListQueue *queue) {
int num = peek(queue);
ListNode *tmp = queue->front;
queue->front = queue->front->next;
free(tmp);
queue->queSize--;
return num;
}
/* 打印队列 */
void printLinkedListQueue(LinkedListQueue *queue) {
int *arr = malloc(sizeof(int) * queue->queSize);
// 拷贝链表中的数据到数组
int i;
ListNode *node;
for (i = 0, node = queue->front; i < queue->queSize; i++) {
arr[i] = node->val;
node = node->next;
}
printArray(arr, queue->queSize);
free(arr);
}
2. 基于数组的实现
使用一个变量 front
指向队首元素的索引,并维护一个变量 size
用于记录队列长度。定义 rear = front + size
,这个公式计算出的 rear
指向队尾元素之后的下一个位置。
基于此设计,数组中包含元素的有效区间为 [front, rear - 1]
,各种操作的实现方法如图 5-6 所示。
- 入队操作:将输入元素赋值给
rear
索引处,并将size
增加 1 。 - 出队操作:只需将
front
增加 1 ,并将size
减少 1 。
可以看到,入队和出队操作都只需进行一次操作,时间复杂度均为 \(𝑂(1)\)
环形数组
对于环形数组,需要让
front
或rear
在越过数组尾部时,直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现,代码如下所示:/* 基于环形数组实现的队列 */ typedef struct { int *nums; // 用于存储队列元素的数组 int front; // 队首指针,指向队首元素 int queSize; // 尾指针,指向队尾 + 1 int queCapacity; // 队列容量 } ArrayQueue; /* 构造函数 */ ArrayQueue *newArrayQueue(int capacity) { ArrayQueue *queue = (ArrayQueue *)malloc(sizeof(ArrayQueue)); // 初始化数组 queue->queCapacity = capacity; queue->nums = (int *)malloc(sizeof(int) * queue->queCapacity); queue->front = queue->queSize = 0; return queue; } /* 析构函数 */ void delArrayQueue(ArrayQueue *queue) { free(queue->nums); free(queue); } /* 获取队列的容量 */ int capacity(ArrayQueue *queue) { return queue->queCapacity; } /* 获取队列的长度 */ int size(ArrayQueue *queue) { return queue->queSize; } /* 判断队列是否为空 */ bool empty(ArrayQueue *queue) { return queue->queSize == 0; } /* 访问队首元素 */ int peek(ArrayQueue *queue) { assert(size(queue) != 0); return queue->nums[queue->front]; } /* 入队 */ void push(ArrayQueue *queue, int num) { if (size(queue) == capacity(queue)) { printf("队列已满\r\n"); return; } // 计算队尾指针,指向队尾索引 + 1 // 通过取余操作实现 rear 越过数组尾部后回到头部 int rear = (queue->front + queue->queSize) % queue->queCapacity; // 将 num 添加至队尾 queue->nums[rear] = num; queue->queSize++; } /* 出队 */ int pop(ArrayQueue *queue) { int num = peek(queue); // 队首指针向后移动一位,若越过尾部,则返回到数组头部 queue->front = (queue->front + 1) % queue->queCapacity; queue->queSize--; return num; }