队列(queue)也是一种受限的线性表。队列的概念与现实生活中的排队相似。

它只允许在线性表的一端进行元素的插入，而在另一端进行元素的删除。允许插入的一端称为队尾(rear），允许刷除的一端称为队头 (front)。

一、队列特点

• 在队列中，通常加入元素称之为入队，删除元素称之为出队。

• 新来的成员总是排在队尾，排在队列最前面的成员最先离开队列，即先进先出 (First In First Out, FIFO)表。

• 设有队列 Q ，在空队列的情况下，依次加入元素 a₁, a₂, ... , a_n，得到 Q = (a₁, a₂, ... , a_n)。那么 a₁就是对队元素，a_n 是队尾元素。出队顺序必须是 a₁先出，然后a₂，最后是 a_n 出队。

二、练习题

( )是一种先进先出的线性表

A. 栈

B. 队列

C. 哈希表(散列表)

D. 二叉树

参考答案 B

先进先出是队列的特点。

栈和队列都是特殊的线性表，其共同点是( )

A. 只允许在端点处插入和删除元素

B. 都是先进先出

C. 都是先进后出

D. 都可以用链表存储

参考答案 D

线性表可以是顺序表存储，也可以是链表存储。

下列叙述中，正确的是( )

A. 线性表的顺序存储结构优于链表存储结构

B. 队列的操作方式是先进后出

C. 栈的操作方式是先进先出

D. 二维数组是指它的每个数据元素为一个顺序表的顺序表

参考答案 D

二维数组就是一维数组的数组。

下列结构中为非线性表的是( )

A. 树

B. 向量

C. 二维表

D. 矩阵

参考答案 A

设栈S和队列Q初始状态为空，元素a1,a2,...,a6依次通过栈S。一个元素出栈后就进入队列Q，若出队的顺序分别是a2,a4,a3,a6,a5,a1，则栈S的容量至少是( )

A. 2

B. 3

C. 4

D. 5

参考答案 B

出队列的顺序就是出栈的顺序，所以当栈中元素个数最多的时候，就是S的容量。画图演算，B选项正确。

若循环队列存储在数组A[0...n]，则入队时的操作是( )

A. rear=rear+1

B. rear=(rear+1) mod (n-1)

C. rear=(rear+1) mod n

D. rear=(rear+1) mod (n+1)

参考答案 D

循环队列就是一个队列首(front)尾(rear)相连。

入队是在队尾，所以是rear+1；主意：A的元素是0~n，所以长度是n+1；

为了防止溢出，用取余的方式得到rear=(rear+1) mod (n+1)；

front也是一样，如果是一个元素出队列，front=(front+1)mod(n+1)