采用一个不带头结点只有一个尾结点指针rear的循环单链表储存队列,设计队列的初始化、进队和出队算法
时间: 2024-10-21 16:18:25 浏览: 102
循环单链表作为队列的数据结构,其实现简单高效,尤其是当需要常数时间复杂度出队操作(从尾部删除元素)时。以下是这种队列的初始化、入队(enqueue)和出队(dequeue)的基本步骤:
1. **初始化**:
- 初始化时,将`rear`指针指向null,表示队列为空。
```c++
void initializeCircularQueue(CircularQueue &q) {
q.rear = nullptr;
}
```
2. **入队(Enqueue)**:
- 进行入队操作时,新节点应该始终添加到队列尾部。如果当前队列已满(即`rear`和`front`相隔`size`个节点),则需要进行循环处理。
```c++
void enqueue(CircularQueue &q, int value) {
if (q.isFull()) return; // 如果队列已满
Node* newNode = new Node(value);
// 如果队列空或者仅有一个元素(rear == front)
if (!q.rear || q.rear->next == q.front) {
q.rear = newNode; // 新节点成为头尾
} else {
newNode->next = q.front; // 将新节点链接到队首,形成循环
q.front->prev = newNode;
q.rear = newNode; // 更新 rear 指向新节点
}
}
```
3. **出队(Dequeue)**:
- 出队操作总是从队首开始,移除并返回队首元素。注意这里是`front`而非`rear`,因为队列头部是下一个出队元素的位置。
```c++
int dequeue(CircularQueue &q) {
if (q.isEmpty()) return -1; // 如果队列为空
int removedValue = q.front->value;
Node *temp = q.front; // 保存头节点
if (q.front == q.rear) { // 队列只剩一个元素
delete temp;
q.rear = nullptr;
} else {
temp->prev->next = q.rear; // 解开循环,更新前驱的 next 指针
q.front = temp->prev; // 更新 front 指向新的头节点
}
delete temp; // 删除旧的头节点
return removedValue;
}
```
阅读全文