如何在Java中使用Deque? - Java67

21-11-11 banq

Queue 和 Deque的区别在于 ,您只能从 Queue 的后端添加元素,但可以在 Deque 的前端和后端添加元素。

考虑你想实现一个售票柜台。人们可以从最后进入队列,并将从前面移除。而且,为了实现这个场景,我们将使用的数据结构将是 Queue 数据结构,对吗?很容易吧?等等,现在让我们再观察一个场景。

 你进入队列并买票。买完票就走人了。但是,您发现票上印的名字有出入还为时不晚。(一个经典的售票柜台错误!)

现在,你会怎么做?已经买好票了,不用再排队了,对吧?您将直接前往售票柜台并检查是否存在差异。但是你们有没有通过这个场景观察到什么?花 2 分钟时间思考一些与队列相关的事情。如果你们观察到,你是第二次从前面进入队列!但是队列中不支持该操作,对吗?所以,基本上, 我们需要一个 Queue 不仅可以从后面插入,还可以从前面插入。 

这就是Deque概念的 由来!众所周知,队列可以使用链表来实现。

一个deque的是一个双端队列,我们可以从两端添加,更新或删除元素。队列可以使用链表来实现,其中首先插入的元素首先被删除(FIFO)。

单向链表可用于实现无界队列,双链表可用于实现双端队列。

 

以下是 Java 中 Dequeue 数据结构的一些重要方法:

  • insertFront() :在双端队列的前面添加一个项目
  • insertLast() : 在双端队列的末尾添加一个项目
  • deleteFront() : 从 deque 的前面删除一个项目
  • deleteLast() : 从双端队列的末尾删除一个项目
  • getFront() : 从 deque 获取前面的元素
  • getRear() : 从双端队列中获取后/最后一项

 

这是我们完整的 Java 程序,用于演示如何在 Java 中使用 Deque 集合类。在这个程序中,我们使用了 ArrayDeque 作为 Deque 的实现。请记住,Dequeue 允许您在两端插入和删除对象,这就是本示例中显示的内容。

您可以使用addFirst()方法在第一个或前面 添加元素,并使用add()方法在后端添加元素 。同样,您可以使用Java 中的removeFirst()方法从前端删除元素 。 

import java.util.ArrayDeque;
import java.util.Deque;


public class DequeDemo extends Thread{
public static Deque<Integer> deque;
public static void main(String[] args) throws InterruptedException {
deque = new ArrayDeque<>();

//add at last
deque.add(1);
//deque : 1

//add at first
deque.addFirst(3);
//deque : 3 -> 1

//add at last
deque.addLast(2);
//deque: 3 -> 1 -> 2

//add at last
deque.add(4);
//deque : 3 -> 1 -> 2 -> 4

//remove at first
deque.removeFirst();
//deque : 1 -> 2 -> 4

deque.forEach(a -> System.out.print(a+"->"));
System.out.println();

}
}

 

Java 中 Deque 的局限性

在考虑多线程环境时,Deque 有一些限制。考虑一个场景。考虑 3 个线程同时处理一个 Deque,并且两个线程都想在第 4 个索引处添加一个元素。

考虑一个 Deque,其中线程 A 和线程 B 都试图将一个元素放在第 4 个位置。线程 A 想要插入值 7,线程 B 想要插入值 9。无论哪个线程首先访问双端队列都会放置一个值。假设线程 B 首先放置一个值 9,然后线程 A 来并将该值更改为 7。现在,线程 A 知道该值是 7,但线程 B 仍然认为该值是 9。这是一个经典案例由于多线程期间缺乏安全性,这些值会丢失。 

当您实际尝试使用 Deque 编写此场景 时,当您尝试从多个线程同时修改 Deque 时,java 将抛出 ConcurrentModificationException。

 

猜你喜欢