java数据结构--双端队列

一.概念

双端队列的意思是可以在头部和尾部添加和删除元素，更一般的单向链表队列比起来更加的灵活，下面我们用双向循环带哨兵链表和数组来分别实现

二.定义接口Dequeue

/*** 双端队列*/
public interface Dequeue<E> {//队头添加元素boolean offerTop(E e);//队尾添加元素boolean offerTail(E e);//队头取元素并删除该元素E pollTop();//队尾取元素并删除该元素E pollTail();//队头取元素E peekTop();//队尾取元素E peekTail();//是否为空boolean isEmpty();//是否为满boolean isFull();}

三.双向循环带哨兵链表链表实现

1.图示

（1）向队头添加节点

（2）向队尾添加节点

对于移除节点，和上面的类似，代码注释中也都做了解释，这里就不在展示了。

2.代码实现

/*** 双向链表实现双端队列* @param <E>*/
public class LinkedDequeue<E> implements Dequeue<E> ,Iterable<E>{//内部节点类static class Node<E>{Node<E> pre;E value;Node<E> next;public Node(Node<E> pre,E value,Node<E> next){this.pre = pre;this.value = value;this.next = next;}}//容量int capacity;//队列中元素的个数int size;//哨兵Node<E> sentinel = new Node<>(null,null,null);//初始化public LinkedDequeue(int capacity){//初始化容量this.capacity = capacity;//开始时哨兵的下一个节点是本身sentinel.next = sentinel;//上一个节点也是本身sentinel.pre = sentinel;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {//获取第一个元素Node<E> p = sentinel.next;@Overridepublic boolean hasNext() {//如果p==sentinel就说明遍历完成了，没有下一个了return p != sentinel;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}/*** 向头部添加节点*  a  -> added ->  b*     <-       <-*  a是哨兵， b是哨兵的下一个节点* @param e* @return*/@Overridepublic boolean offerTop(E e) {if(isFull()){return  false;}Node<E> a = sentinel;Node<E> b = sentinel.next;Node<E> added = new Node<>(a,e,b);a.next = added;b.pre = added;size++;return true;}/*** 向尾部添加节点*a    -> added ->  b*       <-       <-* a是哨兵的上一个，b是哨兵** @param e* @return*/@Overridepublic boolean offerTail(E e) {if(isFull()){return false;}Node<E> b = sentinel;Node<E> a = sentinel.pre;Node<E> added = new Node<>(a,e,b);a.next = added;b.pre = added;size++;return true;}/*** 将头部节点移除* @return 头部元素的值** a removed b* a是哨兵，removed是哨兵的下一个，b是removed的下一个* a -> b*   <-*/@Overridepublic E pollTop() {if(isEmpty()){return null;}Node<E> a = sentinel;Node<E> removed = sentinel.next;Node<E> b = removed.next;a.next = b;b.pre = a;size--;return removed.value;}/*** 将尾部节点移除* @return 尾部元素的值** a removed b* b是哨兵，removed是b的上一个，a是removed的上一个* a -> b*   <-*/@Overridepublic E pollTail() {if(isEmpty()){return null;}Node<E> b = sentinel;Node<E> removed = sentinel.pre;Node<E> a = removed.pre;a.next = b;b.pre = a;size--;return removed.value;}/*** 获取第一个元素的值，但是不移除* @return*/@Overridepublic E peekTop() {if(isEmpty()){return null;}return sentinel.next.value;}/*** 获取最后一个元素的值，但是不移除* @return*/@Overridepublic E peekTail() {if(isEmpty()){return null;}return sentinel.pre.value;}@Overridepublic boolean isEmpty() {return  size == 0;}@Overridepublic boolean isFull() {return  size == capacity;}
}

四.数组带头尾指针实现

1.图示

（1）刚开始时head和tail都在同一位置，表示空

当在尾部tail添加元素时，先在tail处添加元素，然后让tail加一,

注意:这里的加一不是直接tail++,因为是循环队列，所以若到了array.length处，也就是末尾，下一次加一就要跑到索引0的位置了，一般我们之前是用的求余数运算来找到合法的索引位置，但是我们这里会用一个新的方式来运算索引

（2）tail处添加元素

（3）head处添加元素

我们在head处添加元素时，我们是让head先减一，然后再在head处添加，为啥呢？因为我们是循环数组，让head减一，相当于改变了头的位置，好像是在向左移动一样，向左扩展，

注意：这里的减一也是要算出合法的索引，而且如果head本来是在索引0处，那么head就要移动到array.length处，这样就好像是在向前移动

对于头部尾部移除元素，都是类似的，在此不过多描述。

（4）代码实现

/*** 数组实现双端队列* @param <E>*/
public class ArrayDequeue<E> implements Dequeue<E>,Iterable<E>{E array[];//头指针int head;//尾指针int tail;@SuppressWarnings("all")public ArrayDequeue(int capacity){//实际容量要多空出一个来判断空满array = (E[]) new Object[capacity+1];}//加一方法public static int inc(int i,int length){if(i + 1 >= length){return 0;}return i + 1;}//减一方法public static int dec(int i,int length){if(i - 1 < 0){return  length - 1;}return i - 1;}/*** 头部添加元素** 先让head--,然后再在head处添加元素** @param e* @return*/@Overridepublic boolean offerTop(E e) {if(isFull()){return false;}head = dec(head,array.length);array[head] = e;return true;}/*** 在尾部添加依赖** 先在tail处添加元素，然后让tail++* @param e* @return*/@Overridepublic boolean offerTail(E e) {if(isFull()){return false;}array[tail] = e;tail = inc(tail,array.length);return true;}/*** 移除队头元素** 先获取head处元素，然后让head++** @return*/@Overridepublic E pollTop() {if(isEmpty()){return null;}E  e  =  array[head];array[head] = null; //help GChead = inc(head,array.length);return e;}/*** 移除队尾元素** 先让tail--，然后返回tail处的值** @return*/@Overridepublic E pollTail() {if(isEmpty()){return null;}tail = dec(tail,array.length);E e = array[tail];array[tail] = null; //help GCreturn e;}@Overridepublic E peekTop() {if(isEmpty()){return null;}return array[head];}@Overridepublic E peekTail() {if(isEmpty()){return null;}return array[dec(tail, array.length)];}/*** 判断是否为空* @return*/@Overridepublic boolean isEmpty() {return  head == tail;}/*** 判断是否为满* @return*/@Overridepublic boolean isFull() {//当 head > tail 时，/*** 需要判断 head - tail == 1*//*** 当 tail > head 时* 需要判断 tail - head == array.length - 1;*/if(head > tail){return head - tail == 1;}else if( head < tail){return  tail - head == array.length - 1;}else{return false;}}/*** 遍历* @return*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p = head;@Overridepublic boolean hasNext() {return p != tail;}@Overridepublic E next() {E e = array[p];p = inc(p,array.length);return e;}};}
}