一）队列的定义
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的线性表。
- 允许删除的一端称为队头（Front）。
- 允许插入的一端称为队尾（Rear）。
- 当队列中没有元素时称为空队列。
- 队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
二）顺序队列和链队列
2.1）顺序队列
顺序队列是基于顺序存储结构的，一般使用数组实现。在顺序队列中需要注意溢出的情况。
"下溢"现象
当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
"真上溢"现象
当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
"假上溢"现象
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
对于假上溢，有两种解决方案。
(1) 采用平移元素的方法，即一旦发生“假溢出”就把整个队列的元素平移到存储区的首部。平移元素的方法效率是很低的。
(2)将整个队列作为循环队列来处理。这样，虽然物理上队尾在队首之前，但逻辑上队首仍然在前，作插入和删除运算时仍按"先进先出"的原则。
2.2）链队列
链队列采用链式结构实现，较之顺序队列不会出现溢出现象，而且出队、入队只需修改头结点或尾节点的地址。
三）java中的队列
java提供了多种Queue，api稍微有点复杂。
摘抄：http://www.javamex.com/tutorials/synchronization_concurrency_8_queues_2.shtml
Types of Queues
Java provides Queue implementations depending on a few key criteria:
- thread-safety: if you don't require the queue to be accessed concurrently from multiple threads, then a plain LinkedList can be used as a Queue; the advantage of the other implementations is that they offer efficient thread-safety;
- blocking or non-blocking: various blocking implementations add extra methods to put and remove items from the queue, blocking until the operation is possible, with an optional time limit;
- bound or non-bound: sometimes it is useful to put an upper limit on the number of items that can fit in the queue, e.g. to prevent a thread pool from queueing up too many jobs when the machine is busy;
- other special operations: Java provides an implementation that orders by priority, and another that applies a delay to queued items.
As of Java 6, the various queue classes are as follows:
| Blocking? | Other criteria | Bound | Non-bound |
|---|---|---|---|
| Blocking | None | ArrayBlockingQueue | LinkedBlockingQueue |
| Priority-based | PriorityBlockingQueue | ||
| Delayed | DelayQueue | ||
| Non-blocking | Thread-safe | ConcurrentLinkedQueue | |
| Non thread-safe | LinkedList | ||
| Non thread-safe, priority-based | PriorityQueue |
One further type of queue not included above is the SynchronousQueue, which is effectively a zero-length queue (so that a thread adding an item to the queue will block until another thread removes the item).
其中比较常用的就是：LinkedList和PriorityQueue（优先队列）。