Common Definitions
First, let’s start with some definitions. In common usage of the word, a queue is FIFO (first-in-first-out). Just like the first person in line at the post office gets served first. A stack is LIFO (last in first out). Think of a stack of books – the last book you put on the stack is the first book you take off.
Choices in Java
In Java, things are a little more complicated, but the same principles apply. There is the aforementioned Queue interface which has the expected methods to add, remove and look at elements. (Actually, those methods come in two flavors: one throws an exception if the operation fails, the other returns a special value such as null or false; see more here).
There is also a sub-interface of Queue called Deque, short for “double ended queue” and is usually pronounced “deck”. This interface defines methods to access the elements at both ends of the collection. This functionality makes Deque a useful base for both queue and stack implementations.
However, both Queue and Deque are interfaces, so we still haven’t found a concrete implementation to use yet…
The shortlist: ArrayDeque & LinkedList
The 2 main choices are: ArrayDeque and LinkedList. There are a couple of other implementation of Deque such as ConcurrentLinkedDeque and LinkedBlockingDeque, and a plethora of implementations of Queue such as DelayQueue, LinkedBlockingDeque and PriorityQueue. Since those are more specialized (and I haven’t used them much), I won’t go into here.
ArrayDeque
From the javadocs, ArrayDeque is a resizable-array implementation of the Deque interface. Most ArrayDeque operations run in amortized constant time (i.e. slower “once in a while”, but on average constant) except for remove*, contains* and the bulk operations, all of which run in linear time. The docs point out that this class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. It is this statement that leads me to use ArrayDeque as my default implmentation for both stacks and queues.
LinkedList
The LinkedList class implements the List, Queue and Deque interfaces. In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.
LinkedList vs ArrayDeque
So, when would you use a LinkedList over an ArrayDeque?
Pros of a LinkedList implementation are:
- more flexible than the ArrayDeque implementation, as it
- implements all optional list operations.
- allows null elements (not allowed in ArrayDeque)
- well suited when you need to remove/insert items in the middle of the list frequently (something that can result in large array copies for the ArrayDeque).
Cons of a LinkedList implementation:
- not ideal when iterating over items in general
- consumes more memory than the ArrayDeque implementation
Overall
In terms of efficiency, ArrayDeque is more efficient than the LinkedList for iteration and add/remove operation at both ends. So, as the javadocs point out, in general, ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
相关推荐
mybatis 多层级collection嵌套
Collection集合
Denise Milani Video Collection
介绍了VB中集合,如何去何从建立集合对象的使用方法及实例操作
Collection集合简单测试 //添加元素c.add("孙悟空"); //删除指定元素c.remove(6);
前几天学习了collection的文档,里面主要是collection的基础知识,大神们自动忽略吧
C++ Collection.zip
java Collection类整理
UML files collection2
Collection使用
集合框架包含collection和map的子类。其中collection包含list、set和queue。map包括hashmap、hashtable和treemap
Collection接口中的常用方法的简单介绍
NULL 博文链接:https://jaychang.iteye.com/blog/2357143
Mesh Deformation Full Collection.unitypackage
具体数据量不一样,CPU和电脑不同,结果也不同。 Dictionary,加20万条,用时2371.5783毫秒 Collection,加20万条,用时1789.0249毫秒 Dictionary,读取20万条,用时2273毫秒 Collection,读取20万条,用时667毫秒 ...
通常所说的GCC是GUN Compiler Collection的简称,除了编译程序之外,它还含其他相关工具,所以它能把易于人类使用的高级语言编写的源代码构建成计算机能够直接执行的二进制代码。GCC是Linux平台下最常用的编译程序,...
IECollection
Delphi Examples Collection 3.0 This collection will help you to quickly and simply adopt and apply the knowledge of experienced programmers. What you will find here is a set of examples for most used ...
Collection 是所以集合的基类,该实例主要对Collection集合的成员函数的练习以及Iterator和foreach的遍历集合的练习,试用与java/C++ 新手。。
mybatis中mapper文件resultMap中collection和association的使用,参考地址:https://blog.csdn.net/zhizhuodewo6/article/details/82863452