写一段代码假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。
时间: 2024-03-17 09:45:51 浏览: 112
好的,以下是使用带头结点的循环链表表示队列的代码实现,同时只设一个指针指向队尾元素站点。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
typedef struct {
ListNode* rear; // 指向队尾元素站点
} Queue;
void init(Queue* q) {
q->rear = NULL;
}
int isEmpty(Queue* q) {
return q->rear == NULL;
}
void enqueue(Queue* q, int val) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
if (isEmpty(q)) {
q->rear = node;
node->next = node;
} else {
node->next = q->rear->next;
q->rear->next = node;
q->rear = node;
}
}
int dequeue(Queue* q) {
if (isEmpty(q)) {
return -1;
}
ListNode* head = q->rear->next;
int val = head->val;
if (head == q->rear) {
q->rear = NULL;
} else {
q->rear->next = head->next;
}
free(head);
return val;
}
int main() {
Queue q;
init(&q);
printf("Is queue empty: %d\n", isEmpty(&q));
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
printf("Is queue empty: %d\n", isEmpty(&q));
printf("Dequeue: %d\n", dequeue(&q));
printf("Dequeue: %d\n", dequeue(&q));
printf("Dequeue: %d\n", dequeue(&q));
printf("Dequeue: %d\n", dequeue(&q));
printf("Is queue empty: %d\n", isEmpty(&q));
return 0;
}
```
上述代码中,我们使用一个指针 `rear` 指向队尾元素站点,表示当前队列中最后一个入队的元素。在入队操作中,我们新建一个节点,并将其插入到队尾元素站点的后面,然后更新 `rear` 指针指向这个新节点。注意,如果队列为空,则将 `rear` 指向新节点,并将新节点的 `next` 指针指向自身,表示循环链表的特性。
在出队操作中,我们首先判断队列是否为空。如果为空,则返回一个特定的值,例如 `-1`。否则,我们将队头节点 `head` 指向队尾元素站点的后继节点,然后取出 `head` 的值作为出队元素的返回值。如果 `head` 恰好是队尾元素站点,说明队列中只有一个元素,我们将 `rear` 指针置为 `NULL`。否则,我们将队尾元素站点的 `next` 指针指向 `head` 的后继节点,然后释放 `head` 节点的内存。最后,返回出队元素的值即可。
需要注意的是,由于我们使用了循环链表来实现队列,因此在出队操作中,我们不需要考虑队头节点是不是第一个节点,而是只需要将队尾元素站点的后继节点作为队头节点即可。
阅读全文