Java队列Queue和Deque区别 Java中队列Queue和Deque的区别与代码实例
哪 吒 人气:0一、Queue和Deque
Queue以及Deque都是继承于Collection,Deque是Queue的子接口。
Queue是FIFO的单向队列,Deque是双向队列。
Queue有一个直接子类PriorityQueue,而Deque中直接子类有两个:LinkedList以及ArrayDeque。
PriorityQueue的底层数据结构是数组,而无边界的形容,那么指明了PriorityQueue是自带扩容机制的。
ArrayDeque是无初始容量的双端队列,LinkedList则是双向链表。
PriorityQueue可以作为堆使用,而且可以根据传入的Comparator实现大小的调整,会是一个很好的选择。
ArrayDeque通常作为栈或队列使用,但是栈的效率不如LinkedList高。
LinkedList通常作为栈或队列使用,但是队列的效率不如ArrayQueue高。
二、api对比
Queue | Deque | |
增加 | add | add、addFirst、addLast |
offer | offer、offerFirst、offerLast | |
移除 | remove | remove、removeFirst、removeLast |
poll | pop、poll、pollFirst、pollLast | |
获取 | element | element、getFirst、getLast |
peek | peek、peekFirst、peekLast |
备注:
1、add和offer区别
- add() : 添加元素,如果添加成功则返回true,如果队列是满的,则抛出异常
- offer() : 添加元素,如果添加成功则返回true,如果队列是满的,则返回false
2、remove和poll
- remove() : 移除队列头的元素并且返回,如果队列为空则抛出异常
- poll() : 移除队列头的元素并且返回,如果队列为空则返回null
- Deque新增了一个pop方法,也是移除队列头的元素并且返回,如果队列为空则抛出异常。
3、element和peek
- element() :返回队列头元素但不移除,如果队列为空,则抛出异常
- peek() :返回队列头元素但不移除,如果队列为空,则返回null
- 因此,增加推荐使用add,移除推荐使用poll,获取元素推荐使用peek。
三、代码实例
1、queue
队列(queue)是一种常用的数据结构,可以将队列看做是一种特殊的线性表,该结构遵循的先进先出原则。Java中,LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高。
初始化:
Queue <Integer> q = new LinkedList<Integer>();
常用方法:
**add(E e)😗*将指定元素插入此队列尾部,成功返回true。
**offer(E e)😗*将指定元素插入队列尾部,成功返回true。当队列有容量 限制时,此方法由于add,因为后者可能无法插入,而只是抛出IllegalStateException异常。
**remove()😗*获取并移除队列的头部元素,队列为空抛出异常。
**poll():**获取并移除队列的头部元素,队列为空返回null。
**element()😗*获取但是不移除队列头部元素,队列为空抛出异常。
**peek()😗*获取但是不移除队列头部元素,队列为空返回null。
**isEmpty()😗*判断队列是否为空,为空返回true。
**size()😗*获取队列元素数量.
实例代码:
public static void test01(){ Queue<String> queue = new LinkedList<>(); // add()和remove()方法在失败的时候会抛出异常(不推荐) queue.offer("a"); queue.offer("b"); queue.offer("c"); queue.offer("d"); queue.offer("e"); queue.add("f"); //在队列元素为空的情况下,remove() 方法会抛出NoSuchElementException异常,poll() 方法只会返回 null 。 String first2 = queue.remove();//返回第一个元素,删除 System.out.println(first2);//a String first1 = queue.poll();//返回第一个元素,删除 System.out.println(first1);//b String first = queue.peek();//返回第一个元素,但不删除 System.out.println(first);//c System.out.println(queue);//[c, d, e, f] first = queue.element();//返回第一个元素 System.out.println(first);//c }
2、deque
双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队,则可实现栈的数据结构。对于栈而言,有入栈(push)和出栈(pop),遵循先进后出原则。
初始化:
Deque<Integer> d = new LinkedList<Integer>();
常用方法:
**addLast(E e)😗*在队列尾部插入元素.
**offerLast(E e)😗*在队列尾部插入元素。
**removeFirst()😗*获取头部元素。
**pollFirst()😗*获取头部元素。
**getFirst()😗*获取头部元素。
**peekFirst()😗*获取头部元素。
//上述方法均和queue中方法一一对应。
//且queue中的方法,deque中均可用。
**getLast()😗*获取但不移除队列最后一个元素。
**offerFirst()😗*将指定元素插入队列开头。
**peekLast()😗*获取但不移除双端队列最后一个元素。
**pollLast()😗*获取并移除双端队列最后一个元素。
**pop()😗*从双端队列表示的堆栈 中弹出一个元素。
**push()😗*将一个元素推入双端队列表示的堆栈,即队列的头部。成功返回true,如果没有可用空间,抛出IllegalStateException。
**removeLast()😗*获取并移除移除双端队列最后一个元素。
**size()😗*返回双端队列元素数。
**isEmpty()😗*判断队列是否为空,为空返回true。
**remove(Object o)😗*从双端队列中移除第一次出现的指定元素。
实例代码:
public static void test02(){ Deque<String> deque = new LinkedList<>(); deque.offer("a"); deque.offer("b"); deque.offerFirst("c");//在队列头部进行插入 System.out.println(deque);//[c, a, b] deque.offerLast("d"); System.out.println(deque);//[c, a, b, d] String ret = deque.element();//返回第一个元素 System.out.println(ret);//c ret = deque.getFirst();//返回第一个元素 System.out.println(ret);//c ret = deque.getLast();//返回最后一个元素 System.out.println(ret);//d ret = deque.peek();//返回第一个元素,但不删除 System.out.println(ret);//c ret = deque.peekFirst();//返回第一个元素,但不删除 System.out.println(ret);//c ret = deque.peekLast();//返回最后一个元素,但不删除 System.out.println(ret);//d System.out.println(deque); ret = deque.poll();//返回第一个元素,删除 System.out.println(ret);//c System.out.println(deque);//[a, b, d] ret = deque.pop();//返回第一个元素,删除 System.out.println(ret);//a System.out.println(deque);//[b, d] deque.clear(); ret = deque.pop();//抛异常 System.out.println("11111"); ret = deque.poll();//返回null,但不抛异常 System.out.println("++"+ret); System.out.println("22222"); }
总结
加载全部内容