前面所讲的栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出”（First In First Out，FIFO）的数据结构，即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾（rear），把允许删除的一端叫队头（front）。图3－11所示是一个有5个元素的队列。入队的顺序依次为a1、a2、a3、a4、a5，出队时的顺序将依然是a1、a2、a3、a4、a5。

图3－11 队列示意

显然，队列也是一种运算受限制的线性表，所以又叫先进先出表。

在日常生活中队列的例子很多，如排队买东西，排头的买完后走掉，新来的排在队尾。在队列上进行的基本操作如下。

（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。