使用C语言,设用带头结点的循环链表表示队列,并且只设一个尾指针,试编写相应的置队空、判断队列是否为空、入队和出队算法。
时间: 2024-10-19 11:16:18 浏览: 40
在C语言中,我们可以使用单尾指针(只有一个指向最后一个节点的指针,而队列本身没有专门的头节点)来实现循环链表表示的队列。这里是一个简单的示例:
```c
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node *next; // 指向下一个节点的指针
} Node;
// 初始化队列为空
void initQueue(Node **rear) {
*rear = NULL;
}
// 判断队列是否为空
int isEmpty(Node *rear) {
return rear == NULL;
}
// 置队空(清空队列)
void enqueueEmpty(Node **rear) {
*rear = NULL;
}
// 入队操作
void enqueue(int item, Node **rear) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 动态分配内存
newNode->data = item;
newNode->next = (*rear)->next; // 新节点的next指向当前尾部
(*rear)->next = newNode; // 尾部的next指向新节点,形成循环
if ((*rear) == newNode) { // 如果新节点成为新的尾部,说明队列仅有一个元素
*rear = newNode;
}
}
// 出队操作
int dequeue(Node **front, Node **rear) {
if (isEmpty(*front)) { // 队列为空
return -1; // 返回错误码
}
Node *temp = *front;
int item = temp->data; // 获取并删除头部数据
*front = (*front)->next; // 更新头指针
free(temp); // 释放头部节点
// 如果队列只剩一个元素,更新尾部指针
if (*front == *rear) {
*rear = NULL;
}
return item; // 返回删除的数据
}
```
阅读全文