1、双端队列（Deque）

双端队列是在头尾两端都能添加和删除元素的队列。即：

它可以在队头添加元素，也可以在队尾添加元素。
它可以在队头删除元素，也可以在队尾删除元素。

双端队列

注：Deque是double ended queue的简称。

2、双端队列的设计

与队列类似，由于双端队列也是频繁地在队头和队尾添加或删除元素，因此我们也优先使用双向链表来实现双端队列。具体分析过程参见队列，这里不再赘述。

（1）类的结构设计

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

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

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

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

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

接口函数。

（2）接口设计

int size(); //元素的数量
boolean isEmpty(); //是否为空
void enQueueRear (E element); //从队尾入队
E deQueueFront (); //从队头出队
void enQueueFront (E element); //从队头入队
E deQueueRear (); //从队尾出队
E front(); //获取队列的头元素
E rear(); //获取队列的尾元素
void clear(); //清空队内元素

3、双端队列的实现

3.1、编程实现

在队列项目的基础上：

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

②仍然使用名称为Main（包名为：com.atangbiji）的类，来调用（测试）自己封装的双端队列。

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

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

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

（1）定义私有成员变量

Deque.java文件：

package com.atangbiji;

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

（2）实现size()接口

Deque.java文件：

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

（3）实现isEmpty()接口

Deque.java文件：

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

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

Deque.java文件：

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

（5）实现deQueueFront()接口

Deque.java文件：

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

（6）实现enQueueFront (E element)接口

Deque.java文件：

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

（7）实现deQueueRear()接口

Deque.java文件：

/*
 * 从队尾出队
 * @param
 * @return 
 * */
public E deQueueRear() {
	// 从队尾出队, 即：将列表中尾元素删除并返回
	return list.remove(list.size() - 1);
}

（8）实现front()接口

Deque.java文件：

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

（9）实现rear()接口

Deque.java文件：

/*
 * 获取队列的尾元素
 * @param
 * @return 
 * */
public E rear() {
	// 获取队列的尾元素, 就是获取列表中的尾元素
	return list.get(list.size() - 1);
}

（10）现clear()接口

Deque.java文件：

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

3.2、接口测试

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

Main.java文件：

package com.atangbiji;

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