带链队列是什么,以C++语言写一段代码作为例子说明
时间: 2024-09-18 17:17:43 浏览: 44
带链表的队列,也称为双向链表队列,是一种数据结构,它使用节点包含元素值以及指向前一个和后一个节点的链接来存储数据。这种实现不同于数组队列,不需要预先确定队列的大小,可以动态添加或删除元素。
下面是一个简单的 C++ 示例,展示了如何使用链表实现一个队列:
```cpp
#include <iostream>
// 链表节点结构体
struct Node {
int data;
Node* next;
Node* prev; // 双向链表需要prev指针
};
// 队列类
class Queue {
private:
Node* front; // 队首指针
Node* rear; // 队尾指针
public:
Queue() : front(nullptr), rear(nullptr) {}
// 插入元素到队尾
void enqueue(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (rear == nullptr) { // 如果队列为空
newNode->prev = nullptr;
front = rear = newNode;
} else {
newNode->prev = rear;
rear->next = newNode;
rear = newNode;
}
}
// 删除并返回队首元素
int dequeue() {
if (front == nullptr) { // 如果队列为空
return -1; // 返回错误代码
}
int value = front->data;
Node* temp = front;
front = front->next;
if (front != nullptr) {
front->prev = nullptr;
} else {
rear = nullptr;
}
delete temp;
return value;
}
// 查看队列是否为空
bool isEmpty() const {
return front == nullptr;
}
};
int main() {
Queue queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << "Dequeue: " << queue.dequeue() << std::endl; // 输出1
std::cout << "Queue size: " << (queue.isEmpty() ? "0" : "not empty") << std::endl;
return 0;
}
```
阅读全文