品牌网站建设专家,医疗器械网上采购平台,wordpress火车头采集,如何在百度上推广自己白日去如箭#xff0c;达者惜今阳。 --朱敦儒目录
#x1f681;前言#xff1a;
#x1f3dd;️一.队列的概念及结构
#x1f33b;二.队列各种功能的实现
#x1f34d;1.队列的初始化
#x1f3dd;️2.队列…白日去如箭达者惜今阳。 --朱敦儒目录
前言
️一.队列的概念及结构
二.队列各种功能的实现
1.队列的初始化
️2.队列的尾入
3.队列头的元素
4.队列的头出
5.判断是否为空
6.队列尾的元素
7.销毁队列
三.队列的全部代码
1.Queue.h
2.Queue.c
3.test.c 前言
前几天我们对栈进行了实现栈是数据先进后出而今天我们要是实现的队列是完全相反的队列是数据先进先出。而在栈中我们使用的顺序表(数组)来实现的。而队列却用单链表来实现是更加合适的。
在队列入数据的时候相当于是尾插而队列出数据的时候相当于是头删。
队列的顺序结构 入队不需要移动任何元素时间复杂度为O(1)。 出队所有元素需要往前移动时间复杂度为O(N)。队列的链式结构 首先我们定义两个指针队头指针指向第一个节点队尾指针指向尾节点。 入队尾插时间复杂度为O(1)。 出队头删时间复杂度为O(1)。结论所以我们使用单链表来实现队列。
️一.队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行数据操作的特殊线性表队列具有先进先出FIFO(Frist in First out)。
入队列进行插入操作的一端称为队尾。出队列进行删除操作的一端称为对头。
队列的初始结构单链表实现
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;//单链表QDataType data;
}QNode;typedef struct Queue
{QNode* head;//队列头QNode* tail;//队列尾
}Queue;
二.队列各种功能的实现
1.队列的初始化 这里我们实现的单链表是无头不循环的单链表。所以我们把队列头和队列尾初始化为空指针。
//初始化
void QueueInit(Queue* ps)
{assert(ps);ps-head ps-tail NULL;
}
️2.队列的尾入 对于队列的尾入我们要分为两种情况第一种第一次尾入数据的时候队列头和队列尾都是指向的同一个位置并且都是空当我们要尾入的时候创建一个新的结点把新结点赋值给队列的头和队列的尾。
第二种队列已经有数据了我们把新的结点链接到尾后面然后再把新结点赋值为新的结点也就是更新队列的尾。总结队列头是一直不变的队列尾入一个数据就需要把队列尾往后面移动一位。
//队尾入
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newnode (QNode*)malloc(sizeof(QNode));//创建一个新的结点if (newnode NULL){perror(malloc\n);return;}newnode-data x;newnode-next NULL;if ( ps-tail NULL)//第一种情况{ps-headps-tail newnode;//新结点就是队列尾和队列头}else//第二种情况{ps-tail-next newnode;//队列尾链接新的结点ps-tail newnode;//更新队列尾}
}
3.队列头的元素 需要知道队列头的元素是非常简单的只需要返回队列头的元素即可。
//头的元素
QDataType QueueFront(Queue* ps)
{assert(ps);assert(ps-head);return ps-head-data;
}
4.队列的头出 队列的头出也是分为两种情况第一种当队列只有一个结点的时候直接free掉第一个结点即可然后把队列头和对列尾赋值尾空即可。第二种当队列有两个及两个以上的结点的时候我们先保存队列头的下一个结点然后free掉队列头即可。
//对头出
void QueuePop(Queue* ps)
{assert(ps);assert(ps-head);if (ps-head-next NULL)//当队列只有一个结点时{free(ps-head);ps-head ps-tail NULL;}else//当队列有两个或者两个以上的结点时{QNode* next ps-head-next;//free掉第一个结点时先保存下一个结点free(ps-head);ps-head next;}
}
5.判断是否为空
在队列出的时候我们出一个数据就要判断一下队列是否为空如果为空我们就不能出数据了。 我们还是和栈的判断空一样使用bool值来判断。
//判断是否为空
bool QueueEmpty(Queue* ps)
{assert(ps);return ps-head NULL;
}有了上面的代码我们就可以把出队列的数据给打印一下。
很明显这和队列的结构时一致的即先进先出。
6.队列尾的元素
//尾的元素
QDataType QueueBack(Queue* ps)
{assert(ps);assert(ps-head);return ps-tail-data;
}7.销毁队列
最后退出程序我们再把队列给销毁一下。
//销毁队列
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur ps-head;while (cur){QNode* next ps-head-next;free(ps-head);ps-head next;cur next;}ps-head ps-tail NULL;
}
最后我们再把队列的功能给实现一下
三.队列的全部代码
1.Queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;//初始化
void QueueInit(Queue* ps);//队尾插
void QueuePush(Queue* ps,QDataType x);//队头出
void QueuePop(Queue* ps);//头的元素
QDataType QueueFront(Queue* ps);//尾的元素
QDataType QueueBack(Queue* ps);//队列的元素个数
int QueueSize(Queue* ps);//判断是否为空
bool QueueEmpty(Queue* ps);//销毁队列
void QueueDestroy(Queue* ps);
2.Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h//初始化
void QueueInit(Queue* ps)
{assert(ps);ps-head ps-tail NULL;
}//队尾入
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc\n);return;}newnode-data x;newnode-next NULL;if ( ps-tail NULL){ps-headps-tail newnode;}else{ps-tail-next newnode;ps-tail newnode;}
}//对头出
void QueuePop(Queue* ps)
{assert(ps);assert(ps-head);if (ps-head-next NULL)//当队列只有一个结点时{free(ps-head);ps-head ps-tail NULL;}else//当队列有两个或者两个以上的结点时{QNode* next ps-head-next;//free掉第一个结点时先保存下一个结点free(ps-head);ps-head next;}
}//头的元素
QDataType QueueFront(Queue* ps)
{assert(ps);assert(ps-head);return ps-head-data;
}//尾的元素
QDataType QueueBack(Queue* ps)
{assert(ps);assert(ps-head);return ps-tail-data;
}//队列的元素个数
int QueueSize(Queue* ps)
{int count 0;QNode* cur ps-head;while (cur){count;cur cur-next;}return count;
}//销毁队列
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur ps-head;while (cur){QNode* next ps-head-next;free(ps-head);ps-head next;cur next;}ps-head ps-tail NULL;
}//判断是否为空
bool QueueEmpty(Queue* ps)
{assert(ps);return ps-head NULL;
}3.test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
int main()
{QNode q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);printf(对于队列 1 2 3 4 出的数据为\n);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}QueuePush(q, 5);QueuePush(q, 6);QueuePush(q, 7);QueuePush(q, 8);printf(\n);printf(队列的元素为 5 6 7 8\n);printf(队列头的元素为\n);int first QueueFront(q);printf(%d\n, first);printf(队列尾的元素为:\n);int tail QueueBack(q);printf(%d\n, tail);printf(队列的元素的个数为\n);int count QueueSize(q);printf(%d\n, count);QueueDestroy(q);printf(退出程序\n);printf(队列已经被销毁……\n);return 0;
}
