以不带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针。编写相应的入队和出队程序。
时间: 2024-04-30 15:02:39 浏览: 107
循环链表表示队列时,我们可以使用一个指针 `rear` 来指向队尾结点。队列为空时,`rear` 指向 `NULL`。
入队操作时,我们新建一个结点 `new_node`,将数据存入结点中,然后将 `new_node` 插入到队尾。具体步骤如下:
1. 如果队列为空,将 `rear` 指向新结点,然后将结点的 `next` 指针指向自身,表示该结点是队列中唯一的结点;
2. 如果队列不为空,将新结点的 `next` 指针指向 `rear->next`,然后将 `rear->next` 指向新结点,最后更新 `rear` 指针,将其指向新结点。
出队操作时,我们需要删除队头结点。具体步骤如下:
1. 如果队列为空,返回空值;
2. 如果队列只有一个结点,删除该结点,并将 `rear` 指向 `NULL`;
3. 如果队列有多个结点,删除队头结点,并将 `rear->next` 指向新的队头结点。
以下是具体的代码实现:
```c++
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
};
Node* rear = NULL; // 队尾指针,初始值为 NULL
void enqueue(int x) {
Node* new_node = new Node;
new_node->val = x;
if (rear == NULL) { // 队列为空
rear = new_node;
new_node->next = new_node; // 指向自身
} else {
new_node->next = rear->next;
rear->next = new_node;
rear = new_node;
}
}
int dequeue() {
if (rear == NULL) { // 队列为空
return -1;
}
int val = rear->next->val;
if (rear->next == rear) { // 队列只有一个结点
delete rear;
rear = NULL;
} else {
Node* temp = rear->next;
rear->next = temp->next;
delete temp;
}
return val;
}
int main() {
enqueue(1);
enqueue(2);
enqueue(3);
cout << dequeue() << endl; // 1
cout << dequeue() << endl; // 2
enqueue(4);
enqueue(5);
cout << dequeue() << endl; // 3
cout << dequeue() << endl; // 4
cout << dequeue() << endl; // 5
cout << dequeue() << endl; // -1,队列为空
return 0;
}
```
阅读全文