假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队和出队的C++代码
时间: 2024-02-09 20:09:28 浏览: 59
好的,以下是带头结点的循环链表表示队列的 C++ 代码:
```cpp
#include <iostream>
using namespace std;
// 队列元素结构体
struct Node {
int data;
Node *next;
};
// 循环队列类
class Queue {
private:
Node *rear; // 队尾指针
public:
Queue() {
rear = new Node(); // 创建头结点
rear->next = rear; // 头结点指向自己
}
~Queue() {
while (!isEmpty()) {
dequeue();
}
delete rear; // 删除头结点
}
// 判断队列是否为空
bool isEmpty() {
return rear->next == rear;
}
// 入队
void enqueue(int data) {
Node *newNode = new Node();
newNode->data = data;
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
// 出队
int dequeue() {
if (isEmpty()) {
throw "Queue is empty";
}
Node *front = rear->next->next;
int data = front->data;
rear->next->next = front->next;
if (front == rear) {
rear = rear->next;
}
delete front;
return data;
}
};
int main() {
Queue queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
while (!queue.isEmpty()) {
cout << queue.dequeue() << " ";
}
cout << endl;
return 0;
}
```
在这个示例中,我们创建了一个循环链表,头结点的 `next` 指向队列的队尾元素,而队尾指针 `rear` 则指向头结点。入队操作时,我们创建一个新结点并将其插入到队尾元素后面,然后更新队尾指针 `rear`。出队操作时,我们删除队列的头结点后面的结点,并返回其值。需要注意的是,在删除队列的最后一个元素时,需要更新队尾指针 `rear`。
阅读全文