java如何实现队列

队列的基本概念

队列是一种先进先出（FIFO）的数据结构，支持在队尾添加元素（入队），在队头移除元素（出队）。Java中可通过多种方式实现队列，包括内置类和自定义实现。

使用Java内置队列类

Java集合框架提供了多种队列实现，可直接调用：

1. LinkedList：支持队列操作的双向链表。

   Queue<Integer> queue = new LinkedList<>();
   queue.offer(1); // 入队
   queue.poll();    // 出队

2. ArrayDeque：基于数组的双端队列，性能优于LinkedList。

   Queue<String> deque = new ArrayDeque<>();
   deque.offer("A");
   deque.poll();

3. PriorityQueue：基于优先级的堆实现，元素按顺序出队。

   Queue<Integer> pq = new PriorityQueue<>();
   pq.offer(3);
   pq.poll(); // 按自然顺序出队

自定义数组实现队列

通过数组和指针模拟队列操作：

public class ArrayQueue {
    private int[] data;
    private int front, rear, size;

    public ArrayQueue(int capacity) {
        data = new int[capacity];
        front = rear = size = 0;
    }

    public void enqueue(int value) {
        if (size == data.length) throw new IllegalStateException("Queue full");
        data[rear] = value;
        rear = (rear + 1) % data.length; // 循环数组
        size++;
    }

    public int dequeue() {
        if (size == 0) throw new NoSuchElementException("Queue empty");
        int value = data[front];
        front = (front + 1) % data.length;
        size--;
        return value;
    }
}

链表实现队列

使用链表节点动态管理元素：

public class LinkedQueue {
    private static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
    }

    private Node head, tail;

    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (tail == null) head = tail = newNode;
        else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    public int dequeue() {
        if (head == null) throw new NoSuchElementException();
        int value = head.value;
        head = head.next;
        if (head == null) tail = null;
        return value;
    }
}

线程安全队列

多线程环境下可使用ConcurrentLinkedQueue或BlockingQueue实现：

Queue<String> concurrentQueue = new ConcurrentLinkedQueue<>();
BlockingQueue<Integer> blockingQueue = new LinkedBlockingQueue<>();

注意事项

• 数组实现需处理循环索引和扩容问题。
• 链表实现需注意头尾指针的更新。
• 线程安全场景选择并发集合类。