go - キューの実装はありますか?

Question

シンプルで高速な FIF/キュー用の Go コンテナーを提案できる人はいますか? Go には、 と の 3 つの異なるコンテナーheapがlistありvectorます。キューの実装に適しているのはどれですか?

Answer 1

実際、基本的で使いやすい fifo キューが必要な場合は、スライスが必要なすべてを提供します。

queue := make([]int, 0)
// Push to the queue
queue = append(queue, 1)
// Top (just get next element, don't remove it)
x = queue[0]
// Discard top element
queue = queue[1:]
// Is empty ?
if len(queue) == 0 {
    fmt.Println("Queue is empty !")
}

もちろん、無用なサイズ変更と再割り当てを避けるために、追加とスライスの内部実装を信頼できると思います。基本的な使い方であれば、これで十分です。

Answer 2

ベクトルまたはリストのいずれかが機能するはずですが、おそらくベクトルが適しています。ベクトルはおそらくリストよりも少ない頻度で割り当てられ、(現在の Go 実装では) ガベージ コレクションはかなり高価であるため、私はこれを言います。ただし、小さなプログラムでは、おそらく問題にはなりません。

Answer 3

実装側を拡張するために、Moraesは彼の要点でキューとスタックからいくつかの構造体を提案します。

// Stack is a basic LIFO stack that resizes as needed.
type Stack struct {
    nodes   []*Node
    count   int
}
// Queue is a basic FIFO queue based on a circular list that resizes as needed.
type Queue struct {
    nodes   []*Node
    head    int
    tail    int
    count   int
}

この遊び場の例で実際に動作しているのを見ることができます。

Answer 4

type Queue struct {
    slice []int
    len   int
}
func newq() Queue {
    q := Queue{}
    q.slice = make([]int, 0)
    q.len = 0
    return q
}
func (q *Queue) Add(v int) {
    q.slice = append(q.slice, v)
    q.len++
}

func (q *Queue) PopLeft() int {
    a := q.slice[0]
    q.slice = q.slice[1:]
    q.len--
    return a
}
func (q *Queue) Pop() int {
    a := q.slice[q.len-1]
    q.slice = q.slice[:q.len-1]
    q.len--
    return a
}

基本的な必要性については、上記のコードで十分です

Answer 5

ダブルスタックの実装:

O(1) Enqueueand Dequeueand uses slices(これは、キャッシュ ミスに適している傾向があります)。

type Queue struct{
    enqueue, dequeue Stack
}

func (q *Queue) Enqueue(n *Thing){
    q.enqueue.Push(n)
}

func (q *Queue) Dequeue()(*Thing, bool){
    v, ok := q.dequeue.Pop()
    if ok{
        return v, true
    }

    for {
        v, ok := d.enqueue.Pop()
        if !ok{
            break
        }

        d.dequeue.Push(v)
    }

    return d.dequeue.Pop()
}

type Stack struct{
    v []*Thing
}

func (s *Stack)Push(n *Thing){
    s.v=append(s.v, n)
}

func (s *Stack) Pop()(*Thing, bool){
    if len(s.v) == 0 {
        return nil, false
    }

    lastIdx := len(s.v)-1
    v := s.v[lastIdx]
    s.v=s.v[:lastIdx]
    return v, true
}