3. 什么是双端队列（Deque）？如何在Java中实现一个双端队列？

什么是双端队列（Deque）？

双端队列（Deque） 是一种允许在队列的两端进行插入和删除操作的队列。Deque 是 "double-ended queue" 的缩写，具有队列和栈的特性，既可以像队列那样从一端入队，从另一端出队，也可以像栈那样从同一端进行入栈和出栈操作。

Deque 提供了如下操作：

• 从前端插入元素（addFirst）
• 从后端插入元素（addLast）
• 从前端删除元素（removeFirst）
• 从后端删除元素（removeLast）
• 查看前端元素（peekFirst）
• 查看后端元素（peekLast）

如何在Java中实现一个双端队列？

在 Java 中，可以通过数组和链表分别实现一个双端队列。以下是这两种实现方法。

一、使用数组实现双端队列

1. 基本思路

使用循环数组来实现双端队列。需要两个指针 front 和 rear 分别指向队列的前端和后端，数组的容量为 capacity。为了区分队列的空和满状态，可以保留一个位置不使用。

2. 具体实现

public class ArrayDeque {
    private int[] deque;
    private int front;
    private int rear;
    private int size;
    private int capacity;

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

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void addFirst(int element) {
        if (isFull()) {
            throw new RuntimeException("Deque is full");
        }
        front = (front - 1 + capacity) % capacity;
        deque[front] = element;
        size++;
    }

    public void addLast(int element) {
        if (isFull()) {
            throw new RuntimeException("Deque is full");
        }
        deque[rear] = element;
        rear = (rear + 1) % capacity;
        size++;
    }

    public int removeFirst() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        int element = deque[front];
        front = (front + 1) % capacity;
        size--;
        return element;
    }

    public int removeLast() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        rear = (rear - 1 + capacity) % capacity;
        int element = deque[rear];
        size--;
        return element;
    }

    public int peekFirst() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        return deque[front];
    }

    public int peekLast() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        return deque[(rear - 1 + capacity) % capacity];
    }

    public static void main(String[] args) {
        ArrayDeque deque = new ArrayDeque(5);

        deque.addLast(1);
        deque.addLast(2);
        deque.addFirst(3);
        System.out.println("First element: " + deque.peekFirst());
        System.out.println("Last element: " + deque.peekLast());
        System.out.println("Removed first: " + deque.removeFirst());
        System.out.println("Removed last: " + deque.removeLast());
    }
}

3. 时间复杂度

• 插入（addFirst, addLast）：O(1)，只需更新指针并插入元素。
• 删除（removeFirst, removeLast）：O(1)，只需更新指针并删除元素。
• 查看（peekFirst, peekLast）：O(1)，只需访问数组中的对应位置。

二、使用链表实现双端队列

1. 基本思路

使用双向链表来实现双端队列。链表中的每个节点包含一个数据项，以及指向前一个节点和后一个节点的指针。通过维护 front 和 rear 两个指针，可以在两端进行插入和删除操作。

2. 具体实现

public class LinkedListDeque {

    private static class Node {
        int data;
        Node prev;
        Node next;

        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private Node front;
    private Node rear;
    private int size;

    public LinkedListDeque() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public void addFirst(int element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            newNode.next = front;
            front.prev = newNode;
            front = newNode;
        }
        size++;
    }

    public void addLast(int element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            newNode.prev = rear;
            rear = newNode;
        }
        size++;
    }

    public int removeFirst() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        int element = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        } else {
            front.prev = null;
        }
        size--;
        return element;
    }

    public int removeLast() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        int element = rear.data;
        rear = rear.prev;
        if (rear == null) {
            front = null;
        } else {
            rear.next = null;
        }
        size--;
        return element;
    }

    public int peekFirst() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        return front.data;
    }

    public int peekLast() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is empty");
        }
        return rear.data;
    }

    public static void main(String[] args) {
        LinkedListDeque deque = new LinkedListDeque();

        deque.addLast(1);
        deque.addLast(2);
        deque.addFirst(3);
        System.out.println("First element: " + deque.peekFirst());
        System.out.println("Last element: " + deque.peekLast());
        System.out.println("Removed first: " + deque.removeFirst());
        System.out.println("Removed last: " + deque.removeLast());
    }
}

3. 时间复杂度

• 插入（addFirst, addLast）：O(1)，只需在链表的头部或尾部插入节点。
• 删除（removeFirst, removeLast）：O(1)，只需在链表的头部或尾部删除节点。
• 查看（peekFirst, peekLast）：O(1)，只需访问链表的头部或尾部节点。

三、数组实现与链表实现的比较

特性	数组实现双端队列	链表实现双端队列
时间复杂度（插入）	O(1)	O(1)
时间复杂度（删除）	O(1)	O(1)
时间复杂度（查看）	O(1)	O(1)
空间复杂度	O(n)	O(n)
动态调整容量	不容易，需手动扩容	容易，链表可以动态调整
内存使用	可能浪费（未用完的数组空间）	更节省（按需分配）
实现复杂度	较简单（数组操作）	稍复杂（需维护指针）
边界处理	需要处理队列满和空的情况	不需要处理（链表可动态扩展）

四、总结

双端队列（Deque）是一种灵活的数据结构，允许在两端进行插入和删除操作。使用数组实现的双端队列在固定容量的情况下具有较好的性能，但需要处理数组的边界问题；而使用链表实现的双端队列可以动态调整容量，适合内存需求更灵活的场景。

根据具体需求和应用场景，选择合适的实现方式可以更好地利用 Deque 的特性，满足性能和内存使用的要求。