【数据结构】什么是队列?

人生,是一个又一个小小的队列重现.春夏秋冬轮回年年,早中晚夜循环天天.变化的是时间,不变的是你对未来执着的信念. ——封清扬

📌队列的定义

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表.

队列是一种先进先出(First In First Out)的线性表,简称FIFO.允许插入的一端称为队尾,允许删除的一端称为队头.

队列在程序设计中用的非常频繁,比如用键盘在屏幕上进行各种字母或数字的输入. 我们都知道,键盘输入的内容是先存到键盘缓冲区然后再从键盘缓冲区输出到屏幕上,而键盘缓冲区存储数据的方式就是队列,假如我想告诉女朋友你是我的"god",那么用队列存储数据的话按先进先出原则,内容输出到屏幕上也应该是"god":

但是如果键盘缓冲区是使用栈来存储数据的,那就不得了了,按照先进后出的原则,我输入了"god",屏幕上却显示"dog",那估计晚上搓衣板和榴莲是少不了要跪一个了.

📌队列的抽象数据类型

同样是线性表,队列也有类似线性表的各种操作,不同之处在于插入数据只能在队尾进行,删除数据只能在队头进行.

队列的抽象数据类型如下:

ADT 队列(Queue)
Data
	队列的数据对象集合为 {a1, a2, ..., an},每个元素的类型均为QDataType.
	其中, 除第一个元素a1外, 每一个元素有且只有一个直接前驱元素.
	除了最后一个元素an外, 每一个元素有且只有一个直接后继元素.
	数据元素之间的关系是一对一的关系.
Operation
	InitQueue(*Q);			初始化操作, 建立一个空的队列Q.
    DestroyQueue(*Q)        若队列Q存在,则销毁它.
	QueueEmpty(Q);			若队列Q为空,返回true,否则返回false.
	ClearQueue(*Q);			将队列Q清空.
	GetHead(Q, *e);		    若队列Q存在且非空,用e返回Q的队头元素.
    EnQueue(*Q,e);          若队列Q存在,插入新元素e到队列Q中并成为队尾元素.
	DeQueue(*Q,*e);         删除队列Q中队头元素,并用e返回其值.
	QueueLength(Q);			返回队列Q的元素个数.
endADT

📌队列的顺序存储结构

顺序队列和顺序表一样,都是使用数组来实现的,对于队列这种只能一头插入,另一端删除的线性表来说,使用数组必然会导致入队和出队中有一个时间复杂度是O(1),另一个是O(n).

在顺序队列中,入队和出队的逻辑完全和顺序表的尾插,尾删,头插,头删逻辑一样,但区别在于,选择数组下标为0作队头,那入队就是尾插,出队就是头删. 其操作逻辑和顺序表完全相同,这里就不多赘述了.

📌队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出,简称链队列.

为了操作方便,我们将队头指针指向链队列的首节点,将队尾指针指向尾结点:

空队列时,front和rear都指向NULL.

链队列的入队操作和单链表尾插逻辑相同,但在尾插结束后需要移动队尾指针指向新队尾.

链队列的出队操作和单链表头删逻辑相同,但在头删后同样需要移动队头指针指向新队头.