使用循环数组和环形链表实现双端队列

本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。两种实现方式的基本原理和特点，以及详细的Java代码实现和分析。

引言

双端队列(Deque, Double-ended queue)是一种具有队列和栈的性质的数据结构。它允许在两端插入和删除元素，具有较高的灵活性。双端队列在数据结构和算法领域有广泛的应用，如在解决滑动窗口最值问题、实现特定需求的优先队列等场景。本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。以下分别对这两种实现方式进行分析和讲解。

1.基于环形链表的双端队列

环形链表是一种链表的扩展， 其中链表的首尾相连，形成一个环。在实现双端队列时，我们可以使用环形链表来存储元素，这样就可以方便地在表头表尾进行插入和删除操作。

以下是基于环形链表实现双端队列的Java代码：

/*** 基于环形链表的双端队列* @param <E> 元素类型*/
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}size++;Node<E> a = sentinel;Node<E> b = sentinel.next;Node<E> offered = new Node<>(a, e, b);a.next = offered;b.prev = offered;return true;}@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}size++;Node<E> a = sentinel.prev;Node<E> b = sentinel;Node<E> offered = new Node<>(a, e, b);a.next = offered;b.prev = offered;return true;}@Overridepublic E pollFirst() {if (isEmpty()) {return null;}Node<E> a = sentinel;Node<E> polled = sentinel.next;Node<E> b = polled.next;a.next = b;b.prev = a;size--;return polled.value;}@Overridepublic E pollLast() {if (isEmpty()) {return null;}Node<E> polled = sentinel.prev;Node<E> a = polled.prev;Node<E> b = sentinel;a.next = b;b.prev = a;size--;return polled.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;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}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;}}Node<E> sentinel = new Node<>(null, null, null);int capacity;int size;public LinkedListDeque(int capacity) {sentinel.next = sentinel;sentinel.prev = sentinel;this.capacity = capacity;}
}

优点：基于环形链表实现的双端队列具有较好的灵活性，可以实现任意容量大小的双端队列。此外，存储空间会根据实际需求进行动态调整，避免了空间的浪费。

缺点：由于链表结构的特性，相较于数组实现的双端队列，环形链表实现的双端队列空间开销较大。同时，每次访问元素时，都需要遍历链表，导致时间复杂度较高。

2.基于循环数组的双端队列

循环数组是一种线性数据结构，它的逻辑结构和顺序表相似，但在实际存储时将首尾相接，形成一个环状结构。在实现双端队列时，可以使用循环数组来存储元素。当队列的一端进行插入或删除操作时，对应的数组下标只需加一或减一即可。

以下是基于循环数组实现双端队列的Java代码：

/*** 基于循环数组实现, 特点* <ul>*     <li>tail 停下来的位置不存储, 会浪费一个位置</li>* </ul>* @param <E>*/
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {/*ht0   1   2   3b           a*/@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head = dec(head, array.length);array[head] = e;return true;}@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] = e;tail = inc(tail, array.length);return true;}@Overridepublic E pollFirst() {if (isEmpty()) {return null;}E e = array[head];array[head] = null;head = inc(head, array.length);return e;}@Overridepublic E pollLast() {if (isEmpty()) {return null;}tail = dec(tail, array.length);E e = array[tail];array[tail] = null;return e;}@Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}@Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[dec(tail, array.length)];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {if (tail > head) {return tail - head == array.length - 1;} else if (tail < head) {return head - tail == 1;} else {return false;}}@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;}};}E[] array;int head;int tail;@SuppressWarnings("unchecked")public ArrayDeque1(int capacity) {array = (E[]) new Object[capacity + 1];}static int inc(int i, int length) {if (i + 1 >= length) {return 0;}return i + 1;}static int dec(int i, int length) {if (i - 1 < 0) {return length - 1;}return i - 1;}
}

该实现中，为了区分队列为空和队列已满的情况，我们采用了一种方法:浪费一个数组元素。这样，当 tail == head时，队列为空；当 (tail + 1) % array.length == head时，队列已满。

优点: 基于循环数组实现的双端队列具有较好的时间复杂度，访问元素的时间复杂度为O(1)。此外，相比链表实现的双端队列，循环数组实现的双端队列空间开销较小，占用内存较少。

缺点: 循环数组实现的双端队列存在一定的空间浪费。并且，数组的容量固定，在初始化时就要确定。如果访问量较大，可能导致数组不够用而需要进行扩容操作，这将导致时间复杂度的降低。

结论

本文主要介绍了两种实现双端队列的数据结构：基于环形链表的双端队列和基于循环数组的双端队列。根据不同的应用场景和需求，可以选择合适的数据结构进行实现。环形链表的双端队列适合容量不固定、对时间复杂度要求不高的场景；循环数组的双端队列适合对空间和时间复杂度有较高要求的场景。