如何实现一个双端队列
零双端队列性质
见名知意，就是可以在队首、队尾分别执行入队、出队操作的一种队列。
一实现思路
参照用数组实现队列的思路，我们就完全可以实现一个双端队列。因为，我们底层的动态数组已经实现了addFirst()/addLast()，removeFirst()/removeLast()，getFirst()/getLast()的方法。因此，我们双端队列如果需要在队首、队尾分别出队，入队的操作，我们只需要调用底层数据的对应方法就可以。另外，查看队首、队尾元素值，我们调用底层数组的getFirst()/getLast()方法即可。
二代码实现
/**
* @Author:asher
* @Date:2021/4/12 14:41
* @Description:PACKAGE_NAME
* @Version:1.0
*/
public class Deque<E> implements Queue<E> {
private Array<E> array;
public Deque(int capacity) {
array = new Array<>(capacity);
}
public Deque() {
this(10);
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
//队首入队，双端队列新添加的方法
public void enqueueFirst(E e) {
array.addFirst(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
//队尾出队，双端队列新加的方法
public E dequeueLast() {
return array.removeLast();
}
@Override
public E getFront() {
return array.getFirst();
}
//查看队尾元素，双端队列新加的
public E getLast() {
return array.getLast();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Dequeue size: %d , length: %d\n", array.getSize(),array.getCapacity()));
stringBuilder.append("Dequeue: head[");
for (int i = 0; i < getSize(); i++) {
stringBuilder.append(array.get(i));
if (i != getSize()-1) {
stringBuilder.append(" , ");
}
}
stringBuilder.append("] tail");
return stringBuilder.toString();
}
public static void main(String[] args) {
Deque deque=new Deque(5);
System.out.println(deque);
//队尾入队元素2
deque.enqueue(2);
System.out.println(deque);
//队首入队元素1
deque.enqueueFirst(1);
System.out.println(deque);
//队首继续入队元素0
deque.enqueueFirst(0);
//队尾入队元素3
deque.enqueue(3);
System.out.println(deque);
//队首出队
System.out.println(deque.dequeue());
System.out.println(deque);
//队尾出队
System.out.println(deque.dequeueLast());
System.out.println(deque);
}
}
//结果：
Dequeue size: 0 , length: 5
Dequeue: head[] tail
Dequeue size: 1 , length: 5
Dequeue: head[2] tail
Dequeue size: 2 , length: 5
Dequeue: head[1 , 2] tail
Dequeue size: 4 , length: 5
Dequeue: head[0 , 1 , 2 , 3] tail
0
Dequeue size: 3 , length: 5
Dequeue: head[1 , 2 , 3] tail
3
Dequeue size: 2 , length: 2
Dequeue: head[1 , 2] tail说明：这个Dequeue的类，使我们自己通过动态数组实现的一个双端队列。JDK自带也有一个Deque接口。同时，我们的Dequeue也同样实现了前面我们自己定义的Queue那个接口。并且，添加了自己固有的在队尾出队dequeueLast()、队首添加元素的方法enqueueFirst()。
