双端队列

---

一、什么是双端队列

双端队列（Deque）是指允许两端都可以进行入和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
双端队列（Deque）既可说是Queue的子接口，也可说Stack(JDK并未提供这个接口)的子接口。因此。Deque即可当成队列使用，也可当成栈使用。

由此可见，Deque其实就是Queue和Stack混合而成的一种特殊的线性表，完全可以参考起前面的Queue,Stack的实现类实现Deque。

二、双端队列举例

队头入队：
如果一个排在队头的顾客进了餐厅却发现暂无空桌，则其再次回到队头的行为就相当于从队头入队操作。

队尾出队：
如果一个排在队尾的顾客嫌队伍太长离开了队伍，则其行为就相当于从队尾出队操作。

三、双端队列的应用(三种实现方式)

1.用链表（linkedlist）实现双端队列

用linkedlist创建对象：

private LinkedList<T> deque =new LinkedList<>();
1

队头的插入：

//队头插入数据
	public  void Ladd(T insert) {
		deque.add(insert);
	}
1
2
3
4

队尾的插入：

//队尾插入数据
	public  void Fadd(T insert) {
		deque.add(0,insert);
	}
1
2
3
4

队头的删除：

//删除队头的数据
	public void Fremove() {
		deque.remove(0);
	}
1
2
3
4

队尾的删除：

//删除队尾的数据
	public void Lremove() {
		deque.remove(deque.size()-1);
	}
1
2
3
4

查看数据：

//查看数据
	public LinkedList Search() {
		return deque;
		
	}
1
2
3
4
5

完整代码：

public class Deque<T> {
	private LinkedList<T> deque =new LinkedList<>();
	//队头插入数据
	public  void Ladd(T insert) {
		deque.add(insert);
	}
	//队尾插入数据
	public  void Fadd(T insert) {
		deque.add(0,insert);
	}
	//删除队头的数据
	public void Fremove() {
		deque.remove(0);
	}
	//删除队尾的数据
	public void Lremove() {
		deque.remove(deque.size()-1);
	}
	//查看数据
	public LinkedList Search() {
		return deque;	
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

main方法：

public static void main(String[] args) {
		Deque deque = new Deque();
		deque.Fadd("123");
		deque.Fadd("432");
		deque.Fadd("asd");
		deque.Fadd("544");
		deque.Ladd("0");
		System.out.println(deque.Search());
		deque.Fremove();
		System.out.println(deque.Search());
		deque.Lremove();
		System.out.println(deque.Search());
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

输出结果：

2.用List实现双端队列

参考：
https://jishuin.proginn.com/p/763bfbd5f328

3.用创建链表创建节点Node来实现双端队列

参考：
https://www.jianshu.com/p/1105be94c762