假设以带头结点的循环链表示队列,并且只设置一个指针指向指向队尾元素(注意:不设置头指针),试编写相应的置空队列,判断队列是否为空,入队和出队等算法
时间: 2024-11-25 11:31:42 浏览: 44
首先,我们来定义一个结构体 `Node` 表示链表节点,以及一个全局变量 `tail` 指向当前队尾。
```c
typedef struct Node {
int data; // 存储数据
struct Node* next; // 指向下一个节点
} Node;
// 初始化一个空队列
void initQueue(Node** tail) {
*tail = NULL;
}
// 判断队列是否为空
int isQueueEmpty(Node* tail) {
return tail == NULL;
}
// 置空队列
void enqueueEmpty(Node** tail, int value) {
if (*tail != NULL) {
// 如果队列非空,则创建一个新的节点并将其添加到尾部
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = *tail;
*tail = newNode;
} else {
// 队列为空,直接插入新节点
*tail = (Node*)malloc(sizeof(Node));
(*tail)->data = value;
(*tail)->next = *tail; // 循环链表结构
}
}
// 出队操作(从队尾删除节点)
int dequeue(Node** tail) {
if (isQueueEmpty(*tail)) {
printf("Error: Queue is empty.\n");
return -1; // 返回错误码,表示队列为空
}
int value = (*tail)->data;
Node* temp = *tail;
// 更新尾指针,移除已删除的节点
(*tail) = (*tail)->next;
free(temp); // 释放内存
return value; // 返回出队的值
}
```
现在我们已经实现了队列的基本操作:
- `enqueueEmpty`: 置空队列或在队尾添加元素。
- `isQueueEmpty`: 判断队列是否为空。
- `dequeue`: 从队尾出队并返回值。
队列的特点是后进先出(LIFO,Last In First Out),所以在这里我们只有一个指针指向队尾,没有头指针。如果要实现常规的队列操作,比如在队首出队(Enqueue/Dequeue at front),则需要额外的逻辑和一个头指针。
阅读全文