前言
队列的实现也是LeetCode107的关键。队列的实现分为两种,一种是实现先进先出的数据结构,另外一种是使用双栈实现队列。本文介绍第一种的实现,在实现107题时对第二种的实现进行解析。
分析
队列是一种先进先出的数据结构,因此使用链式队列的方式实现起来比较简单。队列的基本操作如下,
typedef struct QueueNode {
int data;
struct QueueNode* next;
} QueueNode;
typedef struct {
QueueNode* front;
QueueNode* rear;
} LinkQueue;
void CreateQueue(LinkQueue* queue);
bool EnQueue(LinkQueue* queue, int data);
bool DeQueue(LinkQueue* queue, int* dataPtr);
void Destroy(LinkQueue* queue);
void Traverse(LinkQueue* queue);
实现
本文中队列实现的是无头结点的,因此在入队和出队时对头结点的处理。
void CreateQueue(LinkQueue* queue) {
queue->front = queue->rear = NULL;
}
bool EnQueue(LinkQueue* queue, int data) {
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
if (!node)
return false;
node->data = data;
node->next = NULL;
if (queue->front == NULL) {
queue->front = queue->rear = node;
} else {
queue->rear->next = node;
queue->rear = node;
}
return true;
}
bool DeQueue(LinkQueue* queue, int* dataPtr) {
if (queue->front == NULL)
return NULL;
QueueNode* p = queue->front->next, *q = queue->front;
queue->front = p;
q->next = NULL;
(*dataPtr) = q->data;
free(q);
return true;
}
void Destroy(LinkQueue* queue) {
while (queue->front) {
queue->rear = queue->front->next;
free(queue->front);
queue->front = queue->rear;
}
}
void Traverse(LinkQueue* queue) {
QueueNode* p = queue->front;
while(p) {
printf("%d ", p->data);
p = p->next;
}
}
结束语
本文中实现了一种先进先出的无头结点的链式队列。栈和队列这两种数据结构,是在树的宽度遍历中使用最频繁的两种,其中队列还可以用双栈的方式实现,具体的解析在下文实现树的宽度逆序层次遍历时会提到。
网友评论