假设以带头节点的单项循环链表表示队列,并且只设一个指针指向队尾元素节点(注意:不设头指针),试设计并验证相应的队列初始化,对列的判空,入队列,出队列和遍历队列的算法。。用C语言来实现
时间: 2024-05-16 21:12:43 浏览: 88
以下是基于带头节点的单项循环链表表示队列的算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 队列节点结构体
typedef struct queue_node {
int data;
struct queue_node *next;
} QueueNode;
// 队列结构体
typedef struct {
QueueNode *rear; // 队尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->rear = (QueueNode *)malloc(sizeof(QueueNode));
q->rear->next = q->rear; // 队尾指向头节点
}
// 判断队列是否为空
int isQueueEmpty(Queue *q) {
return q->rear == q->rear->next;
}
// 入队列
void enQueue(Queue *q, int data) {
QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
p->data = data;
p->next = q->rear->next;
q->rear->next = p;
q->rear = p;
}
// 出队列
int deQueue(Queue *q) {
if (isQueueEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
QueueNode *p = q->rear->next->next;
int data = p->data;
q->rear->next->next = p->next;
if (q->rear == p) {
q->rear = q->rear->next;
}
free(p);
return data;
}
// 遍历队列
void traverseQueue(Queue *q) {
if (isQueueEmpty(q)) {
printf("Queue is empty.\n");
return;
}
QueueNode *p = q->rear->next->next;
while (p != q->rear->next) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
Queue q;
initQueue(&q);
// 入队列
enQueue(&q, 1);
enQueue(&q, 2);
enQueue(&q, 3);
enQueue(&q, 4);
// 遍历队列
traverseQueue(&q);
// 出队列
int data = deQueue(&q);
printf("deQueue: %d\n", data);
// 遍历队列
traverseQueue(&q);
return 0;
}
```
运行结果:
```
1 2 3 4
deQueue: 1
2 3 4
```
阅读全文