目錄
什么是隊列？
循環(huán)隊列
雙端隊列
阻塞隊列
隊列的應用場景
每日一練
什么是隊列？
在 上一篇文章 中講述了棧：先進后出就是棧，隊列剛好相反，先進先出的數(shù)據(jù)結構就是隊列，還是拿紙箱子來舉例：隊列可以理解為一個沒有底的紙箱子，往箱子里面放書，一本一本疊上去，但是全都從下面漏掉了，最先放進去的書就最先調出來。或者從字面意思來理解，隊列就像是生活中排隊買票一樣，排在前面的人先買到票，后面的人后買到票。
隊列主要包含兩個操作：入隊（在隊列尾部插入一個數(shù)據(jù)）和出隊（從隊列頭部刪除一個數(shù)據(jù)） ，和棧類似，隊列也是一種操作受限的線性表數(shù)據(jù)結構，隊列可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。
- 在使用數(shù)組實現(xiàn)的隊列中，入隊的時間復雜度是O(1)，出隊的時間復雜度是O(n)，查找元素的時間復雜度是O(n)。
- 在使用鏈表實現(xiàn)的隊列中，入隊和出隊的時間復雜度都是O(1)，查找元素的時間復雜度是O(n)。
隊列中需要定義兩個指針：一個是指向隊頭的head 指針，另一個是指向隊尾的 tail 指針。在二叉樹的層序遍歷 和 圖的廣度優(yōu)先搜索 算法中可以使用隊列來實現(xiàn)，后面再說。
下面是使用Go語言的數(shù)組實現(xiàn)隊列操作的代碼：
// go-algo-demo/queue/QueueArray.go
type ArrayQueue struct {
data []interface{} //存放隊列數(shù)據(jù)
capacity int //隊列容量
head int //對頭位置
tail int //隊尾位置
}
// 初始化隊列
func NewArrayQueue(n int) *ArrayQueue {
return &ArrayQueue{make([]interface{}, n), n, 0, 0}
}
// 入隊
func (this *ArrayQueue) Enqueue(v interface{}) bool {
if this.tail == this.capacity { //如果隊尾的位置和容量相等,說明隊列已滿
return false
}
this.data[this.tail] = v
this.tail++
return true
}
// 出隊
func (this *ArrayQueue) Dequeue() interface{} {
if this.head == this.tail { //如果隊頭的位置和隊尾的位置相等,說明隊列已空
return nil
}
v := this.data[this.head]
this.head++
return v
}
// 格式化輸出
func (this *ArrayQueue) String() string {
if this.head == this.tail {
return "empty queue"
}
result := ""
for i := this.head; i <= this.tail-1; i++ {
result += fmt.Sprintf("%v ", this.data[i])
}
return result
}
func main() {
queue := NewArrayQueue(5)
//嘗試給容量為5的隊列入隊6個元素,實際也只能入隊成功5個元素
queue.Enqueue(1)
queue.Enqueue(2)
queue.Enqueue(3)
queue.Enqueue(4)
queue.Enqueue(5)
queue.Enqueue(6)
fmt.Println(queue) //1 2 3 4 5
//出隊1個元素
queue.Dequeue()
fmt.Println(queue) // 2 3 4 5
//出隊3個元素
queue.Dequeue()
queue.Dequeue()
queue.Dequeue()
fmt.Println(queue) //5
//再把最后一個元素出隊
queue.Dequeue()
fmt.Println(queue) //empty queue
}上面代碼基于數(shù)組實現(xiàn)了一個隊列，由于數(shù)組的刪除操作會導致數(shù)組中的數(shù)據(jù)不連續(xù)，每次出隊操作都要刪除數(shù)組下標為 0 的數(shù)據(jù)，也就是要搬移下標為0后面的整個隊列中的數(shù)據(jù)，因此隊列出隊操作的時間復雜度是 O(n)。對于這個問題，可以采用如下優(yōu)化方案：在出隊的時候不搬移數(shù)據(jù)，而是把head指針往后移動一位，在入隊的時候判斷如果隊列中沒有空閑空間了，再集中觸發(fā)一次數(shù)據(jù)的搬移操作。比如下面圖中所示，將元素A從隊列中出隊，剩余的元素都不動，只把對頭指針往后移動一位。
循環(huán)隊列
把普通隊列的對頭和隊尾連接起來，就是一個循環(huán)隊列，就像是一個圓環(huán)一樣。使用循環(huán)隊列可以解決數(shù)組越界問題。在循環(huán)隊列中，最關鍵是要確定好隊空和隊滿的判定條件。
- 循環(huán)隊列新增元素時（即入隊操作），需要判斷隊列是否已滿，如果未滿則可以將新元素賦值給隊尾，然后讓tail指針向后移動一個位置；如果已經(jīng)排到了隊列的最后位置，則將tail指針重新指向頭部。
- 循環(huán)隊列刪除元素時（即出隊操作），需要判斷隊列是否為空，如果不為空則將隊頭元素賦值給返回值，然后讓head指針向后移動一個位置；如果已經(jīng)排到了隊列的最后位置，就把head指針重新指向頭部。?
包含n個元素的循環(huán)隊列中（假設容量為capacity），判斷循環(huán)隊列為空的條件是 head == tail，判斷隊列已滿有個規(guī)律如下：?(tail + 1) % capacity?= head，循環(huán)隊列已滿時，上面第三張圖中的 tail 指向的位置實際上是沒有存儲數(shù)據(jù)的，所以循環(huán)隊列會浪費一個數(shù)組的存儲空間。循環(huán)隊列的入隊操作和出隊操作的時間復雜度都是O(1)。
上面第三張圖的頭尾指針帶入 (tail + 1) % capacity?= head 的公式后，計算可得：(7+1)%8=0；再換一個位置，假如 head=3，tail=2，那么 (2+1)%8=3
其實還有一個辦法判斷循環(huán)隊列是否已滿，而且不需要浪費一個存儲空間，那就是定義一個可以容納k個元素的循環(huán)隊列，再多定義一個變量used（表示當前數(shù)組已存儲的數(shù)據(jù)容量），判斷used是否和k相等。但是考慮到在多線程編程中，控制變量越少越能最大可能實現(xiàn)無鎖編程，因此推薦上面浪費一個存儲空間而少定義一個變量的方式。另外，如果是使用鏈表實現(xiàn)的循環(huán)隊列中不存在這個問題。
使用Go語言實現(xiàn)一個循環(huán)隊列的核心代碼如下：
// go-algo-demo/queue/CycleQueue.go
// 隊列為空的條件: (head == tail) 為 true
func (this *CycleQueue) IsEmpty() bool {
if this.head == this.tail {
return true
}
return false
}
// 隊列已滿條件: ((tail+1)%capacity == head) 為 true
func (this *CycleQueue) IsFull() bool {
if this.head == (this.tail+1) % this.capacity {
return true
}
return false
}
// 入隊
func (this *CycleQueue) Enqueue(v interface{}) bool {
if this.IsFull() {
return false
}
this.queue[this.tail] = v
this.tail = (this.tail + 1) % this.capacity
return true
}
// 出隊
func (this *CycleQueue) Dequeue() interface{} {
if this.IsEmpty() {
return nil
}
v := this.queue[this.head]
this.head = (this.head + 1) % this.capacity
return v
}雙端隊列
雙端隊列，顧名思義就是 頭尾兩端都可以FIFO 入隊和出隊的隊列，入隊和出隊的時間復雜度都是O(1)。如下圖所示：
阻塞隊列
阻塞隊列是在隊列為空或者已滿的時候，讀取數(shù)據(jù)或者插入數(shù)據(jù)的特殊情況，具體情況如下：
- 當阻塞隊列為空的時候，因為此時隊列里面還沒有數(shù)據(jù)，如果從隊頭取數(shù)據(jù)會被阻塞，直到隊列中有了數(shù)據(jù)后才能返回；
- 當阻塞隊列已經(jīng)滿了，那么像隊列中插入數(shù)據(jù)就會阻塞，直到隊列中有空閑位置后才能成功插入數(shù)據(jù)；
根據(jù)上面兩個規(guī)則，可以發(fā)現(xiàn)阻塞隊列就是一個 “生產(chǎn)者——消費者模型”，使用這種數(shù)據(jù)結構可以有效地協(xié)調生產(chǎn)和消費的速度，當消費者消費數(shù)據(jù)的速度太慢，隊列就會很容易滿，然后生產(chǎn)者就阻塞等待，直到消費者消費了數(shù)據(jù)，生產(chǎn)者才會繼續(xù)生產(chǎn)。如果消費者消費的速度太慢，可以多配置幾個消費者來加快消費的速度，這樣的解決方案可以實現(xiàn)數(shù)據(jù)的削峰填谷。比較流行的消息隊列 kafka、rabbitmq 底層就是使用了這樣的原理。
舉個例子，比如有個家具廠（生產(chǎn)者）每天能生產(chǎn)100個沙發(fā)，但是一輛車（消費者）每天只能運輸20個沙發(fā)，要想不讓生產(chǎn)出來的沙發(fā)出現(xiàn)堆積，就應該增加到每天五輛車來運輸。
Redis中的 BRPOP和BLPOP 就是阻塞隊列，可以點擊?redis筆記03-鏈表和哈希_浮塵筆記的博客-CSDN博客 查看具體用法。
隊列的應用場景
對于大部分資源有限的場景，當沒有空閑資源時，基本上都可以通過“隊列”這種數(shù)據(jù)結構來實現(xiàn)請求排隊。比如某個線程池中已經(jīng)沒有了空閑線程，當新的任務請求線程資源時，可以選擇非阻塞的隊列，直接拒絕任務請求；也可以選擇阻塞隊列對新來的請求排隊，等到有空閑線程時再取出排隊的請求繼續(xù)處理。還有在操作系統(tǒng)上，CPU會根據(jù)同時請求的進程進行排隊，根據(jù)“先進先出”的原則，最先進入隊列的進程優(yōu)先執(zhí)行，然后再出隊。
- 基于鏈表實現(xiàn)的無界隊列（支持無限排隊），但是也可能會導致過多的請求排隊等待，請求處理的響應時間過長，這種方式不適合對響應時間要求比較高的系統(tǒng)；
- 基于數(shù)組實現(xiàn)的有界隊列（隊列的大小有限），當線程池中排隊的請求超過隊列大小時，后面新來的請求就會被拒絕，這種方式比較適合對響應時間要求比較高的系統(tǒng)，但是要注意設置一個合理的隊列大小。
每日一練
力扣26. 刪除有序數(shù)組中的重復項
給你一個 升序排列 的數(shù)組 nums ，請你 原地 刪除重復出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數(shù)。
示例：輸入：nums = [0,0,1,1,1,2,2,3,3,4]，輸出：5
生活例子：作品獲獎的人上臺領獎品，如果一個人獲得了多份獎，也只會領一份獎品。
方法1：因為已經(jīng)說了是排好序的數(shù)組，所以只需要不停判斷當前位置值和下一位置值是否相等。 若相等則pop掉當前值，否則move到下一位置繼續(xù)做判斷。時間復雜度是 O(n^2)，因為每一次pop操作都需要將被刪除元素后面的所有元素向前移動一格。
func removeDuplicates1(nums []int) (int, []int) {
idx := 0
for idx < len(nums)-1 {
if nums[idx] == nums[idx+1] {
nums = append(nums[:idx], nums[idx+1:]...) // 若相等則pop掉當前值
} else { // 否則move到下一位置繼續(xù)做判斷
idx += 1
}
}
return len(nums), nums
}
func main() {
fmt.Println(removeDuplicates1([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4})) //5 [0 1 2 3 4]
}方法2：不停地往后遍歷數(shù)組，同時自增地分配不重復的值給前面的位置，對于重復的直接跳過。時間復雜度就是O(n)。文章來源：http://www.zghlxwxcb.cn/news/detail-463032.html
func removeDuplicates2(nums []int) int {
idx := 0
for _, num := range nums {
// 如果是第一位數(shù),肯定不可能重復
// 為了保證數(shù)組不越界,因此要判斷 num != nums[idx-1]
if (idx < 1) || (num != nums[idx-1]) {
nums[idx] = num // 如果當前元素不是重復值，就將這個元素分配到目前不重復元素到達的index
idx += 1
}
}
return idx
}
func main() {
fmt.Println(removeDuplicates2([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4})) //5
}源代碼：https://gitee.com/rxbook/go-algo-demo/tree/master/queue文章來源地址http://www.zghlxwxcb.cn/news/detail-463032.html
到了這里，關于數(shù)據(jù)結構與算法04：隊列的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
