使用循环数组和环形链表实现双端队列
本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。两种实现方式的基本原理和特点，以及详细的Java代码实现和分析。
引言
双端队列(Deque, Double-ended queue)是一种具有队列和栈的性质的数据结构。它允许在两端插入和删除元素，具有较高的灵活性。双端队列在数据结构和算法领域有广泛的应用，如在解决滑动窗口最值问题、实现特定需求的优先队列等场景。本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。以下分别对这两种实现方式进行分析和讲解。
1.基于环形链表的双端队列
环形链表是一种链表的扩展， 其中链表的首尾相连，形成一个环。在实现双端队列时，我们可以使用环形链表来存储元素，这样就可以方便地在表头表尾进行插入和删除操作。
以下是基于环形链表实现双端队列的Java代码：
/**
* 基于环形链表的双端队列
* @param <E> 元素类型
*/
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {
@Override
public 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;
}
@Override
public 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;
}
@Override
public 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;
}
@Override
public 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;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return sentinel.next.value;
}
@Override
public E peekLast() {
if (isEmpty()) {
return null;
}
return sentinel.prev.value;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public 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> {
/*
h
t
0 1 2 3
b a
*/
@Override
public boolean offerFirst(E e) {
if (isFull()) {
return false;
}
head = dec(head, array.length);
array[head] = e;
return true;
}
@Override
public boolean offerLast(E e) {
if (isFull()) {
return false;
}
array[tail] = e;
tail = inc(tail, array.length);
return true;
}
@Override
public E pollFirst() {
if (isEmpty()) {
return null;
}
E e = array[head];
array[head] = null;
head = inc(head, array.length);
return e;
}
@Override
public E pollLast() {
if (isEmpty()) {
return null;
}
tail = dec(tail, array.length);
E e = array[tail];
array[tail] = null;
return e;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return array[head];
}
@Override
public E peekLast() {
if (isEmpty()) {
return null;
}
return array[dec(tail, array.length)];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
if (tail > head) {
return tail - head == array.length - 1;
} else if (tail < head) {
return head - tail == 1;
} else {
return false;
}
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public 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)。此外，相比链表实现的双端队列，循环数组实现的双端队列空间开销较小，占用内存较少。
缺点: 循环数组实现的双端队列存在一定的空间浪费。并且，数组的容量固定，在初始化时就要确定。如果访问量较大，可能导致数组不够用而需要进行扩容操作，这将导致时间复杂度的降低。
结论
本文主要介绍了两种实现双端队列的数据结构：基于环形链表的双端队列和基于循环数组的双端队列。根据不同的应用场景和需求，可以选择合适的数据结构进行实现。环形链表的双端队列适合容量不固定、对时间复杂度要求不高的场景；循环数组的双端队列适合对空间和时间复杂度有较高要求的场景。