接做网站单子,沈阳网站建设tlmh,网页编辑按键,班级网站设计论文1、队列的概念2、队列的结构如何选择合适的数据结构实现队列#xff08;数组or链表#xff09; 3、队列的链式存储3.1 队列的链式存储结构3.2 队列的常见接口3.3 队列的接口实现初始化判空入队列出队列获取队头元素获取队尾元素获取节点个数销毁 3.4 源代码 4、队列的顺序存储… 1、队列的概念2、队列的结构如何选择合适的数据结构实现队列数组or链表 3、队列的链式存储3.1 队列的链式存储结构3.2 队列的常见接口3.3 队列的接口实现初始化判空入队列出队列获取队头元素获取队尾元素获取节点个数销毁 3.4 源代码 4、队列的顺序存储循环队列 1、队列的概念
队列是一种先进先出(First In First Out FIFO)的数据结构可以简单理解为排队的概念。在队列中数据项按照插入的顺序排列并且只能在队列的一端插入称为队尾在另一端删除称为队头。
2、队列的结构 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 如何选择合适的数据结构实现队列数组or链表
在前面学习的顺序表中我们知道数组只有在尾插和尾删效率高为O(1)当需要对头部元素操作时效率较低为O(n)。队列的特点是在队尾插入元素在队头删除元素序列两端都需要访问这就导致使用数组实现队列时必定有一端的插入(or删除)效率低因此不建议使用数组实现队列。
3、队列的链式存储
通过上面的分析我选择链式存储结构来实现队列。这是因为链式存储结构实现两端的高效访问很简单——只需要增加一个尾指针即可实现两端的O(1)访问
3.1 队列的链式存储结构
定义两个结构体
QNode保存队列中节点的元素数据和下一个节点Queue保存头指针、尾指针和队列中有效元素个数
typedef int QDateType;
typedef struct QueueNode
{QDateType val;//当前节点的数据struct QueueNode* next;//当前节点的下一个节点
}QNode;typedef struct Queue
{QNode* phead;//头指针QNode* ptail;//尾指针int size;//记录队列有效元素个数
}Queue;3.2 队列的常见接口
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq,QDateType x);//出队列
void QueuePop(Queue* pq);
//获取队头元素
QDateType QueueFront(Queue* pq);
//获取队尾元素
QDateType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//获取有效元素个数
int QueueSize(Queue* pq);3.3 队列的接口实现
初始化
头尾指针置空队列有效元素个数初始化为0
void QueueInit(Queue* pq)
{assert(pq);//哨兵位可选可不选可以有也可以没有pq-phead pq-ptail NULL;pq-size 0;
}判空
直接返回Queue结构体保存的size即可
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}入队列 队尾入队步骤 1申请新节点并初始化该节点将x赋值下一个节点置空 2判断是否存在尾节点队列是否为空
存在尾节点队列不为空只需将新节点接到队尾尾指针后移一位即可。不存在尾节点队列为空改变队头和队尾的值即可
3队列有效节点个数加1
void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));//申请新节点if (newnode NULL){perror(malloc fail);return;}//对新节点初始化newnode-val x;newnode-next NULL;//有尾节点队列不为空if (pq-ptail){pq-ptail-next newnode;pq-ptail newnode;}else{//一个有效节点都没队列为空pq-phead pq-ptail newnode;}pq-size;
}出队列
1判空队列不为空才能出队 2判断队列有效节点的个数
一个节点释放该节点将头尾指针置空多个节点定义临时QNode类型变量保存头节点的下一个节点释放头节点头节点更新为保存的节点
3队列有效节点个数减1
void QueuePop(Queue* pq)
{assert(pq);//三种情况0个节点1个节点,多个节点//0个assert(pq-phead);//暴力检查//if (pq-phead NULL) return;//温柔检查//队列只有1个有效节点if (pq-phead-nextNULL){free(pq-phead);pq-phead pq-ptail NULL;}else{//队列有多个有效节点QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}获取队头元素
断言判断是否存在头节点如果存在直接返回头节点的值即可
QDateType QueueFront(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq-phead);return pq-phead-val;
}获取队尾元素
断言判断是否存在尾节点如果存在直接返回尾节点的值即可
QDateType QueueBack(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq-ptail);return pq-ptail-val;
}获取节点个数
返回size即可
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}销毁
遍历删除释放所有节点最后头尾指针悬空size置0
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}3.4 源代码 .h文件 #pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueNode* next;
}QNode;
入队
为什么需要两个指针
//void QueuePush(QNode** head,QNode** ptail);
//
出队
//void QueuePop(QNode** head);typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq,QDateType x);//出队列
void QueuePop(Queue* pq);QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);.c文件 #include Queue.h//初始化
void QueueInit(Queue* pq)
{assert(pq);//哨兵位可选可不选pq-phead pq-ptail NULL;pq-size 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}//入队列
void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;//有尾节点if (pq-ptail){pq-ptail-next newnode;pq-ptail newnode;}else{//一个有效节点都没pq-phead pq-ptail newnode;}pq-size;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);//三种情况0个节点1个节点,多个节点//0个assert(pq-phead);//暴力检查//if (pq-phead NULL) return;//温柔检查//1个if (pq-phead-nextNULL){free(pq-phead);pq-phead pq-ptail NULL;}else//多个{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDateType QueueFront(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq-phead);return pq-phead-val;
}
QDateType QueueBack(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq-ptail);return pq-ptail-val;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}4、队列的顺序存储循环队列
虽然队列的一般实现使用链式存储但是也有一些情况可以使用数组存储比如循环队列。 具体可以查看这篇博客———循环队列OJ
END
