Java集合框架深入：Queue、Deque与Stack

概述

Java集合框架提供了多种数据结构，其中Queue、Deque和Stack是常用的线性数据结构。它们各有特点，适用于不同的场景。

1. Queue接口

基本操作

import java.util.*;

public class QueueExample {
    public static void main(String[] args) {
        // 创建Queue
        Queue<String> queue = new LinkedList<>();
        
        // 添加元素
        queue.offer("A");  // 添加元素，返回boolean
        queue.offer("B");
        queue.offer("C");
        queue.add("D");    // 添加元素，队列满时抛出异常
        
        System.out.println("队列: " + queue);
        
        // 访问元素
        System.out.println("peek: " + queue.peek());  // 查看队首元素，不移除
        System.out.println("element: " + queue.element());  // 查看队首元素，队列空时抛出异常
        
        // 移除元素
        System.out.println("poll: " + queue.poll());  // 移除队首元素，队列空时返回null
        System.out.println("remove: " + queue.remove());  // 移除队首元素，队列空时抛出异常
        
        System.out.println("移除后: " + queue);
        
        // 检查队列
        System.out.println("是否为空: " + queue.isEmpty());
        System.out.println("大小: " + queue.size());
    }
}

PriorityQueue

import java.util.*;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建优先队列（默认最小堆）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);
        minHeap.offer(3);
        
        System.out.println("最小堆:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
        System.out.println();
        
        // 创建最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);
        maxHeap.offer(3);
        
        System.out.println("最大堆:");
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
        System.out.println();
        
        // 自定义比较器
        PriorityQueue<String> nameQueue = new PriorityQueue<>((a, b) -> a.compareTo(b));
        nameQueue.offer("Charlie");
        nameQueue.offer("Alice");
        nameQueue.offer("Bob");
        
        System.out.println("按字母排序:");
        while (!nameQueue.isEmpty()) {
            System.out.print(nameQueue.poll() + " ");
        }
        System.out.println();
    }
}

2. Deque接口

双端队列

import java.util.*;

public class DequeExample {
    public static void main(String[] args) {
        // 创建Deque
        Deque<String> deque = new ArrayDeque<>();
        
        // 作为队列使用
        deque.offer("A");  // 添加到队尾
        deque.offer("B");
        deque.offer("C");
        
        System.out.println("作为队列: " + deque);
        System.out.println("poll: " + deque.poll());
        
        // 作为栈使用
        deque.push("D");  // 添加到队首
        deque.push("E");
        
        System.out.println("作为栈: " + deque);
        System.out.println("pop: " + deque.pop());
        
        // 双端操作
        deque.offerFirst("F");
        deque.offerLast("G");
        
        System.out.println("双端操作后: " + deque);
        System.out.println("peekFirst: " + deque.peekFirst());
        System.out.println("peekLast: " + deque.peekLast());
    }
}

ArrayDeque vs LinkedList

import java.util.*;

public class DequeComparison {
    public static void main(String[] args) {
        // ArrayDeque性能更好
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        Deque<Integer> linkedList = new LinkedList<>();
        
        // 性能测试
        long startTime, endTime;
        
        // ArrayDeque
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            arrayDeque.offer(i);
        }
        for (int i = 0; i < 100000; i++) {
            arrayDeque.poll();
        }
        endTime = System.nanoTime();
        System.out.println("ArrayDeque耗时: " + (endTime - startTime) + "ns");
        
        // LinkedList
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            linkedList.offer(i);
        }
        for (int i = 0; i < 100000; i++) {
            linkedList.poll();
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList耗时: " + (endTime - startTime) + "ns");
    }
}

3. Stack类

import java.util.*;

public class StackExample {
    public static void main(String[] args) {
        // 创建Stack
        Stack<String> stack = new Stack<>();
        
        // 压栈
        stack.push("A");
        stack.push("B");
        stack.push("C");
        
        System.out.println("栈: " + stack);
        
        // 查看栈顶元素
        System.out.println("peek: " + stack.peek());
        
        // 弹栈
        System.out.println("pop: " + stack.pop());
        System.out.println("pop: " + stack.pop());
        
        System.out.println("弹栈后: " + stack);
        
        // 搜索元素
        System.out.println("搜索A: " + stack.search("A"));
        System.out.println("搜索C: " + stack.search("C"));
        
        // 检查是否为空
        System.out.println("是否为空: " + stack.empty());
    }
}

4. 实际应用示例

括号匹配

import java.util.*;

public class BracketMatcher {
    public static boolean isBalanced(String str) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : str.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println("()[]{}: " + isBalanced("()[]{}"));
        System.out.println("(]: " + isBalanced("(]"));
        System.out.println("([)]): " + isBalanced("([)]"));
        System.out.println("{[]}: " + isBalanced("{[]}"));
    }
}

广度优先搜索

import java.util.*;

public class BFS {
    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            
            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(3, 4));
        graph.put(2, Arrays.asList(5, 6));
        graph.put(3, Collections.emptyList());
        graph.put(4, Collections.emptyList());
        graph.put(5, Collections.emptyList());
        graph.put(6, Collections.emptyList());
        
        System.out.print("BFS遍历: ");
        bfs(graph, 0);
    }
}

LRU缓存

import java.util.*;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
    
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println("初始缓存: " + cache);
        
        cache.get(1);  // 访问1，使其最近使用
        System.out.println("访问1后: " + cache);
        
        cache.put(4, "D");  // 添加4，容量满，移除最久未使用的2
        System.out.println("添加4后: " + cache);
    }
}

5. 最佳实践

1. 选择合适的集合：根据需求选择Queue、Deque或Stack
2. 使用ArrayDeque：优先使用ArrayDeque而不是LinkedList
3. 避免使用Stack类：使用Deque代替Stack
4. 考虑线程安全：多线程环境使用ConcurrentLinkedQueue
5. 合理设置容量：PriorityQueue和LRUCache需要设置合适的容量

总结

Queue、Deque和Stack是Java集合框架中重要的线性数据结构。掌握它们的使用方法和适用场景，可以高效地解决各种数据处理问题。在实际编程中，要根据需求选择合适的集合类型，并注意性能和线程安全。