Deque 在 Java 中有哪些典型应用

Deque（双端队列，Double Ended Queue）在Java中有多种典型应用，主要包括以下几个方面：

1. 实现栈（Stack）：

   • 虽然Java提供了java.util.Stack类，但许多开发者更倾向于使用Deque来实现栈，因为Deque提供了更多的灵活性。
   • 示例代码：

     Deque<Integer> stack = new ArrayDeque<>();
     stack.push(1);
     stack.push(2);
     int topElement = stack.pop(); // topElement will be 2
     

2. 实现队列（Queue）：

   • Deque可以作为队列使用，支持在两端进行元素的插入和删除操作。
   • 示例代码：

     Deque<Integer> queue = new ArrayDeque<>();
     queue.add(1);
     queue.add(2);
     int frontElement = queue.poll(); // frontElement will be 1
     int rearElement = queue.peekLast(); // rearElement will be 2
     

3. 实现循环队列：

   • 通过使用Deque，可以轻松地实现循环队列，这在某些应用场景中非常有用，例如模拟环形缓冲区。
   • 示例代码：

     Deque<Integer> circularQueue = new ArrayDeque<>(5);
     for (int i = 1; i <= 5; i++) {
         circularQueue.add(i);
     }
     System.out.println(circularQueue.pollFirst()); // Output: 1
     System.out.println(circularQueue.peekLast()); // Output: 5
     

4. 解决“下一个更大元素”问题：

   • 在处理“下一个更大元素”这类问题时，可以使用Deque来存储已经遍历过的元素，从而在O(1)时间内找到下一个更大的元素。
   • 示例代码（使用单调栈）：

     Deque<Integer> stack = new ArrayDeque<>();
     int[] nums = {1, 2, 1};
     for (int num : nums) {
         while (!stack.isEmpty() && stack.peek() < num) {
             System.out.print(stack.pop() + " ");
         }
         stack.push(num);
     }
     // Output: 2 1
     

5. 实现广度优先搜索（BFS）：

   • 在图论和树形结构中，Deque常用于实现广度优先搜索算法。
   • 示例代码：

     Deque<Integer> queue = new ArrayDeque<>();
     queue.add(1);
     queue.add(2);
     queue.add(3);
     while (!queue.isEmpty()) {
         int node = queue.poll();
         System.out.print(node + " ");
         if (node == 2) {
             queue.add(4);
         }
         if (node == 3) {
             queue.add(5);
         }
     }
     // Output: 1 2 3 4 5
     

6. 撤销/重做功能：

   • 在许多应用程序中，如文本编辑器或绘图程序，Deque可以用于存储历史记录，以实现撤销和重做功能。
   • 示例代码：

     Deque<String> history = new ArrayDeque<>();
     history.add("Step 1");
     history.add("Step 2");
     System.out.println(history.pollLast()); // Output: Step 2
     history.add("Step 3");
     System.out.println(history.pollFirst()); // Output: Step 1
     

这些只是Deque在Java中的一些典型应用，实际上，Deque的用途非常广泛，可以根据具体需求进行灵活运用。