队列和堆栈介绍

<think>我们被要求介绍Java中的队列(Queue)和堆栈(Stack)。首先，我们需要明确它们都是集合，但具有不同的行为特征。 堆栈(Stack)遵循后进先出(LIFO)原则，而队列(Queue)遵循先进先出(FIFO)原则。 在Java中，Stack是一个类，而Queue是一个接口。我们分别介绍它们： 1. 堆栈(Stack): - 位于java.util.Stack，是Vector的子类（因此是线程安全的，但通常不推荐使用，因为性能较差）。 - 常用方法： push(E item) // 压栈 pop() // 弹栈（移除并返回栈顶元素） peek() // 查看栈顶元素（不移除） empty() // 判断栈是否为空 search(Object o) // 查找元素在栈中的位置（从栈顶开始为1） 但是，由于Stack继承自Vector，在不需要线程安全的情况下，通常推荐使用Deque（双端队列）来实现栈，因为Deque提供了更一致的LIFO操作，并且性能更好。 使用Deque实现栈的常用方法： push(E e) // 等同于addFirst pop() // 等同于removeFirst peek() // 等同于peekFirst 例如： Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.push(2); stack.pop(); // 返回2 2. 队列(Queue): - Queue是一个接口，位于java.util.Queue。 - 常用实现类：LinkedList, ArrayDeque, PriorityQueue等。 - 常用方法： add(E e) // 添加元素，如果队列满则抛出异常 offer(E e) // 添加元素，返回是否成功（推荐使用） remove() // 移除并返回队列头部的元素，如果队列为空则抛出异常 poll() // 移除并返回队列头部的元素，如果队列为空则返回null（推荐使用） element() // 返回队列头部的元素（不移除），如果队列为空则抛出异常 peek() // 返回队列头部的元素（不移除），如果队列为空则返回null（推荐使用） 队列还有多种变体： - 双端队列(Deque)：支持在两端插入和移除元素。 - 阻塞队列(BlockingQueue)：支持阻塞操作的队列，位于java.util.concurrent包下，如ArrayBlockingQueue, LinkedBlockingQueue。 - 优先级队列(PriorityQueue)：元素按照自然顺序或者比较器顺序出队。 代码示例： 堆栈（使用Stack类，不推荐）： Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); System.out.println(stack.pop()); // 输出2 堆栈（推荐使用Deque）： Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.push(2); System.out.println(stack.pop()); // 输出2 队列（使用LinkedList）： Queue<Integer> queue = new LinkedList<>(); queue.offer(1); queue.offer(2); System.out.println(queue.poll()); // 输出1 双端队列（Deque）： Deque<Integer> deque = new LinkedList<>(); deque.offerFirst(1); // 从头部添加 deque.offerLast(2); // 从尾部添加 System.out.println(deque.pollFirst()); // 输出1 System.out.println(deque.pollLast()); // 输出2 优先级队列（PriorityQueue）： Queue<Integer> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(3); priorityQueue.offer(1); priorityQueue.offer(2); System.out.println(priorityQueue.poll()); // 输出1（最小元素优先） 阻塞队列（以ArrayBlockingQueue为例）： BlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<>(10); // 生产者线程 blockingQueue.put(1); // 如果队列满则阻塞 // 消费者线程 int num = blockingQueue.take(); // 如果队列空则阻塞 注意：由于阻塞队列涉及多线程，使用时需要处理中断异常（InterruptedException）。 总结： - 栈：推荐使用Deque接口的实现类（如ArrayDeque）来替代Stack类。 - 队列：根据需求选择实现，如LinkedList、ArrayDeque、PriorityQueue或阻塞队列。 最后，按照要求提出相关问题。</think>### Java队列(Queue)与堆栈(Stack)详解 #### 一、堆栈(Stack) - LIFO（后进先出） 堆栈是一种**后进先出**（Last-In-First-Out）的数据结构，核心操作是压栈(push)和弹栈(pop)。 **1. Stack类实现（不推荐）** ```java // 传统Stack类（继承自Vector，线程安全但性能差） Stack<String> stack = new Stack<>(); stack.push("Java"); // 压栈 stack.push("Python"); System.out.println(stack.peek()); // 查看栈顶 → "Python" System.out.println(stack.pop()); // 弹栈 → "Python" System.out.println(stack.size()); // 剩余元素 → 1 ``` **2. 推荐实现（Deque接口）** ```java // 使用ArrayDeque实现栈（高性能非线程安全） Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // 压栈 stack.push(20); while (!stack.isEmpty()) { System.out.println(stack.pop()); // 弹栈输出: 20 → 10 } ``` **堆栈特性**： - 核心操作：`push()`, `pop()`, `peek()` - 应用场景：方法调用栈、括号匹配、表达式求值、回溯算法 #### 二、队列(Queue) - FIFO（先进先出） 队列是一种**先进先出**（First-In-First-Out）的数据结构，核心操作是入队(enqueue)和出队(dequeue)。 **1. 基础队列实现** ```java Queue<String> queue = new LinkedList<>(); queue.offer("Apple"); // 入队（推荐） queue.add("Banana"); // 入队（失败时抛异常） System.out.println(queue.peek()); // 查看队首 → "Apple" System.out.println(queue.poll()); // 出队 → "Apple" System.out.println(queue.size()); // 剩余元素 → 1 ``` **2. 双端队列(Deque)** ```java Deque<Character> deque = new ArrayDeque<>(); deque.offerFirst('A'); // 队首插入 deque.offerLast('Z'); // 队尾插入 System.out.println(deque.pollFirst()); // → 'A' System.out.println(deque.pollLast()); // → 'Z' ``` #### 三、特殊队列类型 **1. 优先级队列(PriorityQueue)** ```java Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); pq.offer(5); pq.offer(9); pq.offer(2); System.out.println(pq.poll()); // → 9（按优先级出队） System.out.println(pq.poll()); // → 5 ``` **2. 阻塞队列(BlockingQueue)** ```java BlockingQueue<String> bq = new ArrayBlockingQueue<>(3); // 生产者线程 bq.put("Data"); // 队列满时阻塞 // 消费者线程 String data = bq.take(); // 队列空时阻塞 ``` **3. 并发队列** ```java // 高并发场景队列 Queue<Integer> safeQueue = new ConcurrentLinkedQueue<>(); safeQueue.offer(100); // 无锁算法实现 ``` #### 四、队列与堆栈对比 | 特性 | 堆栈(Stack) | 队列(Queue) | |--------------|----------------------|----------------------| | 数据顺序 | LIFO（后进先出） | FIFO（先进先出） | | 核心操作 | push/pop/peek | offer/poll/peek | | 实现类 | Stack, ArrayDeque | LinkedList, ArrayDeque | | 线程安全实现 | Stack（同步） | BlockingQueue实现 | | 典型应用 | 方法调用栈、DFS | 任务调度、BFS | #### 五、经典算法应用 **1. 用队列实现栈** ```java class MyStack { Queue<Integer> queue = new LinkedList<>(); public void push(int x) { queue.offer(x); // 将新元素前的所有元素移到新元素后 for (int i = 0; i < queue.size() - 1; i++) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } } ``` **2. 用栈实现队列** ```java class MyQueue { Deque<Integer> input = new ArrayDeque<>(); Deque<Integer> output = new ArrayDeque<>(); public void push(int x) { input.push(x); } public int pop() { if (output.isEmpty()) { while (!input.isEmpty()) { output.push(input.pop()); } } return output.pop(); } } ``` **3. 括号匹配验证（栈应用）** ```java boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '[') stack.push(']'); else if (c == '{') stack.push('}'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); } ``` ### 总结 - **堆栈**：适用于需要**反向处理**的场景，使用`Deque`接口的`ArrayDeque`实现 - **队列**：适用于**顺序处理**场景，基础实现用`LinkedList`，并发用`BlockingQueue` - **选择原则**： - 需要LIFO行为 → 堆栈 - 需要FIFO行为 → 队列 - 需要两端操作 → 双端队列(Deque) - 需要优先级处理 → 优先级队列(PriorityQueue)