双向链表队列是一种结合了双向链表特性和队列特点的数据结构。在标准队列中，元素遵循先进先出（FIFO）原则，而双向链表允许在列表的前端或后端高效地插入和删除元素。将双向链表用于实现队列时，我们主要利用其双向遍历的能力，尽管在实际应用中，队列的典型操作（入队和出队）主要在一端进行，即在队列的尾部入队，在队列的头部出队。双向链表队列相比单向链表队列的优势在于，它提供了从队列两端快速访问的能力，这在某些算法或数据结构设计中非常有用。
1 双向链表队列的结构
一个双向链表的节点通常包含三个主要部分：
- `data`：存储数据的字段。
- `prev`：指向前一个节点的指针。
- `next`：指向下一个节点的指针。
2 实现双向链表队列的基本操作
2.1 初始化队列
创建一个空的双向链表队列，需要初始化头节点和尾节点，通常这两个节点是相同的，表示队列为空。
```c
struct Node {
int data;
Node* prev;
Node* next;
};
class Deque {
private:
Node* front;
Node* rear;
public:
Deque() {
front = rear = new Node{0, nullptr, nullptr};
}
// 其他方法...
};
```
2.2 入队操作（在队列尾部添加元素）
新元素总是被添加到队列的尾部。需要更新新节点的`prev`指针指向当前尾节点，并且更新当前尾节点的`next`指针指向新节点，最后更新尾节点为新节点。
```c
void enqueue(int value) {
Node* newNode = new Node{value, rear, nullptr};
rear->next = newNode;
rear = newNode;
}
```
2.3 出队操作（从队列头部移除元素）
队列头部的元素被移除。需要确保队列非空，然后更新`front`指针指向下一个节点，并释放被移除节点的内存。
```c
int dequeue() {
if (front == rear) return -1; // 或其他错误代码，表示队列为空
Node* temp = front->next;
int value = temp->data;
front->next = temp->next;
if (temp->next != nullptr) temp->next->prev = front;
delete temp;
if (front->next == nullptr) rear = front; // 队列变为空
return value;
}
```
2.4 查看队首元素
直接访问`front->next`的`data`字段即可，不需要修改链表结构。
```c
int peek() {
if (front == rear) return -1; // 或其他错误代码，表示队列为空
return front->next->data;
}
```
3 示例代码
下面是一个简化的C++示例，展示了双向链表队列的实现框架：
```c++
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
class Deque {
private:
Node* front;
Node* rear;
public:
Deque() {
front = rear = new Node{0, nullptr, nullptr};
}
void enqueue(int value) {
Node* newNode = new Node{value, rear, nullptr};
rear->next = newNode;
rear = newNode;
}
int dequeue() {
if (front == rear) return -1; // 队列为空
Node* temp = front->next;
int value = temp->data;
front->next = temp->next;
if (temp->next != nullptr) temp->next->prev = front;
delete temp;
if (front->next == nullptr) rear = front; // 队列变为空
return value;
}
int peek() {
if (front == rear) return -1; // 队列为空
return front->next->data;
}
};
int main() {
Deque queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << "Front element: " << queue.peek() << std::endl;
std::cout << "Dequeued: " << queue.dequeue() << std::endl;
std::cout << "New front element: " << queue.peek() << std::endl;
return 0;
}
```
这里演示了如何创建一个双向链表队列，进行入队、出队以及查看队首元素的操作。请注意，实际应用中还需考虑异常处理、内存管理优化等问题。
