隊列特性
1.基于數(shù)組：順序隊列。
2.基于鏈表：鏈?zhǔn)疥犃小?對比隊列和棧
1.棧只需要一個棧頂指針。
2.隊列需要一個head指針和一個tail指針。
基于數(shù)組的隊列
1.每次出隊，需要搬移數(shù)據(jù)保證連續(xù)性。對此的優(yōu)化方案：在入隊的時候無空間可用，再集中搬移一次數(shù)據(jù)。
對比隊列學(xué)習(xí)循環(huán)隊列
1.基于數(shù)組的隊列在tail==n時會觸發(fā)數(shù)據(jù)搬移操作。影響入隊操作。
2.循環(huán)隊列可以避免數(shù)據(jù)搬移操作。
循環(huán)隊列難點
1.判斷邊界條件
對滿條件：(tail+1)%n=head 注意：隊滿的時候，tail指向的位置沒有數(shù)據(jù)。所以循環(huán)鏈表會浪費一個數(shù)組的存儲空間。
對空條件：head==tail
阻塞隊列
1.在隊列基礎(chǔ)上加入阻塞操作。（生產(chǎn)者消費者模式）
2.在生產(chǎn)者消費者模式中，如果一個生產(chǎn)者對應(yīng)多個消費者。在這種多線程環(huán)境下會出現(xiàn)線程安全問題。
IMG_1548.JPG
并發(fā)隊列
1.線程安全的隊列叫做并發(fā)隊列。
2.最簡單的方式是在入隊、出隊操作上加鎖。這會導(dǎo)致鎖的粒度大并發(fā)低。同一時刻只允許一個存或者取操作。基于數(shù)組的循環(huán)隊列，利用CAS原子操作，可以實現(xiàn)非常高效的并發(fā)隊列。
應(yīng)用：線程池中拒絕策略。
1.非阻塞方式，直接拒絕。
2.阻塞方式，請求排隊。
阻塞方式：
1.基于鏈表：可實現(xiàn)無限排隊無界隊列。請求過多會導(dǎo)致響應(yīng)時間過長，對于響應(yīng)時間敏感的系統(tǒng)，基于鏈表實現(xiàn)無限排隊的線程池是不合適的。
2.基于數(shù)組：有界隊列，超過隊列大小會拒絕。對時間敏感的系統(tǒng)合理。設(shè)置一個合理大小的隊列很有講究。
規(guī)范.png
