Y a-t-il une implémentation de file d'attente ?

Question

Est-ce que quelqu'un peut suggérer un conteneur Go pour une file d'attente simple et rapide, Go a 3 conteneurs différents: heap, list et vector. Lequel est le plus adapté pour mettre en œuvre une file d'attente?

Answer 1

Implémentation de double pile :

O(1) Enfile et defile et utilise des tranches (qui tendent à être meilleures pour les ratés de cache).

type File struct{
    enfile, defile Pile
}

func (f *File) Enfile(n *Chose){
    f.enfile.Pousse(n)
}

func (f *File) Defile()(*Chose, bool){
    v, ok := f.defile.Pop()
    if ok{
        return v, true
    }

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

        f.defile.Push(v)
    }

    return f.defile.Pop()
}

type Pile struct{
    v []*Chose
}

func (p *Pile)Pousse(n *Chose){
    p.v=append(p.v, n)
}

func (p *Pile) Pop()(*Chose, bool){
    if len(s.v) == 0 {
        return nil, false
    }

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

Answer 2

La manière la plus simple d'implémenter la structure de données de file en Golang est d'utiliser une slice.

Étant donné qu'une file suit une structure FIFO (First-In-First-Out), les opérations de défilement et d'enfilement peuvent être effectuées comme suit:

• Utiliser la fonction intégrée append pour enfiler.
• Retirer le premier élément pour défiler.

Le code suivant implémente une file de base en utilisant une slice. Remarquez comment l'enfilement et le défilement se produisent aux extrémités opposées de la slice.

package main
import "fmt"

func enqueue(queue[] int, element int) []int {
  queue = append(queue, element); // Simplement appender pour enfiler.
  fmt.Println("Enfilé:", element);
  return queue
}

func dequeue(queue[] int) ([]int) {
  element := queue[0]; // Le premier élément est celui à défiler.
  fmt.Println("Défilé:", element)
  return queue[1:]; // Retirer l'élément une fois qu'il est défilé.
}

func main() {
  var queue[] int; // Faire une file d'entiers.

  queue = enqueue(queue, 10);
  queue = enqueue(queue, 20);
  queue = enqueue(queue, 30);

  fmt.Println("File:", queue);

  queue = dequeue(queue);
  fmt.Println("File:", queue);

  queue = enqueue(queue, 40);
  fmt.Println("File:", queue);
}

Avertissement(fuites mémoire): Dans la fonction de défilement ci-dessus, la mémoire allouée pour le premier élément dans le tableau n'est jamais retournée.

Nous pouvons utiliser une structure de données dynamique (liste chaînée) afin d'éviter les fuites de mémoire. Le code d'exemple est donné ci-dessous:

package main
import "container/list"
import "fmt"

func main() {
    // nouvelle liste chaînée
    queue := list.New()

    // Simplement appender pour enfiler.
    queue.PushBack(10)
    queue.PushBack(20)
    queue.PushBack(30)

    // Défiler
    front:=queue.Front()
    fmt.Println(front.Value)
    // Cela supprimera la mémoire allouée et évitera les fuites de mémoire
    queue.Remove(front)
}

Answer 3

Tranche peut être utilisé pour implémenter une file d'attente.

type queue struct {
    values []*int
}

func New() *queue {
   queue := &queue{}
   return queue
}

func (q *queue) enqueue(val *int) {
   q.values = append(q.values, val)
}

//fonction de défilement

Mise à jour:

Voici l'implémentation complète sur ma page GitHub https://github.com/raiskumar/algo-ds/blob/master/tree/queue.go