java如何实现队列
队列的基本概念
队列是一种先进先出（FIFO）的数据结构，支持在队尾添加元素（入队），在队头移除元素（出队）。Java中可通过多种方式实现队列，包括内置类和自定义实现。
使用Java内置队列类
Java集合框架提供了多种队列实现，可直接调用：
- LinkedList：支持队列操作的双向链表。
Queue<Integer> queue = new LinkedList<>(); queue.offer(1); // 入队 queue.poll(); // 出队 - ArrayDeque：基于数组的双端队列，性能优于LinkedList。
Queue<String> deque = new ArrayDeque<>(); deque.offer("A"); deque.poll(); - 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<>();注意事项
- 数组实现需处理循环索引和扩容问题。
- 链表实现需注意头尾指针的更新。
- 线程安全场景选择并发集合类。
