初阶数据结构之队列的实现
1 队列的定义
什么是队列呢？队列只允许在一端进行插入数据操作，在另一端进行删除数据操作。队列具有先进先出FIFO(First In First Out)的特性。
队头：删除数据的一端称为队头。
队尾：插入数据的一端称为队尾。
2 队列底层结构的选择
底层采用数组来实现，在删除队头元素的时候，需要移动数组元素，时间复杂度为O(N)，还会存在空间浪费。
采用链表实现队列，删除队头元素时，只需要让head指向下一个节点同时将头结点的空间还给操作系统。在队尾增加元素时，申请一块空间存放数据，让新节点成为链表尾节点，为了避免在增加元素时需要找链表尾节点，所以创建一个tail指针，指向链表尾节点。
因此采用链表来实现队列再合适不过了。
3 队列的实现
3.1 队列的定义
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//为了降低时间复杂度，增加一个尾指针，同时为了方便维护代码，对两个指针使用结构体进行封装
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
3.2 队列的接口
//初始化队列
void QueueInit(Queue* pq);
//队尾插入数据
void QueuePush(Queue* pq, QDataType x);
//队头出数据
QDataType QueueFront(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//删除队头数据
void QueuePop(Queue* pq);
//队列的大小
int QueueSize(Queue* pq);
//队尾出数据
QDataType QueueBack(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
3.2.1 初始化队列
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
刚开始队列为空，head和tail指向NULL。保证pq不能为NULL，否则
通过pq去访问head和tail会造成野指针。
3.2.2 队尾插入数据
//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newnode)
{
printf("QueuePush():malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
如果head为NULL，说明队列为空，则让head和tail同时指向头结点。
否则，则让tail->next保存新节点的地址同时让tail指向新节点，使新节
点成为链表的尾节点。
3.2.3 队列是否为空
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
if (pq->head == NULL)
{
return true;
}
else
{
return false;
}
}
head指向NULL，说明队列为空，否则，队列不为空。
3.2.4 队头出数据
//队头出数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
队列不为空才能出数据，返回队列头结点的数据（因为head指向头结点）。
3.2.5 删除队头数据
//删除队头数据
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//记录下一个节点的地址
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
删除数据首先要保证队列不能为空，其次使head指向头结点的下一个
节点，再释放头结点。如果head指向了NULL，说明队列为空，此时
应该将tail置为NULL。避免野指针的出现。
3.2.6 队列的大小
//队列的大小
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
int size = 0;
while (NULL != cur)
{
size++;
cur = cur->next;
}
return size;
}
对链表进行遍历，计算链表节点的个数。
3.2.7 队尾出数据
//队尾出数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
保证队列不为空的前提下，返回tail指向的节点的数据。
3.2.8 销毁队列
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->head!=NULL)
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->tail = NULL;
}
对链表进行遍历，先记录要删除节点的下一个节点的地址，然后释放
删除节点的空间，让head指向下一个节点。最后，将tail置为NULL
（避免野指针）。
4 队列完整代码的实现
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//为了降低时间复杂度，增加一个尾指针，同时为了方便维护代码，对两个指针使用结构体进行封装
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//队尾插入数据
void QueuePush(Queue* pq, QDataType x);
//队头出数据
QDataType QueueFront(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//删除队头数据
void QueuePop(Queue* pq);
//队列的大小
int QueueSize(Queue* pq);
//队尾出数据
QDataType QueueBack(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newnode)
{
printf("QueuePush():malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//队头出数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
if (pq->head == NULL)
{
return true;
}
else
{
return false;
}
}
//删除队头数据
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//记录下一个节点的地址
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
//队列的大小
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
int size = 0;
while (NULL != cur)
{
size++;
cur = cur->next;
}
return size;
}
//队尾出数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->head!=NULL)
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->tail = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void TestQueue1()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QDataType ret = QueueFront(&q);
printf("%d ", ret);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
}
void TestQueue2()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
int size = QueueSize(&q);
printf("%d ", size);
QDataType ret = QueueBack(&q);
printf("%d ", ret);
QueueDestroy(&q);
}
int main()
{
//TestQueue1();
TestQueue2();
return 0;
}