目录

基于链表实现:基于双向环形链表的双端队列

基于数组实现:循环数组

分析:

---

基于链表实现:基于双向环形链表的双端队列

package LinkedListDeque;
//基于双向环形链表的双端队列import org.w3c.dom.Node;import java.util.Iterator;public class LinkedListDeque<E> implements Qeque<E>, Iterable<E> {//节点类static class Node<E>{Node<E> prev;E value;Node<E> next;public Node(Node<E> prev, E value, Node<E> next){this.prev=prev;this.value=value;this.next=next;}}int capacity;int size;Node <E> sentinel=new Node<>(null,null,null);public LinkedListDeque(int capacity){this.capacity=capacity;sentinel.next=sentinel;sentinel.prev=sentinel;}//向队列头部添加元素  a added b@Overridepublic boolean offerFirst(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.prev=added;size++;return true;}//向队列尾部添加元素 a added b@Overridepublic boolean offerLast(E e) {if(isFull()){return false;}Node<E> a=sentinel.prev;Node<E> b = sentinel;Node<E> added = new Node(a, e, b);a.next = added;b.prev=added;size++;return true;}@Overridepublic E pollFirst() {if(isEmpty()){return null;}Node<E> a=sentinel;Node<E> first=sentinel.next;Node<E> b=first.next;a.next=b;b.prev=a;size--;return first.value;}@Overridepublic E pollLast() {if(isEmpty()){return null;}Node<E> b=sentinel;Node<E> last=sentinel.prev;Node<E> a=last.prev;a.next=b;b.prev=a;size--;return last.value;}@Overridepublic E peekFirst() {if(isEmpty()){return null;}return sentinel.next.value;}@Overridepublic E peekLast() {if(isEmpty()){return null;}return sentinel.prev.value;}//判断队列是否为空@Overridepublic boolean isEmpty() {return size==0;}//判断队列是否已满@Overridepublic boolean isFull() {return size==capacity;}//迭代器@Overridepublic Iterator<E> iterator() {return new Iterator<E>(){Node<E> p=sentinel.next;public boolean hasNext(){return p!=sentinel;}public E next(){E value=p.value;p=p.next;return value;}};}
}

基于数组实现:循环数组

分析:

  /** h head* t tail      h* 0  1  2  3  4  5* a  b  t     d  c* offerLast  先添加元素在tail++* offerFirst  先head--,再添加元素*
//    head==tail 表示空// head==(tail+1)%size 表示满** pollFirst()  先获取值,再head++* pollLast() 先tail--,再获取值*/

package ArrayDeque;import java.util.Iterator;
//循环数组public class ArrayDeque1<E> implements Qeque<E>, Iterable<E> {private int head,tail;private E[] array;public ArrayDeque1(int capacity) {array= (E[]) new Object[capacity+1];//空与满不一样      }@Overridepublic boolean offerFirst(E e) {if(isFull()){return false;}head=(head-1+array.length)%array.length;array[head]=e;return true;}@Overridepublic boolean offerLast(E e) {if(isFull()){return false;}array[tail]=e;tail=(tail+1)%array.length;return true;}@Overridepublic E pollFirst() {if(isEmpty()){return null;}E value=array[head];head=(head+1)%array.length;return value;}@Overridepublic E pollLast() {if(isEmpty()){return null;}tail=(tail-1+array.length)%array.length;return array[tail];}@Overridepublic E peekFirst() {if(isEmpty()){return null;}return array[head];}@Overridepublic E peekLast() {if(isEmpty()){return null;}int index=(tail-1+array.length)%array.length;return array[index];}@Overridepublic boolean isEmpty() {return head==tail;}@Overridepublic boolean isFull() {return head==(tail+1)%array.length;}@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=(p+1)%array.length;return e;}};}
}