一、是什么
一種先進先出的線性表數(shù)據(jù)結(jié)構(gòu)，只支持入隊和出隊操作
二、使用場景
-
MySQL連接池 -
Redis單線程特性 - 分布式消息隊列
三、工作原理
隊尾插入元素，隊頭刪除元素
四、隊列類型
-
順序隊列：
數(shù)組實現(xiàn)的就是順序隊列（有數(shù)據(jù)搬移操作） -
循環(huán)隊列：
將數(shù)組的首尾相連，形成一個環(huán)（沒有數(shù)據(jù)搬移操作） -
阻塞隊列：
當隊列為空時，從隊頭取數(shù)據(jù)會被阻塞；當隊列已滿時，插入數(shù)據(jù)的操作將被阻塞，形成一個生產(chǎn)者-消費者模型。 -
并發(fā)隊列：
在多線程情況下， 會有多個線程同時操作隊列，此時如果是線程安全的隊列我們就叫作并發(fā)隊列。一般使用CAS（類似樂觀鎖）和鎖來實現(xiàn)并發(fā)隊列。
四、實現(xiàn)
-
代碼實現(xiàn)
type list []int
func NewList() *list {
newList := make(list, 0)
return &newList
}
func listPush(newList *list, a ...int) {
*newList = append(*newList, a...)
}
func listPop(newList *list) (listObj int) {
length := len(*newList)
if length <= 0 {
return
}
listObj = (*newList)[0]
*newList = (*newList)[1:length]
return
}
-
Redis實現(xiàn)
rpush + lpop = list（隊列）
五、優(yōu)劣
- 優(yōu)點：
- 不涉及到數(shù)組搬移時，出隊和入隊的時間復雜度都為
O(1) - 操作受限，使用比較可控，不容易出錯（和數(shù)組、鏈表相比較）
- 缺點：
- 在內(nèi)存中，隊列結(jié)構(gòu)里的數(shù)據(jù)大小和生命周期是固定的，缺乏靈活性
六、替代性技術(shù)
- 數(shù)組
- 鏈表
- 棧
