スライスと循環バッファを使用して Go でキューを効率的に実装するにはどうすればよいですか?

Go でキューを実装するにはどうすればよいですか?

Go では、標準ライブラリは組み込みのキュー コンテナを提供しません。この記事では、基礎となるデータ構造としてスライスを使用して Go でキューを実装する別のアプローチを紹介します。

キューの作成

キューを作成するには、空のスライス:

queue := []int{}

エンキュー中要素

要素をキューに追加するには、要素をスライスの最後に追加します。

queue = append(queue, 6)

要素のデキュー

キューから要素を削除するには、スライスの最初の要素を変数に代入し、次を使用して削除します。 slicing:

el := queue[0]
queue = queue[1:]

パフォーマンスに関する考慮事項

スライスベースのキューは実装が簡単ですが、いくつかの制限があります。エンキュー操作ごとに基になる配列の再割り当てが必要ですが、キューが大きい場合は非効率になる可能性があります。

この問題を軽減するには、循環バッファ実装を使用できます。循環バッファでは、要素はバッファ内の所定の位置に追加および削除され、コストのかかる配列の再割り当ての必要性を回避します。

サンプル コード

例は次のとおりです。循環バッファ実装の:

package main

import (
    "fmt"
)

// Queue represents a circular buffer queue.
type Queue struct {
    buf []int
    head int
    tail int
}

// NewQueue creates a new queue with the given buffer size.
func NewQueue(size int) *Queue {
    return &Queue{make([]int, size), 0, 0}
}

// Enqueue adds an element to the queue.
func (q *Queue) Enqueue(v int) {
    q.buf[q.tail] = v
    q.tail = (q.tail + 1) % len(q.buf)
}

// Dequeue removes and returns the oldest element from the queue.
func (q *Queue) Dequeue() int {
    v := q.buf[q.head]
    q.head = (q.head + 1) % len(q.buf)
    return v
}

この実装は、特に大規模なバッファのエンキュー/デキュー操作のパフォーマンスを向上させます。キュー。

以上がスライスと循環バッファを使用して Go でキューを効率的に実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。