队列(Queue):队列简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。
这和我们日常生活中的排队是一致的,最早排队的也是最早离队的。其操作的特性是先进先出 (First In First Out, FIFO),故又称为先进先出的线性表,如图3-5所示。
队头(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。
需要注意的是,队列是操作受限的线性表,所以,不是任何对线性表的操作都可以作为队列的操作。比如,不可以随便读取队列中间的某个数据。