设以不带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针。编写相应的入队和出队程序。
时间: 2024-04-30 15:04:05 浏览: 19
好的,我理解你的问题。以下是不带头结点的循环链表队列的入队和出队程序:
```c++
struct Node {
int val;
Node* next;
};
class Queue {
private:
Node* rear;
public:
Queue() { rear = nullptr; }
void enqueue(int val) {
Node* newNode = new Node { val, nullptr };
if (rear == nullptr) {
newNode->next = newNode;
rear = newNode;
} else {
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
}
int dequeue() {
if (rear == nullptr) throw "queue is empty";
int val;
if (rear == rear->next) { // only one element
val = rear->val;
delete rear;
rear = nullptr;
} else {
Node* front = rear->next;
val = front->val;
rear->next = front->next;
delete front;
}
return val;
}
};
```
入队和出队的时间复杂度都是 $O(1)$,因为只是简单地修改了指针。注意,这里的队列是循环队列,因此插入新元素时,要注意队列为空的情况。若队列为空,则将新元素作为唯一的元素,并且将 rear 指针指向它。其它情况下,rear 一定不为空,直接插入新元素并更新 rear 指针即可。
在出队时,若队列为空,则抛出异常。否则,虽然只有一个指针,却也可以通过 rear->next 指针找到队首元素,然后将它从队列中删除即可。
希望我的回答能够满足你的需求。如果你有其它问题,可以继续问我。