本文通过C++语言实现链式队列的初始化、销毁、入队、出队操作,并在main函数中进行实例演示,展示了如何存储和操作队列元素。
时间: 2024-10-24 20:06:44 浏览: 58
链式队列是一种利用指针链接节点的数据结构,它在C++中通常由头结点和一系列指向下一个元素的指针构成。以下是使用C++实现链式队列的基本步骤:
1. 初始化:创建一个`Node`类,包含数据成员如`data`和一个指向下一个节点的指针`next`。队列类`Queue`会有一个头指针`front`表示队列前端,以及一个尾指针`rear`表示队尾。
```cpp
class Node {
public:
int data;
Node* next;
};
class Queue {
private:
Node* front, *rear;
};
```
2. 入队(Enqueue):当添加新元素时,新建一个`Node`,将其设置为新的队尾,然后将`rear`指向下个节点。
```cpp
void enqueue(Queue& q, int value) {
Node* newNode = new Node{value, nullptr};
if (q.rear == nullptr)
q.front = q.rear = newNode;
else
q.rear->next = newNode;
q.rear = newNode;
}
```
3. 出队(Dequeue):移除并返回队首元素。如果队列为空,抛出异常;否则更新`front`指针并删除旧的队首节点。
```cpp
int dequeue(Queue& q) {
if (q.front == nullptr)
throw "Queue is empty";
int value = q.front->data;
Node* temp = q.front;
q.front = q.front->next;
delete temp;
return value;
}
```
4. 销毁:遍历队列,释放每个节点的内存。
```cpp
~Queue() {
Node* current = front;
while (current != nullptr) {
Node* temp = current;
current = current->next;
delete temp;
}
front = rear = nullptr;
}
```
5. 主函数示例:
```cpp
int main() {
Queue q;
// 使用enqueue进行元素添加,dequeue进行元素删除...
return 0;
}
阅读全文