知识模块
☕ Java 知识模块
二、Java 集合框架
Queue vs Stack

Queue vs Stack

Queue（队列）和 Stack（栈）是两种经典的数据结构，它们的区别在于元素的存取顺序。Queue 是先进先出（FIFO），Stack 是先进后出（LIFO）。理解它们的实现和应用场景，是 Java 集合框架学习的重要部分。

一、数据结构基础

1.1 队列（Queue）- FIFO

队列是一种**先进先出（First In First Out）**的数据结构。

        队列（FIFO）

    入队（enqueue）                    出队（dequeue）
         │                                  │
         ▼                                  ▼
    ┌────┬────┬────┬────┬────┐        ┌────┬────┬────┬────┬────┐
    │ A  │ B  │ C  │ D  │ E  │   →    │ B  │ C  │ D  │ E  │    │
    └────┴────┴────┴────┴────┘        └────┴────┴────┴────┴────┘
    ▲                                  ▲
    │                                  │
   尾部                               头部
   
   A 最先入队，也最先出队

1.2 栈（Stack）- LIFO

栈是一种**先进后出（Last In First Out）**的数据结构。

        栈（LIFO）

    入栈（push）    出栈（pop）
         │              │
         ▼              ▼
       ┌───┐          ┌───┐
       │ E │ ← 栈顶    │ D │ ← 栈顶
       ├───┤          ├───┤
       │ D │          │ C │
       ├───┤          ├───┤
       │ C │          │ B │
       ├───┤          ├───┤
       │ B │          │ A │ ← 栈底
       ├───┤          └───┘
       │ A │ ← 栈底
       └───┘
       
    E 最后入栈，最先出栈

1.3 对比

对比项Queue（队列）Stack（栈）
存取顺序FIFO（先进先出）LIFO（后进先出）
入口尾部（rear）栈顶（top）
出口头部（front）栈顶（top）
形象比喻排队买票叠盘子
应用场景任务调度、消息队列函数调用栈、撤销操作

二、Queue 接口

2.1 Queue 接口定义

public interface Queue<E> extends Collection<E> {
    // 插入元素（失败抛异常）
    boolean add(E e);
    
    // 插入元素（失败返回 false）
    boolean offer(E e);
    
    // 移除并返回队头（队列为空抛异常）
    E remove();
    
    // 移除并返回队头（队列为空返回 null）
    E poll();
    
    // 获取队头但不移除（队列为空抛异常）
    E element();
    
    // 获取队头但不移除（队列为空返回 null）
    E peek();
}

2.2 Queue 方法对比

操作抛异常返回特殊值
插入add(e)offer(e)
移除remove()poll()
检查element()peek()

2.3 Queue 实现类

                    ┌─────────────┐
                    │   Queue<E>  │
                    └──────┬──────┘
                           │
        ┌──────────────────┼──────────────────┐
        │                  │                  │
  ┌─────┴─────┐      ┌─────┴─────┐      ┌─────┴─────┐
  │ LinkedList│      │PriorityQueue│    │ArrayDeque │
  └───────────┘      └───────────┘      └───────────┘
  链表队列            优先队列            数组双端队列

2.4 LinkedList 作为 Queue

// LinkedList 实现了 Queue 接口
Queue<String> queue = new LinkedList<>();
 
// 入队
queue.offer("A");
queue.offer("B");
queue.offer("C");
 
// 查看队头
System.out.println(queue.peek());  // A
 
// 出队
System.out.println(queue.poll());  // A
System.out.println(queue.poll());  // B
System.out.println(queue.poll());  // C
System.out.println(queue.poll());  // null（队列为空）

2.5 PriorityQueue（优先队列）

PriorityQueue 是基于堆实现的优先队列，元素按优先级（自然顺序或自定义比较器）排序。

// 默认最小堆（小元素优先）
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.offer(2);
 
// 按升序出队
System.out.println(pq.poll());  // 1
System.out.println(pq.poll());  // 2
System.out.println(pq.poll());  // 3
System.out.println(pq.poll());  // 5
 
// 最大堆（大元素优先）
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
// 或
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);
 
// 自定义优先级
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparing(Task::getPriority).reversed()
);

三、Deque 接口

3.1 Deque 定义

Deque（Double Ended Queue）是双端队列，支持在两端进行插入和删除操作。

public interface Deque<E> extends Queue<E> {
    // 头部操作
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    
    // 栈操作
    void push(E e);    // 等同于 addFirst(e)
    E pop();           // 等同于 removeFirst()
}

3.2 Deque 作为栈

// ArrayDeque 和 LinkedList 都实现了 Deque 接口
// 可以作为栈使用
 
Deque<String> stack = new ArrayDeque<>();
 
// 入栈
stack.push("A");
stack.push("B");
stack.push("C");
 
// 查看栈顶
System.out.println(stack.peek());  // C
 
// 出栈
System.out.println(stack.pop());   // C
System.out.println(stack.pop());   // B
System.out.println(stack.pop());   // A

3.3 Deque 作为队列

Deque<String> queue = new ArrayDeque<>();
 
// 入队（尾部）
queue.offerLast("A");
queue.offerLast("B");
queue.offerLast("C");
 
// 出队（头部）
System.out.println(queue.pollFirst());  // A
System.out.println(queue.pollFirst());  // B
System.out.println(queue.pollFirst());  // C

四、ArrayDeque

4.1 特点

ArrayDeque 是基于可扩容数组实现的双端队列。

特点说明
底层数据结构可扩容数组（循环数组）
容量自动扩容（初始 16）
性能比 LinkedList 更快
不允许 null不能存储 null 元素

4.2 内部结构

ArrayDeque 内部结构（循环数组）：

head = 8, tail = 11

           head              tail
            │                 │
            ▼                 ▼
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │ A │ B │ C │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

head 指向队头元素，tail 指向下一个插入位置
数组是循环使用的

4.3 性能对比

// ArrayDeque vs LinkedList 作为栈的性能测试
 
// ArrayDeque 作为栈
Deque<Integer> stack1 = new ArrayDeque<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
    stack1.push(i);
}
while (!stack1.isEmpty()) {
    stack1.pop();
}
System.out.println("ArrayDeque: " + (System.currentTimeMillis() - start) + "ms");
 
// LinkedList 作为栈
Deque<Integer> stack2 = new LinkedList<>();
start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
    stack2.push(i);
}
while (!stack2.isEmpty()) {
    stack2.pop();
}
System.out.println("LinkedList: " + (System.currentTimeMillis() - start) + "ms");
 
// 结果：ArrayDeque 比 LinkedList 快约 2-3 倍

五、阻塞队列

5.1 BlockingQueue 接口

BlockingQueue 是线程安全的阻塞队列，常用于生产者-消费者模式。

public interface BlockingQueue<E> extends Queue<E> {
    // 插入（满则等待）
    void put(E e) throws InterruptedException;
    
    // 插入（满则等待指定时间）
    boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
    
    // 移除（空则等待）
    E take() throws InterruptedException;
    
    // 移除（空则等待指定时间）
    E poll(long timeout, TimeUnit unit) throws InterruptedException;
}

5.2 常见实现类

实现类特点
ArrayBlockingQueue有界阻塞队列（数组实现）
LinkedBlockingQueue可选有界阻塞队列（链表实现）
PriorityBlockingQueue无界优先阻塞队列
SynchronousQueue无缓冲，直接传递
DelayQueue延迟队列（元素需实现 Delayed）

5.3 生产者-消费者示例

public class ProducerConsumerDemo {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new ArrayBlockingQueue<>(10);
        
        // 生产者
        new Thread(() -> {
            for (int i = 0; i < 20; i++) {
                try {
                    queue.put("消息-" + i);
                    System.out.println("生产: 消息-" + i);
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
        
        // 消费者
        new Thread(() -> {
            for (int i = 0; i < 20; i++) {
                try {
                    String msg = queue.take();
                    System.out.println("消费: " + msg);
                    Thread.sleep(200);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
    }
}

六、常见面试题

Q1: Queue 和 Stack 的区别？

A:

对比项QueueStack
存取顺序FIFO（先进先出）LIFO（后进先出）
入口/出口尾入头出栈顶入栈顶出
应用任务调度、消息队列函数调用栈、撤销

Q2: ArrayDeque 和 LinkedList 作为栈哪个更好？

A: ArrayDeque 更好：

  • ArrayDeque 基于数组，内存连续，缓存友好
  • LinkedList 基于链表，每个节点需要额外存储前后指针
  • ArrayDeque 的操作更快，内存占用更少

Q3: PriorityQueue 是如何实现的？

A: 基于二叉堆实现：

  • 最小堆：父节点 ≤ 子节点，堆顶是最小元素
  • 最大堆：父节点 ≥ 子节点，堆顶是最大元素
  • 入队和出队都是 O(log n)

Q4: BlockingQueue 有什么用？

A:

  • 生产者-消费者模式
  • 线程池任务队列
  • 消息队列
  • 实现流量控制

Q5: 为什么 ArrayDeque 不允许 null？

A:

  • null 有特殊含义：poll() 返回 null 表示队列为空
  • 如果允许 null，会产生歧义

Q6: 如何实现一个线程安全的栈？

A:

// 方式1：使用 synchronized
public class SyncStack<E> {
    private Deque<E> stack = new ArrayDeque<>();
    
    public synchronized void push(E e) {
        stack.push(e);
    }
    
    public synchronized E pop() {
        retu
HashSet vs TreeSetIterator Fail-Fast