假设以带头结点的循环链表表示队列,且只设一个尾指针rear指向队尾结点。 编写函数,实现队列的基本操作,请给出完整代码
时间: 2024-04-30 17:03:01 浏览: 15
以下是带头结点的循环链表实现队列的基本操作的完整代码,包括入队、出队、判空、清空队列、获取队头元素和获取队列长度:
```c++
#include <iostream>
using namespace std;
// 队列节点的结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Queue {
private:
ListNode *rear; // 队列尾指针
public:
// 队列的构造函数,创建空队列
Queue() {
rear = new ListNode(-1); // 创建头节点
rear->next = rear; // 初始化rear指向头节点
}
// 队列的析构函数,释放所有节点的内存空间
~Queue() {
clear(); // 清空队列
delete rear; // 释放头节点的内存空间
}
// 判断队列是否为空,如果队列为空返回true,否则返回false
bool empty() {
return rear == rear->next; // 队列为空当且仅当rear->next指向头节点
}
// 清空队列,释放除头节点外的所有节点的内存空间
void clear() {
while (!empty()) {
pop(); // 依次弹出队列中的所有元素
}
}
// 入队,将元素x插入队列尾部
void push(int x) {
ListNode *node = new ListNode(x); // 创建新节点
node->next = rear->next; // 将新节点插入到队列尾部
rear->next = node; // 更新rear指针
rear = node; // 将rear指向新节点
}
// 出队,弹出队列头部的元素,并返回该元素的值
int pop() {
if (empty()) { // 如果队列为空,则无法弹出元素
throw "Queue is empty";
}
int x = rear->next->val; // 获取队列头部元素的值
ListNode *node = rear->next; // 获取队列头部元素对应的节点
rear->next = node->next; // 将node从队列中删除
if (rear == node) { // 如果队列只有一个元素
rear = rear->next; // 则将rear指向头节点
}
delete node; // 释放node的内存空间
return x; // 返回弹出的元素值
}
// 获取队头元素,但不弹出该元素
int front() {
if (empty()) { // 如果队列为空,则无法获取队头元素
throw "Queue is empty";
}
return rear->next->val; // 返回队头元素的值
}
// 获取队列长度,即元素个数
int size() {
int count = 0;
ListNode *p = rear->next;
while (p != rear) {
p = p->next;
count++;
}
return count;
}
};
int main() {
Queue q;
cout << "Push 1, 2, 3" << endl;
q.push(1);
q.push(2);
q.push(3);
cout << "Queue size: " << q.size() << endl;
cout << "Front element: " << q.front() << endl;
cout << "Pop element: " << q.pop() << endl;
cout << "Front element: " << q.front() << endl;
cout << "Pop element: " << q.pop() << endl;
cout << "Front element: " << q.front() << endl;
cout << "Pop element: " << q.pop() << endl;
cout << "Queue size: " << q.size() << endl;
return 0;
}
```
输出结果为:
```
Push 1, 2, 3
Queue size: 3
Front element: 1
Pop element: 1
Front element: 2
Pop element: 2
Front element: 3
Pop element: 3
Queue size: 0
```