队列结构体

### 队列结构体的定义与实现 #### 定义队列结构体 在C/C++中，可以通过数组或者链表来实现队列。以下是两种常见的队列结构体定义方式。 1. **基于数组的循环队列** 循环队列是一种优化后的数组实现方法，可以有效利用空间并减少内存浪费。其核心思想是当尾部到达数组末尾时，允许头部回到数组起始位置继续存储数据[^2]。 ```c++ typedef int CQDataType; typedef struct CircularQueue { CQDataType* a; // 动态分配的数组用于存储队列元素 int head; // 头指针，指向当前第一个元素的位置 int tail; // 尾指针，指向下一个待插入元素的位置 int size; // 当前队列的最大容量 } CQ; ``` 2. **基于链表的队列** 使用链表作为底层存储结构，能够动态扩展队列大小而无需预先设定固定长度。链表节点通常由数据部分和指针部分组成[^3]。 ```c++ typedef int QDataType; typedef struct QueueNode { QDataType data; // 存储实际数据 struct QueueNode* next; // 指向下一个节点的指针 } QNode; typedef struct LinkQueue { QNode* front; // 队首指针 QNode* rear; // 队尾指针 } LQueue; ``` --- #### 基于数组的队列基本操作 对于上述`CircularQueue`类型的队列，其实现如下： 1. 初始化队列： 创建一个新的队列对象，并初始化头尾指针以及最大容量。 ```c++ void InitQueue(CircularQueue& q, int capacity) { q.a = new CQDataType[capacity]; q.head = q.tail = 0; q.size = capacity; } ``` 2. 判断队列是否为空： 如果头指针等于尾指针，则说明队列为空。 ```c++ bool IsEmpty(const CircularQueue& q) { return q.head == q.tail; // 若相等则为空 [^2] } ``` 3. 插入元素到队列（入队）： 在尾部添加新元素之前需检查是否有足够的空间可用。 ```c++ bool Enqueue(CircularQueue& q, const CQDataType& value) { if ((q.tail + 1) % q.size == q.head) { // 检查队满条件 return false; } q.a[q.tail] = value; q.tail = (q.tail + 1) % q.size; // 更新tail索引 [^2] return true; } ``` 4. 删除元素从队列（出队）： 移除最前面的一个元素并将head向前移动一位。 ```c++ bool Dequeue(CircularQueue& q, CQDataType& result) { if (IsEmpty(q)) { return false; } result = q.a[q.head]; // 获取即将移除的值 q.head = (q.head + 1) % q.size; // 更新head索引 [^2] return true; } ``` --- #### 基于链表的队列基本操作 针对`LinkQueue`类型的操作函数设计如下所示： 1. 初始化链式队列： 设置前后两个指针均指向NULL表示初始状态下的空队列。 ```c++ void InitLQueue(LQueue& lq) { lq.front = lq.rear = NULL; } ``` 2. 入队操作： 新建一个节点将其链接至现有链条末端完成新增过程。 ```c++ bool Enlink(LQueue& lq, const QDataType& val) { QNode* newNode = new QNode{val, nullptr}; if (!newNode) { return false; // 内存不足返回失败标志位 } if (lq.rear == NULL) { // 特殊情况处理首次赋值场景 lq.front = lq.rear = newNode; } else { lq.rear->next = newNode; // 正常情况下更新rear所指地址即可 lq.rear = newNode; } return true; } ``` 3. 出队操作： 取得front处的内容之后释放该单元资源再调整剩余序列关系。 ```c++ bool Delink(LQueue& lq, QDataType& res) { if (lq.front == NULL) { return false; // 空队列无法执行删除动作 } QNode* temp = lq.front; res = temp->data; lq.front = lq.front->next; delete temp; // 清理已使用的堆区变量防止泄露现象发生 if (lq.front == NULL) { // 考虑极端情形即整个列表被清空的情况特殊对待一下 lq.rear = NULL; } return true; } ``` --- #### Java中的队列实现示例 除了C/C++外，在Java语言里也有标准库支持创建队列实例的方法之一便是借助`LinkedList`容器类模拟功能相似的行为模式[^5]: ```java import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args){ Queue<Integer> queue=new LinkedList<>(); // 添加元素 queue.offer(1); queue.add(2); System.out.println(queue); // 输出: [1, 2] Integer element=queue.poll(); // 返回并移除首个项目 System.out.println(element+" "+queue);// 输出: 1 [2] boolean isEmpty=queue.isEmpty(); System.out.println(isEmpty); // 输出: false while(!queue.isEmpty()){ System.out.print(queue.remove()+" "); // 连续打印直到耗尽全部成员为止... } } } ``` ---