當(dāng)前的Go庫不提供隊(duì)列容器。為了實(shí)現(xiàn)一個(gè)簡單的隊(duì)列，我使用圓形數(shù)組作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。它遵循TAOCP中提到的算法：Insert Y into queue X: X[R]<-Y; R<-(R+1)%M; if R=F then OVERFLOW.Delete Y from queue X: if F=R then UNDERFLOW; Y<-X[F]; F<-(F+1) % M.F: Front, R: Rear, M: Array length.以下是代碼：package mainimport ( "fmt")type Queue struct { len int head, tail int q []int}func New(n int) *Queue { return &Queue{n, 0, 0, make([]int, n)} }func (p *Queue) Enqueue(x int) bool { p.q[p.tail] = x p.tail = (p.tail + 1) % p.len return p.head != p.tail}func (p *Queue) Dequeue() (int, bool) { if p.head == p.tail { return 0, false } x := p.q[p.head] p.head = (p.head + 1) % p.len return x, true}func main() { q := New(10) for i := 1; i < 13; i++ { fmt.Println(i, q.Enqueue(i)) } fmt.Println() for i := 1; i < 13; i++ { fmt.Println(q.Dequeue()) } }但是輸出顯然是錯(cuò)誤的：1是2是3是4是5是6是7是8是9是10是11是12是11是12是0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤0錯(cuò)誤我認(rèn)為我還需要一個(gè)領(lǐng)域來使代碼正常工作。你有什么建議？改進(jìn)的代碼有一個(gè)小的缺點(diǎn)：大小為n的數(shù)組只能包含n-1個(gè)元素。package mainimport ( "fmt")type Queue struct { len int head, tail int q []int}func New(n int) *Queue { return &Queue{n, 0, 0, make([]int, n)} }func (p *Queue) Enqueue(x int) bool { p.q[p.tail] = x ntail := (p.tail + 1) % p.len ok := false if ntail != p.head { p.tail = ntail ok = true } return ok}func (p *Queue) Dequeue() (int, bool) { if p.head == p.tail { return 0, false } x := p.q[p.head] p.head = (p.head + 1) % p.len return x, true}func main() { q := New(10) for i := 1; i < 13; i++ { fmt.Println(i, q.Enqueue(i)) } fmt.Println() for i := 1; i < 13; i++ { fmt.Println(q.Dequeue()) } }
3 回答
慕森王
TA貢獻(xiàn)1777條經(jīng)驗(yàn) 獲得超3個(gè)贊
當(dāng)Enqueue失敗時(shí)，您仍會(huì)增加p.tail，因此下一次它似乎不會(huì)失敗-這就解釋了false第一個(gè)循環(huán)中的單個(gè)（并弄亂了第二個(gè)循環(huán)中的所有內(nèi)容）。原始算法說的OVERFLOW意思是“放棄一切”，而不是“只是繼續(xù)前進(jìn)，就好像什么都沒發(fā)生一樣” ；-)。
p.tail如果您已檢查是否發(fā)生了故障，那么您所需要做的就是遞減-或?qū)⑦f增的值放在本地臨時(shí)文件中，然后p.tail僅在未發(fā)生故障時(shí)才將其移動(dòng)到，這可能會(huì)更優(yōu)雅。這樣一來，否則Enqueue就不會(huì)排隊(duì)新的價(jià)值，但本身隊(duì)列（而沒有溢出值）仍是語義完整和正確的未來運(yùn)營。
米琪卡哇伊
TA貢獻(xiàn)1998條經(jīng)驗(yàn) 獲得超6個(gè)贊
在任何合理的go版本（1.x之后）中，您都不需要所有這些麻煩。一切都可以通過切片來實(shí)現(xiàn)。
queue := []int{}
添加到隊(duì)列：
queue = append(queue, 6)
從隊(duì)列中彈出：
el := queue[0]
queue = queue[1:]
這是一個(gè)實(shí)現(xiàn)，它顯示pop并不需要花費(fèi)很多時(shí)間（實(shí)際上，這里的時(shí)間比push短，因?yàn)槲艺J(rèn)為隊(duì)列增長時(shí)會(huì)重新分配內(nèi)存）。
package main
import (
"fmt"
"time"
)
func main() {
n := 10000000
queue := []int{1, 2, 3}
start := time.Now()
for i := 0; i < n; i++ {
queue = append(queue, i)
}
elapsed := time.Since(start)
fmt.Println(elapsed)
start = time.Now()
for i := 0; i < n; i++ {
_ = queue[0]
queue = queue[1:]
}
elapsed = time.Since(start)
fmt.Println(elapsed)
fmt.Println(queue)
}
在我的機(jī)器上，數(shù)字為：
216.611664ms
13.441106ms
來自@DaveC的評(píng)論：
這很簡單，并且對(duì)所有其他情況都非常有效，除了關(guān)鍵代碼（不需要分配（對(duì)垃圾回收器施加壓力）是不受歡迎的）之外，有兩點(diǎn)要注意，首先，它確實(shí)會(huì)在push時(shí)（盡管有效，而不是在每次調(diào)用時(shí)）重新分配底層數(shù)組。而pop不會(huì)釋放任何空間，直到發(fā)生這種情況。這導(dǎo)致第二件事，如果（通常）隊(duì)列包含指向某個(gè)對(duì)象的指針，那么最好將queue [0] = nil; queue = queue [1：]使隊(duì)列立即停止引用指針。
- 3 回答
- 0 關(guān)注
- 297 瀏覽
添加回答
舉報(bào)
0/150
提交
取消