万维网网站注册,做网站很忙吗,linux网站管理面板,wordpress的样式表目录 Java中的Stack类 不用Stack有以下两点原因 1、从性能上来说应该使用Deque代替Stack。 2、Stack从Vector继承是个历史遗留问题#xff0c;JDK官方已建议优先使用Deque的实现类来代替Stack。 该用ArrayDeque还是LinkedList#xff1f; ArrayDeque与LinkList区别#xff1… 目录 Java中的Stack类 不用Stack有以下两点原因 1、从性能上来说应该使用Deque代替Stack。 2、Stack从Vector继承是个历史遗留问题JDK官方已建议优先使用Deque的实现类来代替Stack。 该用ArrayDeque还是LinkedList ArrayDeque与LinkList区别 ArrayDeque LinkList 结论 API积累 Deque中常用方法: 把Deque当栈用的时候 把Deque当队列用的时候 从上面(头部)插入 从上面(头部)出来/观察: 从下面(尾部)插入 从下面(尾部)出来/观察: Java中的Stack类
Java中Stack类从Vector类继承底层是用数组实现的线程安全的栈。栈是一种后进先出(LIFO)的容器常用的操作push/pop/peek。
不过Java中用来表达栈的功能push/pop/peek更适用的是使用双端队列接口Deque并用实现类ArrayDeque / LinkedList来进行初始化。
DequeInteger stack new ArrayDeque();
DequeInteger stack new LinkedList();不用Stack有以下两点原因
1、从性能上来说应该使用Deque代替Stack。 Stack和Vector都是线程安全的其实多数情况下并不需要做到线程安全因此没有必要使用Stack。毕竟保证线程安全需要上锁有额外的系统开销。 2、Stack从Vector继承是个历史遗留问题JDK官方已建议优先使用Deque的实现类来代替Stack。 Stack从Vector继承的一个副作用是暴露了set/get方法可以进行随机位置的访问这与Stack只能从尾巴上进行增减的本意相悖。 此外Deque在转成ArrayList或者stream的时候保持了“后进先出”的语义而Stack因为是从Vector继承没有这个语义。 StackInteger stack new Stack();
DequeInteger deque new ArrayDeque();stack.push(1);
stack.push(2);
deque.push(1);
deque.push(2);System.out.println(new ArrayList(stack)); // [1,2]
ListInteger list1 stack.stream().collect(Collectors.toList());//[1,2]// deque转成ArrayList或stream时保留了“后进先出”的语义
System.out.println(new ArrayList(deque)); // [2,1]
ListInteger list2 deque.stream().collect(Collectors.toList());//[2,1]该用ArrayDeque还是LinkedList
ArrayDeque和LinkedList这两者底层一个采用数组存储一个采用链表存储
ArrayDeque与LinkList区别
ArrayDeque
数组结构插入元素不能为null无法确定数据量时后期扩容会影响效率
LinkList
链表结构插入元素能为null无法确定数据量时有更好表现 PS这两者既可当成栈仅支持在尾部加入或移除元素使用也可当成双端队列使用即可以在队列的两端头或尾将元素加入或移除。 单次加入/移除元素的平均时间复杂度均为O(1)。 那么问题来了在用作栈时到底用ArrayDeque好还是LinkedList好呢 注意到ArrayDeque源码注释中有一句话 This class is likely to be faster than {link Stack} when used as a stack, and faster than {link LinkedList} when used as a queue. ArrayDeque用作栈时比Stack快没有疑问用作队列的时候似乎也会比LinkedList快
笔者经过50W数据量的测试发现两者性能基本接近ArrayDeque平均耗时在18-24msLinkedList耗时平均在20-28ms。
如果数据量上升到100W的话ArrayDeque的优势会更明显。
结论ArrayDeque会略胜一筹不过差别通常可以忽略
public static void main(String[] args) {int length 500000;int max length;// 生成一个长度为length值从1~max的随机数组int[] data new RandomIntArray(length,1,length,max).next();int loopCount 10;long t1, t2;t1 System.currentTimeMillis();for (int i 0; i loopCount; i) {// testArrayDeque(data);testLinkedList(data);}t2 System.currentTimeMillis();// 测试loopCount次取平均结果System.out.println(timeTaken: String.format(%.1f, (t2-t1)/(double)loopCount));
}public static void testArrayDeque(int[] data) {int length data.length;DequeInteger stack new ArrayDeque();for (int i 0; i length/2; i) {stack.push(data[i]);stack.push(data[i1]);stack.pop();stack.push(stack.peek()1);}
}public static void testLinkedList(int[] data) {int length data.length;DequeInteger stack new LinkedList();for (int i 0; i length/2; i) {stack.push(data[i]);stack.push(data[i1]);stack.pop();stack.push(stack.peek()1);}
}结论
ArrayDeque会略胜一筹不过差别通常可以忽略。 经过性能对比笔者更倾向于使用ArrayDeque来表达Java中的栈功能。 API积累
Deque中常用方法:
以这2个为基础整出来的Deque除了结构不一样方法都一样的。
把Deque当栈用的时候
入栈push(E e)出栈poll() / pop() 后者在栈空的时候会抛出异常前者返回null查看栈顶peek() 为空时返回null
把Deque当队列用的时候
入队offer(E e)出队poll() 为空时返回null查看队首peek() 为空时返回null 有些时候需要进行一些骚操作的时候比如取得栈底元素取得队尾元素这些常规操作就不能满足了。 下面就是Deque中一些更详细的方法。
从上面(头部)插入
方法名作用void addFirst(E e)将指定的元素插入此双端队列的前面 空间不足抛异常boolean offerFirst(E e)将指定的元素插入此双端队列的前面 空间不足插入失败返回回falsevoid push(E e)将指定的元素插入此双端队列的前面 空间不足抛异常
从上面(头部)出来/观察:
方法名作用E removeFirst()检索并删除第一个元素为空时抛出异常E remove()和removeFirst一样 检索并删除第一个元素为空时抛出异常E pop()和removeFirst一样 检索并删除第一个元素为空时抛出异常E pollFirst()检索并删除第一个元素 为空时返回nullE poll()和pollFirst一样 检索并删除第一个元素 为空时返回nullE getFirst()只看看第一个元素 不出来为空就抛异常E element()和getFirst一样 只看看第一个元素 不出来为空就抛异常E peekFirst()只看看第一个元素 不出来为空时返回nullE peek()和peekFirst一样 只看看第一个元素 不出来为空时返回null
从下面(尾部)插入
方法名作用void addLast(E e)将指定的元素插入此双端队列的后面 空间不足抛异常boolean offerLast(E e)将指定的元素插入此双端队列的后面空间不足返回falseboolean add(E e)将指定的元素插入此双端队列的后面空间不足抛异常boolean offer(E e)将指定的元素插入此双端队列的后面空间不足返回false
从下面(尾部)出来/观察:
方法名作用E removeLast()检索并删除最后一个元素为空时抛出异常E pollLast()检索并删除最后一个元素 为空时返回nullE getLast()只看看最后一个元素 不出来为空就抛异常E peekLast()只看看最后一个元素 不出来为空时返回null
