宜兴做阿里巴巴网站,莱芜都市网下载,数据分析培训,办公室装修设计费标准一.队列的概念 队列#xff08;Queue#xff09;是一种常见的数据结构#xff0c;它按照先进先出的原则管理数据。这意味着最先进入队列的元素将被最先移出队列#xff0c;类似于现实生活中排队的场景。 在队列中#xff0c;数据项被添加到队列的一端#xff0c;称为队尾…一.队列的概念 队列Queue是一种常见的数据结构它按照先进先出的原则管理数据。这意味着最先进入队列的元素将被最先移出队列类似于现实生活中排队的场景。 在队列中数据项被添加到队列的一端称为队尾而从队列中移除数据项的操作则发生在另一端称为队首。新元素被添加到队列的尾部并且从队列中移除元素时总是从队列的头部开始。 队列的基本操作
队列的初始化。入队将元素添加到队列的尾部。出队从队列的头部移除元素。获取队首元素查看队列的头部元素但不移除它。判断队列是否为空检查队列是否不包含任何元素。队列的销毁。
队列常用于需要按顺序处理数据的场景比如任务调度、缓冲等。
二.队列的特点 1.先进先出队列中的元素按照先进先出的原则进行排列和访问。最先进入队列的元素将被最先移出队列。 2.有限容量队列通常具有固定的容量限制即队列中能够容纳的元素数量是有限的。当队列已满时无法再向其中添加新的元素除非先移除队列中的一些元素。 3.受限的访问队列的访问受到限制只能在队列的两端进行操作。元素的插入入队只能发生在队列的尾部而元素的移除出队只能从队列的头部进行。 4.动态变化队列的大小可以动态地扩展或收缩具体取决于实现队列的数据结构。一些队列的实现允许在需要时动态地增加其容量以适应更多的元素。 5.线性结构队列是一种线性数据结构元素之间的关系是一对一的。每个元素都有且仅有一个直接前驱和一个直接后继。 6.适用性队列常用于需要严格控制元素访问顺序的情况如任务调度、资源分配等。 7.高效性对于队列中的元素添加和移除操作时间复杂度通常是常数级别的。这使得队列在许多应用中具有高效的性能。 8.应用广泛队列是一种常见且重要的数据结构在计算机科学和软件工程中被广泛应用例如操作系统中的进程调度、网络数据包传输、消息队列、算法设计等领域。 9.稳定性队列的稳定性指的是对于相同的输入输出结果是确定的不受其他因素影响而这一点栈结构是做不到的。这使得队列在许多算法和系统设计中具有可靠性和可预测性。
三.队列的实现
队列是基于链表和顺序表来实现结合队列的特点使用链表来实现更为便洁。
源码
Queue.h
#pragma once
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.h
#define QueueData inttypedef struct QueueNode
{QueueData val;struct QueueNode* next;
}QueueNode;
typedef struct
{QueueNode* phead;QueueNode* pend;int size;
}Queue;//储存的是链表的头节点和链表的尾节点以及队列的元素个数更容易维护队列。
void QueueInit(Queue* pQ);//初始化
void QueuePush(Queue* pQ, QueueData x);//队尾入队
void QueuePop(Queue* pQ);//出队
QueueData QueueFront(Queue* pQ);//取队头元素
int QueueSize(Queue* pQ);//获取队列元素个数
bool QueueEmpty(Queue* pQ);//判空
void QueueDestroy(Queue* pQ);//销毁队列
Queue.c
#includeQueue.h
void QueueInit(Queue* pQ)
{assert(pQ);pQ-pend pQ-phead NULL;pQ-size 0;
}
void QueuePush(Queue* pQ, QueueData x)
{assert(pQ);QueueNode* pnew (QueueNode*)malloc(sizeof(QueueNode));assert(pnew);pnew-val x;pnew-next NULL;if (pQ-size 0){pQ-pend pQ-phead pnew;}else{pQ-pend-next pnew;pQ-pend pnew;}pQ-size;
}
QueueData QueueFront(Queue* pQ)
{assert(pQ);assert(pQ-size);return pQ-phead-val;
}
void QueuePop(Queue* pQ)
{assert(pQ);QueueData ret pQ-phead-val;if (pQ-size 1){free(pQ-phead);pQ-pend pQ-phead NULL;}else{QueueNode* pn pQ-phead;pQ-phead pQ-phead-next;free(pn);}pQ-size--;return ret;
}
int QueueSize(Queue* pQ)
{assert(pQ);return pQ-size;
}
bool QueueEmpty(Queue* pQ)//判空
{assert(pQ);return pQ-size;
}
void QueueDestroy(Queue* pQ)
{assert(pQ);while (pQ-phead){QueueNode* pnext pQ-phead-next;free(pQ-phead);pQ-pheadpnext;}pQ-pend pQ-phead NULL;pQ-size 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
int main()
{Queue ps;QueueInit(ps);int n 10;while (n--)QueuePush(ps, n 1);while (QueueEmpty(ps)){printf(%d ,QueueFront(ps));QueuePop(ps);}QueueDestroy(ps);return 0;
}
