算法设计:在一个循环链队中只有尾指针(记为 rear,结点结构为数据源data,指针域为next,没有头 结点),请给出这个队列的入队、出队实现过程并测 试。
时间: 2024-05-14 20:14:04 浏览: 84
入队实现过程:
1. 创建一个新节点,并将要插入的数据放入新节点的数据源 data 中。
2. 如果 rear 指针为空,说明队列为空,将新节点赋值给 rear 指针,并将新节点的 next 指针指向自己,然后返回。
3. 如果 rear 指针不为空,则将新节点的 next 指针指向 rear 指针的下一个节点,将 rear 指针的 next 指针指向新节点,最后将新节点赋值给 rear 指针。
出队实现过程:
1. 如果 rear 指针为空,说明队列为空,直接返回。
2. 如果 rear 指针不为空,则将 rear 指针的下一个节点赋值给一个临时变量 temp。
3. 如果 temp 等于 rear 指针,说明队列只有一个节点,将 rear 指针置为空。
4. 如果 temp 不等于 rear 指针,则将 rear 指针的 next 指针指向 temp 的下一个节点。
5. 最后,将 temp 节点的数据源 data 返回。
测试代码如下:
```
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Queue {
public:
Queue() {
rear = NULL;
}
void enqueue(int data) {
Node* new_node = new Node;
new_node->data = data;
if (rear == NULL) {
rear = new_node;
rear->next = rear;
}
else {
new_node->next = rear->next;
rear->next = new_node;
rear = new_node;
}
}
int dequeue() {
if (rear == NULL) {
cout << "Queue is empty!" << endl;
return -1;
}
Node* temp = rear->next;
int data = temp->data;
if (temp == rear) {
rear = NULL;
}
else {
rear->next = temp->next;
}
delete temp;
return data;
}
private:
Node* rear;
};
int main() {
Queue q;
// 测试入队
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
// 测试出队
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
// 测试空队列
cout << q.dequeue() << endl;
return 0;
}
```
阅读全文