【数据结构与算法】(7)基础数据结构之双端队列的链表实现、环形数组实现示例讲解

2.6 双端队列

1) 概述

双端队列、队列、栈对比

	定义	特点
队列	一端删除（头）另一端添加（尾）	First In First Out
栈	一端删除和添加（顶）	Last In First Out
双端队列	两端都可以删除、添加
优先级队列		优先级高者先出队
延时队列		根据延时时间确定优先级
并发非阻塞队列	队列空或满时不阻塞
并发阻塞队列	队列空时删除阻塞、队列满时添加阻塞

注1：

• Java 中 LinkedList 即为典型双端队列实现，不过它同时实现了 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();
}

2) 链表实现

/*** 基于环形链表的双端队列* @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;}
}

3) 数组实现

/*** 基于循环数组实现, 特点* <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;}
}

数组实现中，如果存储的是基本类型，那么无需考虑内存释放，例如

但如果存储的是引用类型，应当设置该位置的引用为 null，以便内存及时释放

习题

E01. 二叉树 Z 字层序遍历-Leetcode 103

public class E01Leetcode103 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}LinkedList<TreeNode> queue = new LinkedList<>();queue.offer(root);boolean leftToRight = true;int c1 = 1;while (!queue.isEmpty()) {int c2 = 0;LinkedList<Integer> deque = new LinkedList<>();for (int i = 0; i < c1; i++) {TreeNode n = queue.poll();if (leftToRight) {deque.offerLast(n.val);} else {deque.offerFirst(n.val);}if (n.left != null) {queue.offer(n.left);c2++;}if (n.right != null) {queue.offer(n.right);c2++;}}c1 = c2;leftToRight = !leftToRight;result.add(deque);}return result;}public static void main(String[] args) {TreeNode root = new TreeNode(new TreeNode(new TreeNode(4),2,new TreeNode(5)),1,new TreeNode(new TreeNode(6),3,new TreeNode(7)));List<List<Integer>> lists = new E01Leetcode103().zigzagLevelOrder(root);for (List<Integer> list : lists) {System.out.println(list);}}
}