链式结构实现队列
- 1.队列
- 1.1队列的概念及结构
- 1.2队列的实现
- 2. 队列的各种函数实现
- 3. 队列的全部代码实现
1.队列
1.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)的原则
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
如图所示：
1.2队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2. 队列的各种函数实现
首先，我们先定义一个栈的结构
typedef int QDataType;//节点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;//链表的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
这里我们定义了两个结构体，这是因为在尾插的时候需要一个尾指针，如果每次尾插的时候都要遍历找尾效率太低，所以，我们可以定义一个尾指针，在头删的时候需要一个头指针，这个size其实可以加上有也可以不加，但是不加上的话求队列长度的时候需要遍历，比较麻烦，多个数据共同管理这个队列，所以，我们可以封装成一个结构体来管理这个队列。
初始化队列
void QueueInit(Queue* pq)
{aseert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
因为，队列中的每个节点的空间都是动态开辟的，所以在用完队列后要及时释放动态开辟的每一个节点。
队尾入队列
void QueuePush(Queue* pq,QDataType x)
{assert(pq);QNode* newcode = QueueBuyNode(x);if (pq->phead == NULL){assert(pq->ptail == NULL);//防止一个为空一个不为空的情况pq->phead = pq->ptail = newcode;}else{pq->ptail->next = newcode;pq->ptail = pq->ptail->next;}pq->size++;
}
这里也可以不把申请节点的代码单独写成一个函数，因为这里只有这一个地方会用到申请节点的操作，但是还是建议封装成一个函数，一方面可以提高代码的可读性，另一方面可以在一定程度上避免代码出错。
这里的assert(pq->ptail == NULL);这句代码主要时为了防止自己的代码写错，造成一个为空一个不为空的情况，所以也可以不写，保证写代码的时候细心一点就可以了。
申请一个节点
QNode* QueueBuyNode(QDataType x)
{c* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;
}
注意：这里是申请一个节点，所以要用定义队列节点的结构体类型 QNode，而不是管理队列的结构题类型
队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead->next == NULL){pq->phead = NULL;pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead =next;}pq->size--;
}
这里的队头出数据也就是头删操作，要注意当删除的链表元素只剩一个时，这里的头指针和尾指针同时指向这一个节点，当删除这个节点的时候，头指针和尾指针都会改变，所以，最好单独处理一下。
因为当只有一个节点的时候执行删除操作后，头指针会变成空，所以我们可以在头指针变成空的时候也把尾指针变成空，所以，这个代码也可以这样写。
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}
获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
想要获取队头元素，只需要返回队头指针指向的元素的值
获取队列尾部元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
想要获取队尾元素，只需要返回队尾指针指向的元素的值
获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
这里只需要返回控制队列结构里面的size就可以了，如果不把size封装结构体里面就需要遍历链表求队列元素个数，不但麻烦，效率也低。
检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}
当头指针和尾指针同时指向空的时候，链表一定为空。
3. 队列的全部代码实现
Queue.h
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QDataType;//节点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;//链表的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);//队尾入队列
void QueuePush(Queue* pq, QDataType x);// 队头出队列
void QueuePop(Queue* pq);//获取队列头部元素
QDataType QueueFront(Queue* pq);// 获取队列队尾元素
QDataType QueueBack(Queue* pq);//获取队列中有效元素个数
int QueueSize(Queue* pq);//检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);Queue.c
#include "Queue.h"// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}QNode* QueueBuyNode(QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//队尾入队列
void QueuePush(Queue* pq,QDataType x)
{assert(pq);QNode* newcode = QueueBuyNode(x);if (pq->phead == NULL){assert(pq->ptail == NULL);pq->phead = pq->ptail = newcode;}else{pq->ptail->next = newcode;pq->ptail = pq->ptail->next;}pq->size++;
}// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead->next == NULL){pq->phead = NULL;pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead =next;}pq->size--;
}//获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}
Test.c
#include "Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("size : %d\n",QueueSize(&q));while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);return 0;
}
因为队列是后进先出的，所以要访问队列里面的元素时，必须要把队列当前元素取出才能访问下一个元素，每可以看到在打印队列里面的内容时，会把队列变成空，那么队列里面的内容就没有了，但时这也是实际当中的需求，所以不会有什么影响。
运行结果如图：
