什么是队列

在生活中，大家肯定都有过排队买票的经历，在排队买票时，排在前面的人先买到票离开排队的队伍，然后轮到后面的人买；如果又有人来买票，就依次排到队尾。买票的过程中，队伍中的人从头到尾依次出列。

像排队这样，先来的先离开，后来的排在队尾后离开，我们称之为“先进先出”（First In First Out，简称FIFO）原则。在数据结构中，也有一种数据结构遵循这一原则，那就是队列（Queue）。

队列和栈一样，也是一种受限制的线性表，它只允许在一端进行插入操作，在另一端进行删除操作。其中允许删除的一端称为队头，允许插入的一端称为队尾。向队列中插入元素称为入队，从队列中删除元素称为出队。图1就是一个队列。

图1 队列

队列中会有一个指针指向队头，这个指针称为队头指针。当有元素出队时，队头指针向后移动，指向下一个元素，下一个元素成为新的队头元素（类似于栈的栈顶指针）。

队列中也会有一个指针指向队尾，称为队尾指针，队尾指针是指向最后一个元素之后的一个空指针。当有元素需要入队时，就插入到队尾指针所指位置处，插入之后，队尾指针向后移动，指向下一个空位。

当队列已满时，元素不能再入队；同理，当队列为空，无法执行出队操作。

由于遵循“先进行出”原则，队列也叫先进先出表。

队列的常用操作如下：

● Create()：创建队列。

● Push()：入队。

● Out()：出队。

● getLength()：获取队列长度。

● getHead()：获取队头元素。

● Clear()：清空队列。

● Destory()：销毁队列。

队列在程序设计中的使用也颇为常见。如操作系统和客服系统，都是应用了队列这种数据结构来实现先进先出的排队功能；再比如用键盘进行各种字母和数字的输入并显示到显示器上，就是队列的典型应用。