假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设置头指针),请编写相应的置空队列,判断队列是否为空,入队和出队算法。
时间: 2024-04-30 10:04:15 浏览: 17
以下是带头结点的循环链表表示队列的代码实现:
```c++
#include <iostream>
using namespace std;
// 队列结点
struct Node {
int data;
Node* next;
Node(int d): data(d), next(nullptr) {}
};
// 队列类
class Queue {
private:
Node* rear; // 队尾指针
public:
// 构造函数
Queue(): rear(nullptr) {
rear = new Node(0); // 头结点
rear->next = rear; // 队列为空时,队尾指针指向头结点
}
// 析构函数
~Queue() {
Node* p = rear->next;
while (p != rear) {
Node* q = p;
p = p->next;
delete q;
}
delete rear;
}
// 置空队列
void clear() {
Node* p = rear->next;
while (p != rear) {
Node* q = p;
p = p->next;
delete q;
}
rear->next = rear;
}
// 判断队列是否为空
bool empty() {
return rear->next == rear;
}
// 入队
void enqueue(int x) {
Node* p = new Node(x);
p->next = rear->next;
rear->next = p;
rear = p;
}
// 出队
int dequeue() {
if (empty()) {
cout << "Queue is empty." << endl;
return -1;
}
Node* p = rear->next->next;
int x = p->data;
rear->next->next = p->next;
if (rear == p) {
rear = rear->next; // 如果队列中只有一个结点,出队后需要修改队尾指针
}
delete p;
return x;
}
// 输出队列
void print() {
if (empty()) {
cout << "Queue is empty." << endl;
return;
}
Node* p = rear->next->next;
while (p != rear->next) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.print(); // 输出 1 2 3
q.dequeue();
q.print(); // 输出 2 3
q.clear();
q.print(); // 输出 Queue is empty.
return 0;
}
```
需要注意的是,由于使用了带头结点的循环链表实现队列,因此队列中至少有一个结点,即头结点。当队列为空时,队尾指针应指向头结点。