Java [数据结构] Deque与Queue

avatar
作者
筋斗云
阅读量:0

🤺深入理解 Java 中的 Deque 和 Queue🤺

在现代软件开发中,数据结构是构建高效、可维护代码的基础。

Java 作为一门广泛应用的编程语言,其丰富的集合框架(Collections Framework)为开发者提供了多种强大的数据结构,其中 Queue(队列)和 Deque(双端队列)尤为常见。本文将深入探讨 Java 中的 QueueDeque,帮助你更好地理解和使用它们来解决实际问题。

队列和双端队列在日常编程中的应用场景非常广泛。无论是任务调度、缓存系统,还是处理广度优先搜索(BFS)算法,队列都能大显身手。而双端队列则进一步扩展了队列的功能,使得数据可以从两端插入和删除,增加了数据处理的灵活性。

本文将从概念、接口方法和具体实现三个方面,详细介绍 QueueDeque 的基本原理及其在 Java 中的具体应用。通过对比这两种数据结构的异同,希望读者能够更好地选择和使用它们,提高程序的性能和可读性。

接下来,让我们首先了解 Queue 的基本概念及其在 Java 中的实现。

Queue(队列)使用Deque

概念

  • 队列是一种先进先出(FIFO,First-In-First-Out)的数据结构。
  • 常用于排队系统,如任务调度、缓冲区等。

主要接口方法

  • boolean add(E e): 将元素添加到队列尾部,如果成功返回 true,如果失败(例如容量限制)抛出异常。
  • boolean offer(E e): 将元素添加到队列尾部,如果成功返回 true,如果失败返回 false。
  • E remove(): 移除并返回队列头部的元素,如果队列为空抛出异常。
  • E poll(): 移除并返回队列头部的元素,如果队列为空返回 null。
  • E element(): 返回队列头部的元素,但不移除它,如果队列为空抛出异常。
  • E peek(): 返回队列头部的元素,但不移除它,如果队列为空返回 null。

实现类

  • LinkedList
  • PriorityQueue
  • ArrayDeque
  • ConcurrentLinkedQueue
  • LinkedBlockingQueue
  • ArrayBlockingQueue

import java.util.Deque; import java.util.ArrayDeque;  public class QueueUsingDequeDemo {      public static void main(String[] args) {         // 创建一个ArrayDeque实例,当作单向队列使用         Deque<String> queue = new ArrayDeque<>();          // 入队操作:在队列尾部添加元素         queue.offer("苹果");         queue.offer("香蕉");         queue.offer("樱桃");          System.out.println("当前队列: " + queue);          // 出队操作:从队列头部移除并获取元素         String firstFruit = queue.poll();         if (firstFruit != null) {             System.out.println("出队元素: " + firstFruit);             System.out.println("出队后队列: " + queue);         } else {             System.out.println("队列为空,无法出队。");         }          // 检查队列是否为空         boolean isEmpty = queue.isEmpty();         System.out.println("队列是否为空? " + isEmpty);     } } 

Deque(双端队列)

概念

  • 双端队列是一种可以在两端进行插入和删除操作的数据结构。
  • 支持既可以作为队列使用(FIFO),也可以作为栈使用(LIFO,Last-In-First-Out)。

主要接口方法

  • 插入操作:
    • void addFirst(E e): 在队列的头部添加元素,如果失败抛出异常。
    • void addLast(E e): 在队列的尾部添加元素,如果失败抛出异常。
    • boolean offerFirst(E e): 在队列的头部添加元素,如果成功返回 true,如果失败返回 false。
    • boolean offerLast(E e): 在队列的尾部添加元素,如果成功返回 true,如果失败返回 false。
  • 移除操作:
    • E removeFirst(): 移除并返回队列头部的元素,如果队列为空抛出异常。
    • E removeLast(): 移除并返回队列尾部的元素,如果队列为空抛出异常。
    • E pollFirst(): 移除并返回队列头部的元素,如果队列为空返回 null。
    • E pollLast(): 移除并返回队列尾部的元素,如果队列为空返回 null。
  • 检查操作:
    • E getFirst(): 返回队列头部的元素,但不移除它,如果队列为空抛出异常。
    • E getLast(): 返回队列尾部的元素,但不移除它,如果队列为空抛出异常。
    • E peekFirst(): 返回队列头部的元素,但不移除它,如果队列为空返回 null。
    • E peekLast(): 返回队列尾部的元素,但不移除它,如果队列为空返回 null。

实现类都可以

  • LinkedList
  • ArrayDeque
  • LinkedBlockingDeque
import java.util.Deque; import java.util.ArrayDeque;  public class DequeDemo {      public static void main(String[] args) {         // 创建一个ArrayDeque实例         Deque<String> deque = new ArrayDeque<>();          deque.addFirst("你好");          // 在队列末尾添加元素         deque.addLast("苹果");         deque.addLast("香蕉");         deque.addLast("樱桃");          System.out.println("初始双端队列: " + deque);          // 在队列开头添加元素         deque.addFirst("火龙果");          System.out.println("在队首添加后: " + deque);          // 从队列开头移除并获取元素         String firstFruit = deque.removeFirst();         String s = deque.pollFirst();          System.out.println("从队首1移除: " + firstFruit);         System.out.println("从队首2移除: " + s);          System.out.println("移除后双端队列: " + deque);          // 从队列末尾移除并获取元素         String lastFruit = deque.removeLast();         System.out.println("从队尾移除: " + lastFruit);         System.out.println("再次移除后双端队列: " + deque);          // 检查双端队列是否为空         boolean isDequeEmpty = deque.isEmpty();         System.out.println("大小" + deque.size());         System.out.println("双端队列是否为空? " + isDequeEmpty);     } } 

总结

  • Queue 适用于需要先进先出的情况,常见实现类如 LinkedListPriorityQueue
  • Deque 提供了更多的灵活性,可以作为队列(FIFO)和栈(LIFO)使用,常见实现类如 LinkedListArrayDeque

觉得有用的话可以点点赞 (*/ω\*),支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

    广告一刻

    为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!