為什么要用雙端隊列呢？單向隊列我感覺也可以實現(xiàn)功能，因為大部分的查找只是查找后繼節(jié)點，或者是判斷當(dāng)前節(jié)點的前驅(qū)是不是head。另外，同步器維護的waiter的node到底是什么作用？源碼的注釋是為了指向condition的waiter節(jié)點，但是沒有特別看明白。
1 回答
千巷貓影
TA貢獻1829條經(jīng)驗 獲得超7個贊
很明顯嘛，假如你的隊列是單向的如：Head -> N1 -> N2 -> Tail。出隊的時候你要獲取N1很簡單，Head.next就行了，入隊你就麻煩了，你要遍歷整個鏈表到N2，然后N2.next = N3;N3.next = Tail。入隊的復(fù)雜度就是O(n),而且Tail也失去他的意義。相反雙向鏈表出隊和入隊都是O(1)時間復(fù)雜度。說白了空間換時間。
- 1 回答
- 0 關(guān)注
- 2513 瀏覽
添加回答
舉報
0/150
提交
取消