ホームページ > バックエンド開発 > Golang > 循環配列を使用して Go でキューを正しく実装するにはどうすればよいですか?

循環配列を使用して Go でキューを正しく実装するにはどうすればよいですか?

Mary-Kate Olsen
リリース: 2024-11-28 11:39:18
オリジナル
969 人が閲覧しました

How to Correctly Implement a Queue in Go Using a Circular Array?

Go でキューを実装する方法

この質問では、基になるデータとして循環配列を使用した Go での単純なキューの実装について説明します。構造。このアプローチは、「The Art of Computer Programming」で概説されているアルゴリズムに従います。ただし、提示された最初のコードでは、出力が正しくないという問題が発生しました。

矛盾を理解する

このコードの主な問題は、矛盾を処理するメカニズムが欠如していることです。キューがいっぱいの状況。円形アレイのアプローチでは、いつ容量に達したかを判断する方法が必要です。元のコードにはこのチェックが欠けていたため、配列の末尾を超えて要素を上書きしようとしました。

実装の改良

この問題を解決するには、簡単な変更を加えます。が紹介されています。 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 中国語 Web サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート