隊(duì)列特性
1.基于數(shù)組：順序隊(duì)列。
2.基于鏈表：鏈?zhǔn)疥?duì)列。
對(duì)比隊(duì)列和棧
1.棧只需要一個(gè)棧頂指針。
2.隊(duì)列需要一個(gè)head指針和一個(gè)tail指針。
基于數(shù)組的隊(duì)列
1.每次出隊(duì)，需要搬移數(shù)據(jù)保證連續(xù)性。對(duì)此的優(yōu)化方案：在入隊(duì)的時(shí)候無(wú)空間可用，再集中搬移一次數(shù)據(jù)。
對(duì)比隊(duì)列學(xué)習(xí)循環(huán)隊(duì)列
1.基于數(shù)組的隊(duì)列在tail==n時(shí)會(huì)觸發(fā)數(shù)據(jù)搬移操作。影響入隊(duì)操作。
2.循環(huán)隊(duì)列可以避免數(shù)據(jù)搬移操作。
循環(huán)隊(duì)列難點(diǎn)
1.判斷邊界條件
對(duì)滿(mǎn)條件：(tail+1)%n=head 注意：隊(duì)滿(mǎn)的時(shí)候，tail指向的位置沒(méi)有數(shù)據(jù)。所以循環(huán)鏈表會(huì)浪費(fèi)一個(gè)數(shù)組的存儲(chǔ)空間。
對(duì)空條件：head==tail
阻塞隊(duì)列
1.在隊(duì)列基礎(chǔ)上加入阻塞操作。（生產(chǎn)者消費(fèi)者模式）
2.在生產(chǎn)者消費(fèi)者模式中，如果一個(gè)生產(chǎn)者對(duì)應(yīng)多個(gè)消費(fèi)者。在這種多線(xiàn)程環(huán)境下會(huì)出現(xiàn)線(xiàn)程安全問(wèn)題。
IMG_1548.JPG
并發(fā)隊(duì)列
1.線(xiàn)程安全的隊(duì)列叫做并發(fā)隊(duì)列。
2.最簡(jiǎn)單的方式是在入隊(duì)、出隊(duì)操作上加鎖。這會(huì)導(dǎo)致鎖的粒度大并發(fā)低。同一時(shí)刻只允許一個(gè)存或者取操作?；跀?shù)組的循環(huán)隊(duì)列，利用CAS原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列。
應(yīng)用：線(xiàn)程池中拒絕策略。
1.非阻塞方式，直接拒絕。
2.阻塞方式，請(qǐng)求排隊(duì)。
阻塞方式：
1.基于鏈表：可實(shí)現(xiàn)無(wú)限排隊(duì)無(wú)界隊(duì)列。請(qǐng)求過(guò)多會(huì)導(dǎo)致響應(yīng)時(shí)間過(guò)長(zhǎng)，對(duì)于響應(yīng)時(shí)間敏感的系統(tǒng)，基于鏈表實(shí)現(xiàn)無(wú)限排隊(duì)的線(xiàn)程池是不合適的。
2.基于數(shù)組：有界隊(duì)列，超過(guò)隊(duì)列大小會(huì)拒絕。對(duì)時(shí)間敏感的系統(tǒng)合理。設(shè)置一個(gè)合理大小的隊(duì)列很有講究。
規(guī)范.png
參考書(shū)阿里巴巴規(guī)范：https://github.com/alibaba/p3c/blob/master/%E9%98%BF%E9%87%8C%E5%B7%B4%E5%B7%B4Java%E5%BC%80%E5%8F%91%E6%89%8B%E5%86%8C%EF%BC%88%E8%AF%A6%E5%B0%BD%E7%89%88%EF%BC%89.pdf
