链式队列设计,要求:(1)以带头结点的循环单链表实现,并只设尾指针,不设头指针。(2)编写实现这种链式队列的初始化、入队列、出队列、取元素、判断非空函数。(3)设计一个主函数进行测试。
时间: 2024-11-15 18:31:05 浏览: 24
链式队列设计通常利用循环单链表实现,因为循环结构可以避免在队列为空时处理特殊情况。在这种设计中,我们仅保留一个尾指针(rear),用于指向当前队尾节点,而不用维护头指针(因为队首始终是下一个元素)。以下是关键方法的实现:
1. 初始化(Enqueue初始化):
```c++
void initQueue(Queue* &queue) {
queue = new Node();
queue->next = queue;
queue->data = nullptr; // 或者设置一个默认值
}
```
2. 入队(enqueue):
```c++
void enqueue(Queue* &queue, int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = queue->next;
queue->next = newNode; // 尾指针更新
}
```
3. 出队(dequeue):
```c++
int dequeue(Queue* &queue) {
if (queue == nullptr || queue->next == queue) return -1; // 空队列处理
int frontValue = queue->next->data;
Node* temp = queue->next;
queue->next = temp->next;
delete temp; // 释放内存
return frontValue;
}
```
4. 取元素(peek):
```c++
int peek(Queue* &queue) {
if (queue == nullptr || queue->next == queue) return -1; // 空队列处理
return queue->next->data;
}
```
5. 判断非空(is_empty):
```c++
bool is_empty(Queue* queue) {
return queue == nullptr || queue->next == queue;
}
```
6. 主函数测试:
```c++
int main() {
Queue* queue = nullptr;
initQueue(queue);
enqueue(queue, 1); // 应该成功添加到队列
enqueue(queue, 2);
cout << "Peek: " << peek(queue) << endl; // 输出 1
cout << "Dequeue: " << dequeue(queue) << endl; // 输出并移除 1,然后应返回2
cout << "Is empty: " << (is_empty(queue) ? "Yes" : "No") << endl;
return 0;
}
```
注意:在实际编程中,还需要考虑错误处理和内存管理,比如检查分配失败的情况。这里为了简洁起见,没有包含所有的边界条件检查。
阅读全文