2.6 雙端隊列
概述
雙端隊列、隊列、棧對比
| 定義 | 特點 | |
|---|---|---|
| 隊列 | 一端刪除（頭）另一端添加（尾） | First In First Out |
| 棧 | 一端刪除和添加（頂） | Last In First Out |
| 雙端隊列 | 兩端都可以刪除、添加 | |
| 優(yōu)先級隊列 | 優(yōu)先級高者先出隊 | |
| 延時隊列 | 根據(jù)延時時間確定優(yōu)先級 | |
| 并發(fā)非阻塞隊列 | 隊列空或滿時不阻塞 | |
| 并發(fā)阻塞隊列 | 隊列空時刪除阻塞、隊列滿時添加阻塞 |
注1：
- Java 中 LinkedList 即為典型雙端隊列實現(xiàn)，不過它同時實現(xiàn)了 Queue 接口，也提供了棧的 push pop 等方法
注2：
不同語言，操作雙端隊列的方法命名有所不同，參見下表
操作 Java JavaScript C++ leetCode 641 尾部插入 offerLast push push_back insertLast 頭部插入 offerFirst unshift push_front insertFront 尾部移除 pollLast pop pop_back deleteLast 頭部移除 pollFirst shift pop_front deleteFront 尾部獲取 peekLast at(-1) back getRear 頭部獲取 peekFirst at(0) front getFront 吐槽一下 leetCode 命名比較 low
常見的單詞還有 enqueue 入隊、dequeue 出隊
接口定義
public interface Deque<E> {
boolean offerFirst(E e);
boolean offerLast(E e);
E pollFirst();
E pollLast();
E peekFirst();
E peekLast();
boolean isEmpty();
boolean isFull();
}
鏈表實現(xiàn)
/**
* 基于環(huán)形鏈表的雙端隊列
* @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;
}
}
數(shù)組實現(xiàn)
/**
* 基于循環(huán)數(shù)組實現(xiàn), 特點
* <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;
}
}
數(shù)組實現(xiàn)中，如果存儲的是基本類型，那么無需考慮內(nèi)存釋放，例如
image.png
但如果存儲的是引用類型，應當設置該位置的引用為 null，以便內(nèi)存及時釋放
image.png
