双向队列

在队列中，我们仅能删除头部元素或在尾部添加元素。如下图所示，双向队列（double-ended queue）提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

双向队列常用操作

双向队列的常用操作如下表（双向队列操作效率）所示，具体的方法名称需要根据所使用的编程语言来确定。

方法名	描述	时间复杂度
push_first()	将元素添加至队首	𝑂(1)
push_last()	将元素添加至队尾	𝑂(1)
pop_first()	删除队首元素	𝑂(1)
pop_last()	删除队尾元素	𝑂(1)
peek_first()	访问队首元素	𝑂(1)
peek_last()	访问队尾元素	𝑂(1)

同样地，我们可以直接使用编程语言中已实现的双向队列类：

/* 初始化双向队列 */
Deque<Integer> deque = new LinkedList<>();

/* 元素入队 */
deque.offerLast(2);   // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // 添加至队首
deque.offerFirst(1);

/* 访问元素 */
int peekFirst = deque.peekFirst();  // 队首元素
int peekLast = deque.peekLast();    // 队尾元素

/* 元素出队 */
int popFirst = deque.pollFirst();  // 队首元素出队
int popLast = deque.pollLast();    // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
boolean isEmpty = deque.isEmpty();

双向队列实现

双向队列的实现与队列类似，可以选择链表或数组作为底层数据结构。

基于双向链表的实现

回顾上一节内容，我们使用普通单向链表来实现队列，因为它可以方便地删除头节点（对应出队操作）和在尾节点后添加新节点（对应入队操作）。

对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，我们采用“双向链表”作为双向队列的底层数据结构。

如下图所示，我们将双向链表的头节点和尾节点视为双向队列的队首和队尾，同时实现在两端添加和删除节点的功能。

实现代码如下所示：

代码实现

public class LinkedListDeque<E> {
  /**
   * 队列的长度
   */
  private int size = 0;
  /**
   * 头节点
   */
  private ListNode<E> front;
  /**
   * 尾节点
   */
  private ListNode<E> rear;

  /**
   * 获取队列的长度
   *
   * @return 队列的长度
   */
  public int size() {
    return size;
  }

  /**
   * 判断队列是否为空
   *
   * @return true 队列为空，false 队列不为空
   */
  public boolean isEmpty() {
    return size() == 0;
  }

  /**
   * 队首入队操作
   *
   * @param e 入队元素
   */
  public void pushFirst(final E e) {
    push(e, true);
  }

  /**
   * 队尾入队操作
   *
   * @param e 入队元素
   */
  public void pushLast(final E e) {
    push(e, false);
  }

  /**
   * 队首出队操作
   *
   * @return 队首元素
   */
  public E popFirst() {
    return pop(true);
  }

  /**
   * 队尾出队操作
   *
   * @return 队尾元素
   */
  public E popLast() {
    return pop(false);
  }

  /**
   * 获取队首元素
   *
   * @return 队首元素
   */
  public E peekFirst() {
    if (isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    return front.value;
  }

  /**
   * 获取队尾元素
   *
   * @return 队尾元素
   */
  public E peekLast() {
    if (isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    return rear.value;
  }

  /**
   * 将队列中的元素转化为数组
   *
   * @return 队列中的元素组成的数组
   */
  public Object[] toArray() {
    ListNode<E> curr = front;
    Object[] res = new Object[size()];
    for (int i = 0; i < size(); i++) {
      res[i] = curr.value;
      curr = curr.next;
    }
    return res;
  }

  /**
   * 出队操作
   *
   * @param isFront 出队位置，true 队首，false 队尾
   * @return 出队元素
   */
  private E pop(final boolean isFront) {
    if (isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    E value;
    if (isFront) {
      // 队首出队操作
      // 保存队首元素的值
      value = front.value;
      // 获取队首节点的后继节点
      ListNode<E> next = front.next;
      if (next != null) {
        // 将后继节点的前驱节点指向null，让队首节点与链表断开
        next.prev = null;
      }
      // 更新头节点，让其指向后继节点
      front = next;
    } else {
      // 队尾出队操作
      // 保存队尾元素的值
      value = rear.value;
      // 获取队尾节点的前驱节点
      ListNode<E> prev = rear.prev;
      if (prev != null) {
        // 将前驱节点的后继节点指向null，让其与链表断开
        prev.next = null;
      }
      // 更新尾节点，让其指向前驱节点
      rear = prev;
    }
    // 队列长度减1
    size--;
    return value;
  }

  /**
   * 入队操作
   *
   * @param e       入队元素
   * @param isFront 入队位置，true 队首，false 队尾
   */
  private void push(final E e, final boolean isFront) {
    // 创建新节点
    ListNode<E> newNode = new ListNode<>(e);
    // 如果队列为空，则头节点和尾节点都指向新节点
    if (isEmpty()) {
      front = rear = newNode;
    } else if (isFront) {
      // 队首入队操作，将新节点添加到链表的头部
      // 头节点的前驱节点指向新节点
      front.prev = newNode;
      // 新节点的后继节点指向头节点
      newNode.next = front;
      // 更新头节点，让其指向新节点
      front = newNode;
    } else {
      // 队尾入队操作，将新节点添加到链表的尾部
      // 尾节点的后继节点指向新节点
      rear.next = newNode;
      // 新节点的前驱节点指向尾节点
      newNode.prev = rear;
      // 更新尾节点，让其指向新节点
      rear = newNode;
    }
    // 队列长度加1
    size++;
  }

  private static class ListNode<E> {
    /**
     * 节点值
     */
    E value;
    /**
     * 前驱节点
     */
    ListNode<E> prev;
    /**
     * 后继节点
     */
    ListNode<E> next;

    /**
     * 构造函数
     *
     * @param value 节点值
     */
    public ListNode(final E value) {
      this.value = value;
    }
  }
}

测试

class LinkedListDequeTest {
  @Test
  public void test() {
    LinkedListDeque<Integer> deque = new LinkedListDeque<>();
    deque.pushLast(2);
    deque.pushLast(5);
    deque.pushFirst(3);
    deque.pushLast(4);
    deque.pushFirst(1);
    Assertions.assertArrayEquals(new Integer[]{1, 3, 2, 5, 4}, deque.toArray());
    Assertions.assertEquals(1, deque.peekFirst());
    Assertions.assertEquals(4, deque.peekLast());
    Assertions.assertEquals(1, deque.popFirst()); // 3, 2, 5, 4
    Assertions.assertEquals(4, deque.popLast()); // 3, 2, 5
    Assertions.assertEquals(3, deque.size());
    Assertions.assertEquals(3, deque.popFirst()); // 2, 5
    Assertions.assertEquals(2, deque.popFirst()); // 5
    Assertions.assertEquals(5, deque.popLast());
    Assertions.assertTrue(deque.isEmpty());
  }
}

基于数组的实现

如下图所示，与基于数组实现队列类似，我们也可以使用环形数组来实现双向队列。

在队列的实现基础上，仅需增加“队首入队”和“队尾出队”的方法：

代码实现

public class ArrayDeque<E> {
  /**
   * 用于存储队列元素的数组
   */
  private final Object[] elementData;
  /**
   * 队列的长度
   */
  private int size;
  /**
   * 队头指针，指向队首元素
   */
  private int front;

  public ArrayDeque() {
    this(10);
  }

  public ArrayDeque(int capacity) {
    this.elementData = new Object[capacity];
    front = size = 0;
  }

  /**
   * 获取队列的容量
   *
   * @return 队列的容量
   */
  public int capacity() {
    return elementData.length;
  }

  /**
   * 获取队列的长度
   *
   * @return 队列的长度
   */
  public int size() {
    return size;
  }

  /**
   * 判断队列是否为空
   *
   * @return true：队列为空；false：队列不为空
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * 队首入队操作
   *
   * @param e 入队元素
   */
  public void pushFirst(final E e) {
    if (size() == capacity()) {
      throw new IllegalStateException("队列已满");
    }
    // 队首指针向左移动一位
    // 通过取余操作实现 front 越过数组头部后回到尾部
    front = index(front - 1);
    // 将元素添加至队首
    elementData[front] = e;
    // 队列长度加1
    size++;
  }

  /**
   * 队尾入队操作
   *
   * @param e 入队元素
   */
  public void pushLast(final E e) {
    if (size() == capacity()) {
      throw new IllegalStateException("队列已满");
    }
    // 计算队尾指针，指向队尾元素的下一个位置
    // 通过取余操作实现 rear 越过数组尾部后回到头部
    int rear = index(front + size);
    // 将元素添加至队尾
    elementData[rear] = e;
    // 队列长度加1
    size++;
  }

  /**
   * 队首出队操作
   *
   * @return 队首元素
   */
  public E popFirst() {
    // 获取队首元素
    E e = peekFirst();
    // 队首指针向右移动一位
    front = index(front + 1);
    // 队列长度减1
    size--;
    return e;
  }

  /**
   * 队尾出队操作
   *
   * @return 队尾元素
   */
  public E popLast() {
    // 获取队尾元素
    E e = peekLast();
    // 队列长度减1
    size--;
    return e;
  }

  /**
   * 获取队首元素
   *
   * @return 队首元素
   */
  public E peekFirst() {
    if (isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    return elementData(front);
  }

  /**
   * 获取队尾元素
   *
   * @return 队尾元素
   */
  public E peekLast() {
    if (isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    // 计算尾元素索引
    int last = index(front + size - 1);
    return elementData(last);
  }

  /**
   * 将队列中的元素转化为数组
   *
   * @return 队列中的元素组成的数组
   */
  public Object[] toArray() {
    // 仅转换有效长度范围内的列表元素
    Object[] res = new Object[size];
    // 将有效长度范围内的元素复制到新数组中
    for (int i = 0, j = front; i < size; i++, j++) {
      res[i] = elementData(index(j));
    }
    return res;
  }

  @SuppressWarnings("unchecked")
  E elementData(int index) {
    return (E) elementData[index];
  }

  private int index(int index) {
    // 通过取余操作实现数组首尾相连
    // 当 index 越过数组尾部后，回到头部
    // 当 index 越过数组头部后，回到尾部
    return (index + capacity()) % capacity();
  }
}

测试

class ArrayDequeTest {
  @Test
  public void test() {
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    deque.pushLast(2);
    deque.pushLast(5);
    deque.pushFirst(3);
    deque.pushLast(4);
    deque.pushFirst(1);
    Assertions.assertArrayEquals(new Integer[]{1, 3, 2, 5, 4}, deque.toArray());
    Assertions.assertEquals(1, deque.peekFirst());
    Assertions.assertEquals(4, deque.peekLast());
    Assertions.assertEquals(1, deque.popFirst()); // 3, 2, 5, 4
    Assertions.assertEquals(4, deque.popLast()); // 3, 2, 5
    Assertions.assertEquals(3, deque.size());
    Assertions.assertEquals(3, deque.popFirst()); // 2, 5
    Assertions.assertEquals(2, deque.popFirst()); // 5
    Assertions.assertEquals(5, deque.popLast());
    Assertions.assertTrue(deque.isEmpty());
  }
}

双向队列应用

双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。

我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过 50 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。