链式队列设计,要求: (1)以带头结点的循环单链表实现,并只设尾指针,不设头指针。 (2)编写实现这种链式队列的初始化、入队列、出队列、取元素、判断非空函数。 (3)设计一个主函数进行测试。
时间: 2024-03-05 18:51:08 浏览: 77
好的,我来回答你的问题。
链式队列是一种基于链表实现的队列,它具有入队列和出队列的基本操作,并且可以动态地增加或删除元素,因此它比顺序队列更加灵活。
以下是链式队列的设计和实现:
```cpp
#include <iostream>
using namespace std;
// 定义队列的结点
struct Node {
int data;
Node* next;
};
// 定义链式队列
class LinkedQueue {
public:
LinkedQueue() {
rear = new Node;
rear->next = rear;
}
~LinkedQueue() {
while (!isEmpty()) {
dequeue();
}
delete rear;
}
// 入队列
void enqueue(int x) {
Node* p = new Node;
p->data = x;
p->next = rear->next;
rear->next = p;
rear = p;
}
// 出队列
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return;
}
Node* p = rear->next->next;
delete rear->next;
rear->next = p;
}
// 取队头元素
int getFront() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
return rear->next->data;
}
// 判断队列是否为空
bool isEmpty() {
return rear->next == rear;
}
private:
Node* rear;
};
// 主函数
int main() {
LinkedQueue queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
cout << queue.getFront() << endl;
queue.dequeue();
cout << queue.getFront() << endl;
queue.dequeue();
cout << queue.getFront() << endl;
queue.dequeue();
cout << queue.isEmpty() << endl;
return 0;
}
```
其中,链式队列的设计采用了带头结点的循环单链表实现,并只设尾指针,不设头指针。在入队列操作中,新建一个结点并将其插入到队列的尾部,然后更新尾指针。在出队列操作中,删除队列的头部结点即可。取队头元素的操作只需要返回头部结点的数据即可。判断队列是否为空只需要判断尾指针是否指向头结点即可。
以上是链式队列的设计和实现,希望对你有所帮助。
阅读全文