1.队列
1.1队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
1.2队列的实现
1.准备工作
还是三个文件
头文件中需要包含库函数等
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
//表示队列
typedef struct QueueNode
{
int val;
struct QueueNode* next;
}QNode;
//队列的结构
typedef struct Queue
{
QNode* phead;//头结点指针
QNode* ptail;//尾结点指针
int size;
}Queue;
//初始化
void QueueInit(Queue* qp);
//销毁
void QueueDestory(Queue* qp);
//入队列
void QueuePush(Queue* qp,QDataType x);
//出队列
void QueuePop(Queue* qp);
//获取队列头部元素
QDataType QueueFront(Queue* qp);
//获取队列尾部元素
QDataType QueueBack(Queue* qp);
//判断是否为空
bool QueueEmpty(Queue* qp);
//获取队列的有效元数个数
int QueueSize(Queue* qp);
2.初始化队列
初始化队列和初始化栈其实差不多
都是先把指针置为空
然后再将数据置为0
//初始化
void QueueInit(Queue* qp)
{
assert(qp);
qp->phead = NULL;
qp->ptail = NULL;
qp->size = 0;
}3.销毁队列
销毁队列的话
就是遍历队列，然后将队列中的指针给free掉
并置为空
数据也置为0
void QueueDestory(Queue* qp)
{
assert(qp);
QNode* cur = qp->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
qp->phead = qp->ptail = NULL;
qp->size = 0;
}4.入队列
首先需要开辟空间
然后检测开辟的空间否为开辟成功
然后就是把数据x传入到val中
让next置为空
如果尾结点不为空，那么就让他的next去指向新的节点，再让新开辟的成为尾结点
并让size++
void QueuePush(Queue* qp, QDataType x)
{
assert(qp);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("mallco fall");
return;
}
newnode->val = x;
newnode->next = NULL;
if (qp->ptail)
{
qp->ptail->next = newnode;
qp->ptail = newnode;
}
else
{
qp->phead = qp->ptail = newnode;
}
qp->size++;
}
5.出队列
出队列的话我们需要检测一下，分为多个情况
0 1和多
首先是0个节点
没有节点的话我们需要断言头结点是否为空
一个节点的话，我们需要判断他的头结点的next是否为空
是就是一个节点
那么我们需要释放掉头结点，让头和尾都为空
多个节点的话就需要创建一个新节点
让头结点的next指向新的节点
然后free掉头结点
让新节点成为头结点
最后让size--
void QueuePop(Queue* qp)
{
assert(qp);//多种情况，0个节点，一个节点和多个节点
温柔检查
//if (qp->phead == NULL)
//{
// return;
//}
//暴力检查,0个节点
assert(qp->phead != NULL);
//一个节点
if (qp->phead->next == NULL)
{
free(qp->phead);
qp->phead = qp->ptail = NULL;
}
//多个节点
else
{
QNode* next = qp->phead->next;
free(qp->phead);
qp->phead = next;
}
qp->size--;
}
6.获取队列头元素
获取头元素就是获取头元素的val
QDataType QueueFront(Queue* qp)
{
assert(qp);
assert(qp->phead != NULL);
return qp->phead->val;
}7.获取队列尾元素
获取尾元素就是获取它的尾的val
QDataType QueueBack(Queue* qp)
{
assert(qp);
assert(qp->ptail != NULL);
return qp->ptail->val;
}8.判断是否为空
判断是否为空只需要返回头和尾节点是否为空
bool QueueEmpty(Queue* qp)//判断空
{
assert(qp);
return qp->phead == NULL;//qp->size == 0;
}9.有效元素个数
有效元素个数只需要返回他的size就可以了
int QueueSize(Queue* qp)
{
assert(qp);
return qp->size;
}
