每日科技名词|队列

情毒

队列

queue

定义：只在表的一端进行插入操作，而在另一端进行删除操作的线性表。

学科：计算机科学技术_理论计算机科学_数据结构

相关名词：线性表 数据结构


图片来源：视觉中国

【延伸阅读】

队列是一种特殊的线性表。线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同属性的数据元素的有限序列。队列的特殊之处就在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，这种特殊性我们称之为先进先出。因此，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。若队列中没有元素时，称为空队列。

队列由于实现方式等原因有很多种类。队列以数组实现称为顺序队列，以链表实现称为链式队列，除此之外还可以使用栈来实现优先队列。有时为了提高队列的空间利用率，就会将队头和队尾连接起来，这时的队列称为循环队列。

一般来说，队列的操作有如下五种：

1.初始化队列。示意代码：Init_Queue(q)。初始条件：队列q不存在。操作结果：构造了一个空队列。

2.入队操作。示意代码：In_Queue(q,x)。初始条件：队列q存在。操作结果：对已存在的队列q，插入一个元素x到队尾，队列发生变化。

3.出队操作。示意代码：Out_Queue(q,x)。初始条件：队列q存在且非空。操作结果：删除队首元素，并返回其值，队列发生变化。

4.读取队头元素。示意代码：Front_Queue(q,x)。初始条件：队列q存在且非空。操作结果：读取队头元素，并返回其值，队列不变。

5.判队空操作。示意代码：Empty_Queue(q)。初始条件：队列q存在。操作结果：若q为空队则返回为1，否则返回为0。

队列虽然是一种比较简单的数据结构，但是它有很多的应用。比如生活中处处可见的排队，操作系统中的任务调度，人们工作时发的短信和邮件等，这种任务的核心问题都是先来先服务。此外，在数据结构和算法领域也有很多应用，可以用队列将复杂的二维拓扑问题转换成一维线性问题，也可以用队列来求解迷宫问题。

（延伸阅读作者：大连理工大学计算机学院教授 杨鑫）

红尖烈刀

沙发。。。。。。。。。。。。。。。。。