双端队列：链表实现与数组环形实现

双端队列基础

• Deque：头尾都可进可出
• 常见操作：
  • 头插 insertFront(x)、尾插 insertLast(x)
  • 头删 deleteFront()、尾删 deleteLast()
  • 取头 getFront()、取尾 getRear()
  • 判空 isEmpty()、判满 isFull()（固定容量时）

链表版双端队列

import java.util.Deque;
import java.util.LinkedList;

public class Code_09 {

    // 1) 基于 JDK 双端链表的定长 Deque
    class MyCircularDeque1 {
        public Deque<Integer> deque = new LinkedList<>();
        public int size;
        public int limit;

        public MyCircularDeque1(int k){
            size = 0;
            limit = k;
        }

        public boolean insertFront(int value){
            if (isFull()) return false;
            deque.offerFirst(value);
            size++;
            return true;
        }

        public boolean insertLast(int value){
            if (isFull()) return false;
            deque.offerLast(value);
            size++;
            return true;
        }

        public boolean deleteFront(){
            if (isEmpty()) return false;
            deque.pollFirst();
            size--;
            return true;
        }

        public boolean deleteLast(){
            if (isEmpty()) return false;
            deque.pollLast();
            size--;
            return true;
        }

        public int getFront(){
            return isEmpty() ? -1 : deque.peekFirst();
        }

        public int getRear(){
            return isEmpty() ? -1 : deque.peekLast();
        }

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

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

数组版环形双端队列

 class MyCircularDeque2{
        public int[] deque;
        public int l, r, size, limit;

        public MyCircularDeque2(int k){
            deque = new int[k];
            l = r = size = 0;
            limit = k;
        }

        // 头插
        public boolean insertFront(int value){
            if (isFull()) return false;
            if (isEmpty()) {
                l = r = 0;
                deque[l] = value;
            } else {
                l = (l == 0) ? (limit - 1) : (l - 1);
                deque[l] = value;
            }
            size++;
            return true;
        }

        // 尾插
        public boolean insertLast(int value){
            if (isFull()) return false;
            if (isEmpty()) {
                l = r = 0;
                deque[r] = value;
            } else {
                r = (r == limit - 1) ? 0 : (r + 1);
                deque[r] = value;
            }
            size++;
            return true;
        }

        // 头删
        public boolean deleteFront(){
            if (isEmpty()) return false;
            if (size == 1) {
                // 删成空，l/r 复位可选
                // l = r = 0; // 可省略：只要 size=0，l/r 值无影响
            } else {
                l = (l == limit - 1) ? 0 : (l + 1);
            }
            size--;
            return true;
        }

        // 尾删
        public boolean deleteLast(){
            if (isEmpty()) return false;
            if (size == 1) {
                // 同上
                // l = r = 0;
            } else {
                r = (r == 0) ? (limit - 1) : (r - 1);
            }
            size--;
            return true;
        }

        public int getFront(){
            return isEmpty() ? -1 : deque[l];
        }

        public int getRear(){
            return isEmpty() ? -1 : deque[r];
        }

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

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