1、队列（Queue）

队列是一种特殊的线性表，它只能在头尾两端进行操作。

元素出入特点：
- 它只能在队尾入队（添加元素）；
- 它只能在队头出队（删除元素）。
元素出入原则：先进先出。

2、顺序队列与链式队列

仔细观察可以发现，如果我们把队列内部元素按照入队的先后顺序依次存储在前面学习过的动态数组或链表中，那么元素的入队操作完全等价于在动态数组或链表的尾部添加元素，元素的出队操作完全等价于在动态数组或链表的头部删除元素。因此，我们可以直接利用动态数组或（双向）链表来实现队列。

**注：**如果频繁在头部进行添加、删除操作，建议使用双向链表。此时，动态数组的时间复杂度为O(n)，双向链表的时间复杂度为O(1)。

基于数组实现的队列是顺序队列，基于链表实现的队列为链式队列。
由于队列需要频繁地在尾部添加元素和头部删除元素，因此我们优先使用双向链表来实现队列。

3、链式队列的设计

（1）类的结构设计

在编程之前，我们需要先对队列类（Queue）的结构进行设计。因为我们是直接利用双向链表来实现队列，所以我们可以通过“组合”的方式来实现队列。即：将双向链表类的对象定义成Queue类的私有成员变量。

**注：**我们之所以没采用“继承”（即：让Queue类直接继承双向链表类）的方式来实现队列，是因为如果Queue类直接继承双向链表类，那么它在继承双向链表特性的同时也会继承它的其他接口，从而破坏了Queue类封装的接口。

因此，队列类需要的成员主要包括：

私有成员变量：双向链表类的对象。

1	private DoubleLinkedList<E> list = new DoubleLinkedList<E>();

接口函数。

（2）接口设计

int size(); //元素的数量
boolean isEmpty(); //是否为空
void enQueue (E element); //入队
E deQueue (); //出队
E front(); //获取队列的头元素
void clear(); //清空队内元素

4、链式队列的实现

4.1、编程实现

新建一个项目，在其中：

①先新建一个名称为Queue（包名为：com.atangbiji）的类，用来自己实现队列；

②再新建一个名称为Main（包名为：com.atangbiji）的类，用来调用（测试）自己封装的队列。

③将前面章节中封装好的双向链表类拷贝到该项目的com.atangbiji包中，供Queue类调用，如下图所示。

**注：**其实Java中已经为我们封装好了Queue类。当我们调用Queue时会提示有两个Queue类。为了测试自己写的数据结构，此时我们应该选择包名为com.atangbiji的那个。

④接口实现，我们这里直接考虑队列内部元素均为泛型的情况。

（1）定义私有成员变量

Queue.java文件：

package com.atangbiji;

public class Queue<E> {	
	 //使用双向链表来实现队列
	 private DoubleLinkedList<E> list = new DoubleLinkedList<E>();	 
}

（2）实现size()接口

Queue.java文件：

/*
 * 元素的数量
 * @param
 * @return 
 * */
public int size() {
	// 队列中元素数量, 就是列表中存储的元素数量
	return list.size();
}

（3）实现isEmpty()接口

Queue.java文件：

/*
 * 是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	// 队列是否空, 就是列表是否空
	return list.isEmpty();
}

（4）实现enQueue(E element)接口

Queue.java文件：

/*
 * 入队
 * @param
 * @return 
 * */
public void enQueue(E element) {
	// 入队, 即：将元素添加到列表的最后面
	list.add(element);
}

（5）实现deQueue()接口

Queue.java文件：

/*
 * 出队
 * @param
 * @return 
 * */
public E deQueue() {
	// 出队, 即：将列表中头元素删除并返回
	return list.remove(0);
}

（6）实现front()接口

Queue.java文件：

/*
 * 获取队列的头元素
 * @param
 * @return 
 * */
public E front() {
	// 获取队列的头元素, 就是获取列表中的头元素
	return list.get(0);
}

（7）实现clear ()接口

Queue.java文件：

/*
 * 清空队内元素
 * @param
 * @return 
 * */
public void clear() {
	// 清空队列, 就是清空列表
	list.clear();
}

4.2、接口测试

在Main类（Main.java文件）中新建一个Queue对象，用来测试自己封装的队列。这里仅以入队和出队接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		Queue<Integer> queue = new Queue<Integer>();
		queue.enQueue(11);
		queue.enQueue(22);
		queue.enQueue(33);
		queue.enQueue(44);
		queue.enQueue(55);
		
		//若队列不为空，则让队头元素出队。直到队列为空为止。
		while (!queue.isEmpty()) {
			System.out.println(queue.deQueue());
		}

	}
}