请你帮我实现一个队列数据结构,该结构存储的元素类型为结构体BtNode,并且在元素入队时若空间满可以自动分配内存
时间: 2024-10-24 16:06:23 浏览: 16
为了实现一个队列数据结构,我们首先需要定义`BtNode`结构体以及一个队列的头尾指针。当队列满时,我们可以动态地扩展容量。这里是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct BtNode {
int data;
struct BtNode* next; // 指向下一个节点的指针
} BtNode;
// 队列结构体,包含头和尾指针
typedef struct Queue {
BtNode* front; // 队首指针
BtNode* rear; // 队尾指针
int size; // 当前队列大小
int capacity; // 容量上限
} Queue;
// 初始化队列
Queue* createQueue(int capacity) {
if (capacity <= 0) {
printf("Capacity must be a positive integer.\n");
return NULL;
}
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->front = queue->rear = NULL;
queue->size = 0;
queue->capacity = capacity;
return queue;
}
// 入队操作(如果队列已满则扩容)
void enqueue(Queue* queue, int data) {
if (queue->size == queue->capacity) {
// 扩容
queue->capacity *= 2; // 或者其他适当的倍数
BtNode* newNode = (BtNode*)malloc(sizeof(BtNode));
newNode->data = data;
newNode->next = NULL;
if (queue->rear) {
queue->rear->next = newNode;
} else {
queue->front = newNode;
}
queue->rear = newNode;
} else {
// 正常情况下的入队
BtNode* newNode = (BtNode*)malloc(sizeof(BtNode));
newNode->data = data;
newNode->next = queue->rear;
if (queue->front == NULL) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
}
queue->size++;
}
}
// 出队操作
int dequeue(Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty.\n");
return -1;
} else {
int data = queue->front->data;
BtNode* temp = queue->front;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
queue->size--;
return data;
}
}
// 清空队列并释放内存
void destroyQueue(Queue* queue) {
while (queue->front != NULL) {
BtNode* temp = queue->front;
queue->front = queue->front->next;
free(temp);
}
free(queue);
}
// 示例用法
int main() {
Queue* q = createQueue(5); // 创建一个容量为5的队列
enqueue(q, 1);
enqueue(q, 2);
enqueue(q, 3);
while (!isEmpty(q)) {
printf("%d ", dequeue(q)); // 输出队列中的元素
}
destroyQueue(q); // 清理内存
return 0;
}
```
阅读全文