关于Deque,之前我的总结是,如果要当作Stack使用,则stick to Stack methods,比如push, pop, peek。如果当作Queue使用,则stick to Queue method,比如add/offer, poll/remove, peek。在实现上,我一般使用的是ArrayDeque, a resizable double-ended array。
今天突然想到一个问题,用Deque实现的Queue或者Stack,在使用enhanced for loop的时候,Java是怎么知道元素弹出的正确顺序呢? 或者如果混用Queue和Stack的方法,peek会弹出什么结果?iterator会给出什么顺序的结果呢?
我们来看看ArrayDeque的源码:
1 | transient int head; |
这里有2个pointers, head和tail,当arraydeque是empty的时候,head和tail重叠。
对于push来说,移动的是head,head的值减1再使用,并且用的是modulus circularly decrement。
1 | /** |
对于add/offer来说,tail的值用了再加1,并且用的是modulus circularl increment。
1 | /** |
peek总是从head pointer取值
1 | /** |
iterator总是从head pointer -> tail pointer
1 | /** |
所以现在情形就很清楚了,来看一个例子。首先按照顺序push [1 2 3], 这时peek是3,然后再add/offer [4 5 6], 这时peek还是3,然后iterator的结果是: [3 2 1 4 5 6]
1 | Deque<Integer> dq = new ArrayDeque<>(); |