### 队列的基本操作
一个基础的队列应至少支持以下两种核心操作:
1. **Enqueue** (入队) - 在队尾添加元素。
2. **Dequeue** (出队) - 从队首移除并返回元素。
为了实现这些功能,我们可以借助数组或链表这两种主要的数据存储方式来进行构造。
#### 数组实现队列
对于基于动态数组实现的循环队列,我们需要定义如下关键组件:
c
#include <stdio.h>
#define MAX_SIZE 50 // 假设我们设定的最大容量为50个元素
typedef int ElementType; // 定义队列中的元素类型
// 结构体声明用于表示队列
struct Queue {
ElementType data[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue *q);
int isEmpty(struct Queue q);
int isFull(struct Queue q);
ElementType dequeue(struct Queue *q);
void enqueue(struct Queue *q, ElementType item);
- `front` 表示对头的位置索引,
- `rear` 指向队尾位置或者下一个待插入新项的空间,
初始化函数 (`initQueue`) 设置 `front` 和 `rear` 的初始值;空闲检测函数(`isEmpty`)检查是否为空队列;满载判断函数(`isFull)`则确定当前队列是否已达到最大容纳量;而enqueue和dequeue分别处理元素加入与删除的操作,并确保当进行到"边界"(即绕回数组开头时),正确更新对应的指针。
这里省略了具体的函数实现在此以保持篇幅简洁,但它们的核心思想是通过移动前缀(front/rear指向的变化)而非实际内容迁移的方式管理内存空间。
#### 链表实现队列
另外一种常见的方法则是利用单链表作为底层容器实现队列。这种方式下不需要预先分配固定大小的内存,可以根据需要增长:
c
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
ElementType data;
struct Node* next;
}Node;
typedef struct {
Node* front;
Node* rear;
}LinkedQueue;
void createEmpty(LinkedQueue *);
bool isEmpty(LinkedQueue*);
void enQueue(LinkedQueue*, ElementType );
ElementType deQueue(LinkedQueue*);
在此模型里,每个节点包含两个部分: 数据域(data)及后继节点地址(next)。'front' 节点始终代表队列头部的第一个有效项目,而 'rear' 则总是最后一个项目的所在处以及新的元素要追加的地方。
enQueue 函数会创建一个新的结点并将其实例化后的next成员设置为NULL,然后将其连接至原队尾(rear)之后使新节点成为新的队尾;相反地,deQueue需找到并断开head所指向的那个节点再重新调整 head 并释放旧队首占用资源即可完成一次出队动作。
无论是采用哪种形式的内部储存机制构建队列,其设计都围绕着FIFO原理展开并通过精心编写的接口保证逻辑上的连贯性和一致性,使得开发者可以方便快捷地运用此类抽象于各种程序情境之中。最后,请务必注意适时管理和清理由上述算法产生的系统资源,尤其是在涉及动态内存申请的情况下更是如此。