如何在Go中使用循環數組正確實現隊列？

如何在 Go 中實現隊列

本題探討了使用循環數組作為底層資料在 Go 中實現簡單隊列結構。該方法遵循“電腦程式設計的藝術”中概述的演算法。然而，最初提出的程式碼遇到了輸出不正確的問題。

理解差異

程式碼的主要問題在於缺乏處理錯誤的機制佇列已滿的情況。圓形陣列方法需要一種方法來確定何時達到容量。原始程式碼缺少此檢查，導致嘗試覆蓋數組末尾之外的元素。

完善實作

要解決此問題，只需進行簡單的修改被介紹。 Enqueue 函數現在包含一個條件來驗證尾索引是否不等於頭索引。如果它們相等，則隊列已滿，並且函數傳回 false。否則，它將元素添加到佇列中，增加尾部索引，並傳回 true。

改進的程式碼

以下是更新的程式碼：

package main

import (
    "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
    if ntail != p.head {
        p.tail = ntail
        return true
    }
    return false
}

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())
    }
}

透過此修改，程式碼可以正確處理入隊和出隊元素，從而產生預期的結果輸出：

1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
10 true
11 true
12 true

11 true
12 true
1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
10 true

以上是如何在Go中使用循環數組正確實現隊列？的詳細內容。更多資訊請關注PHP中文網其他相關文章！