C语言循环链表实现队列:单指针指向队尾元素
C语言循环链表实现队列:单指针指向队尾元素
本文将介绍使用C语言,以带头节点循环链表表示队列,并只设一个指针指向队尾元素结点的队列实现方法。该方法相比传统队列实现,节省了头指针空间,且在某些场景下可以提高效率。
数据结构定义:
typedef struct Node {
int data;
struct Node *next;
} Node;
队列初始化:
void initQueue(Node **rear) {
*rear = (Node *)malloc(sizeof(Node)); // 创建一个头结点
(*rear)->next = *rear; // 头结点的 next 指向自身
}
入队列:
void enQueue(Node **rear, int data) {
Node *newNode = (Node *)malloc(sizeof(Node)); // 创建一个新结点
newNode->data = data;
newNode->next = (*rear)->next; // 新结点的 next 指向头结点
(*rear)->next = newNode; // 队尾结点的 next 指向新结点
*rear = newNode; // 队尾指针指向新结点
}
出队列:
int deQueue(Node **rear) {
if ((*rear)->next == *rear) { // 队列为空
printf('Queue is empty!\n');
return -1;
}
int data = (*rear)->next->data; // 取出队头结点的数据
Node *temp = (*rear)->next; // 保存队头结点的指针
(*rear)->next = temp->next; // 队头结点的 next 指向下一个结点
if (*rear == temp) { // 队列中只有一个结点
*rear = (*rear)->next; // 队尾指针指向头结点
}
free(temp); // 释放队头结点的空间
return data;
}
代码示例:
#include <stdio.h>
#include <stdlib.h>
// ... 队列数据结构和函数定义 ...
int main() {
Node *rear = NULL;
initQueue(&rear);
enQueue(&rear, 1);
enQueue(&rear, 2);
enQueue(&rear, 3);
printf('出队元素:%d\n', deQueue(&rear));
printf('出队元素:%d\n', deQueue(&rear));
return 0;
}
总结:
本文介绍了使用循环链表实现队列的另一种方式,仅使用一个指针指向队尾元素。该方法在某些场景下可以提高效率,但需要注意代码逻辑的理解和实现。
原文地址: https://www.cveoy.top/t/topic/n8c9 著作权归作者所有。请勿转载和采集!