4、ConcurrentLinkedQueue非阻塞無界鏈表隊(duì)列

ConcurrentLinkedQueue是一個(gè)線程安全的隊(duì)列，基于鏈表結(jié)構(gòu)實(shí)現(xiàn)，是一個(gè)無界隊(duì)列，理論上來說隊(duì)列的長度可以無限擴(kuò)大。

與其他隊(duì)列相同，ConcurrentLinkedQueue也采用的是先進(jìn)先出（FIFO）入隊(duì)規(guī)則，對元素進(jìn)行排序。 ? （推薦學(xué)習(xí)：java面試題目）

當(dāng)我們向隊(duì)列中添加元素時(shí)，新插入的元素會(huì)插入到隊(duì)列的尾部；而當(dāng)我們獲取一個(gè)元素時(shí)，它會(huì)從隊(duì)列的頭部中取出。

因?yàn)镃oncurrentLinkedQueue是鏈表結(jié)構(gòu)，所以當(dāng)入隊(duì)時(shí)，插入的元素依次向后延伸，形成鏈表；而出隊(duì)時(shí)，則從鏈表的第一個(gè)元素開始獲取，依次遞增；

值得注意的是，在使用ConcurrentLinkedQueue時(shí)，如果涉及到隊(duì)列是否為空的判斷，切記不可使用size()==0的做法，因?yàn)樵趕ize()方法中，是通過遍歷整個(gè)鏈表來實(shí)現(xiàn)的，在隊(duì)列元素很多的時(shí)候，size()方法十分消耗性能和時(shí)間，只是單純的判斷隊(duì)列為空使用isEmpty()即可。

public class ConcurrentLinkedQueueTest {<br/>    public static int threadCount = 10;<br/>    public static ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>();<br/>    static class Offer implements Runnable {<br/>        public void run() {<br/>            //不建議使用 queue.size()==0，影響效率。可以使用!queue.isEmpty()<br/>            if (queue.size() == 0) {<br/>                String ele = new Random().nextInt(Integer.MAX_VALUE) + "";<br/>                queue.offer(ele);<br/>                System.out.println("入隊(duì)元素為" + ele);<br/>            }<br/>        }<br/>    }<br/>    static class Poll implements Runnable {<br/>        public void run() {<br/>            if (!queue.isEmpty()) {<br/>                String ele = queue.poll();<br/>                System.out.println("出隊(duì)元素為" + ele);<br/>            }<br/>        }<br/>    }<br/>    public static void main(String[] agrs) {<br/>        ExecutorService executorService = Executors.newFixedThreadPool(4);<br/>        for (int x = 0; x < threadCount; x++) {<br/>            executorService.submit(new Offer());<br/>            executorService.submit(new Poll());<br/>        }<br/>        executorService.shutdown();<br/>    }<br/>}<br/>

一種輸出：

入隊(duì)元素為313732926<br/>出隊(duì)元素為313732926<br/>入隊(duì)元素為812655435<br/>出隊(duì)元素為812655435<br/>入隊(duì)元素為1893079357<br/>出隊(duì)元素為1893079357<br/>入隊(duì)元素為1137820958<br/>出隊(duì)元素為1137820958<br/>入隊(duì)元素為1965962048<br/>出隊(duì)元素為1965962048<br/>出隊(duì)元素為685567162<br/>入隊(duì)元素為685567162<br/>出隊(duì)元素為1441081163<br/>入隊(duì)元素為1441081163<br/>出隊(duì)元素為1627184732<br/>入隊(duì)元素為1627184732<br/>

ConcurrentLinkedQuere類圖

如圖ConcurrentLinkedQueue中有兩個(gè)volatile類型的Node節(jié)點(diǎn)分別用來存在列表的首尾節(jié)點(diǎn)，其中head節(jié)點(diǎn)存放鏈表第一個(gè)item為null的節(jié)點(diǎn)，tail則并不是總指向最后一個(gè)節(jié)點(diǎn)。

Node節(jié)點(diǎn)內(nèi)部則維護(hù)一個(gè)變量item用來存放節(jié)點(diǎn)的值，next用來存放下一個(gè)節(jié)點(diǎn)，從而鏈接為一個(gè)單向無界列表。

public ConcurrentLinkedQueue(){<br/>    head=tail=new Node<E>(null);<br/>}<br/>

如上代碼初始化時(shí)候會(huì)構(gòu)建一個(gè) item 為 NULL 的空節(jié)點(diǎn)作為鏈表的首尾節(jié)點(diǎn)。

Offer 操作offer 操作是在鏈表末尾添加一個(gè)元素，

下面看看實(shí)現(xiàn)原理。

public boolean offer(E e) {<br/>    //e 為 null 則拋出空指針異常<br/>    checkNotNull(e);<br/>    //構(gòu)造 Node 節(jié)點(diǎn)構(gòu)造函數(shù)內(nèi)部調(diào)用 unsafe.putObject，后面統(tǒng)一講<br/>    final Node<E> newNode = new Node<E>(e);<br/>    //從尾節(jié)點(diǎn)插入<br/>    for (Node<E> t = tail, p = t; ; ) {<br/>        Node<E> q = p.next;<br/>        //如果 q=null 說明 p 是尾節(jié)點(diǎn)則插入<br/>        if (q == null) {<br/>            //cas 插入（1）<br/>            if (p.casNext(null, newNode)) {<br/>                //cas 成功說明新增節(jié)點(diǎn)已經(jīng)被放入鏈表，然后設(shè)置當(dāng)前尾節(jié)點(diǎn)（包含 head，1，3，5.。。個(gè)節(jié)點(diǎn)為尾節(jié)點(diǎn)）<br/>                if (p != t)// hop two nodes at a time<br/>                    casTail(t, newNode); // Failure is OK. return true;<br/>            }<br/>            // Lost CAS race to another thread; re-read next<br/>        } else if (p == q)//(2)<br/>            //多線程操作時(shí)候，由于 poll 時(shí)候會(huì)把老的 head 變?yōu)樽砸茫缓?head 的 next 變?yōu)樾?head，所以這里需要<br/>            //重新找新的 head，因?yàn)樾碌?head 后面的節(jié)點(diǎn)才是激活的節(jié)點(diǎn)<br/>            p = (t != (t = tail)) ? t : head;<br/>        else<br/>            // 尋找尾節(jié)點(diǎn)(3)<br/>            p = (p != t && t != (t = tail)) ? t : q;<br/>    }<br/>}<br/>

從構(gòu)造函數(shù)知道一開始有個(gè)item為null的哨兵節(jié)點(diǎn)，并且head和tail都是指向這個(gè)節(jié)點(diǎn)。

以上是java多線程和并發(fā)面試題目（第4題，附答案）的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！