队列的基本概念

队列的定义

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操作的特性是先进先出（First In First Out，FIFO），如图所示。

• 队头（Front）：允许删除的一端，也称队首。
• 队尾（Rear）：允许插入的一端。
• 空队列：不含任何元素的空表。

队列常见的基本操作

• InitQueue(&Q) ：初始化队列，构造一个空队列 Q 。
• QueueEmpty(Q)：判队列空，若队列 Q 为空返回 true，否则返回 false。
• EnQueue(&Q, x)：入队，若队列 Q 未满，将 x 加入，使之成为新的队尾。
• DeQueue(&Q, &x)：出队，若队列 Q 非空，删除队首元素，并用 x 返回。
• GetHead(Q, &x)：读队首元素，若队列 Q 非空，则将队首元素赋值给 x 。

需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。