Implémentation de la file d'attente dans Golang

  2. HowTo
  3. Go Howtos
  4. Implémentation de la file d'attente dans …
Jay Singh 30 janvier 2023
Go Go Queue
  1. Implémentation de la file d’attente à l’aide de slice dans Golang
  2. Implémentation de la file d’attente à l’aide de container/list dans Golang
Implémentation de la file d'attente dans Golang

Une queue, comme une pile, est une structure de données typique qui organise les choses dans un ordre logique. Une queue utilise le mécanisme FIFO (First In First Out), dans lequel la première chose mise en file d’attente est également la première à être retirée de la file d’attente.

Vous pouvez créer une file d’attente de base dans Golang en :

  1. Slice
  2. Paquet Container/List

Implémentation de la file d’attente à l’aide de slice dans Golang

Les actions Dequeue et Enqueue peuvent être menées comme suit puisqu’une file d’attente suit une structure FIFO (First-In-First-Out) :

  1. Pour mettre en file d’attente, utilisez la fonction intégrée add.
  2. Pour sortir de la file d’attente, slice le morceau initial.

Exemple 1:

package main

import "fmt"

type StringQueue struct {
    queue []string
}

func (q *StringQueue) Enqueue(s string) {
    q.queue = append(q.queue, s)
}

func (q *StringQueue) Top() string {
    return q.queue[0]
}

func (q *StringQueue) Dequeue() string {
    temp := q.queue[0]
    q.queue = q.queue[1:]
    return temp
}

func (q *StringQueue) Empty() bool {
    return len(q.queue) == 0
}

func main() {
    fmt.Println("Queues")
    queue := StringQueue{make([]string, 0)}
    (&queue).Enqueue("Item 1")
    (&queue).Enqueue("Item 2")
    fmt.Println("Top:", (&queue).Top())
    fmt.Println("Dequeued", (&queue).Dequeue())
    fmt.Println("New Top:", (&queue).Top())
    fmt.Println("Empty?", (&queue).Empty())
    fmt.Println("Dequeued", (&queue).Dequeue())
    fmt.Println("Empty now?", (&queue).Empty())
}

Production:

Queues
Top: Item 1
Dequeued Item 1
New Top: Item 2
Empty? false
Dequeued Item 2
Empty now? true

Exemple 2 :

package main

import (
    "fmt"
    "sync"
)

type customQueue struct {
    queue []string
    lock  sync.RWMutex
}

func (c *customQueue) Enqueue(name string) {
    c.lock.Lock()
    defer c.lock.Unlock()
    c.queue = append(c.queue, name)
}

func (c *customQueue) Dequeue() error {
    if len(c.queue) > 0 {
        c.lock.Lock()
        defer c.lock.Unlock()
        c.queue = c.queue[1:]
        return nil
    }
    return fmt.Errorf("Pop Error - Queue is empty")
}

func (c *customQueue) Front() (string, error) {
    if len(c.queue) > 0 {
        c.lock.Lock()
        defer c.lock.Unlock()
        return c.queue[0], nil
    }
    return "", fmt.Errorf("Peep Error - Queue is empty")
}

func (c *customQueue) Size() int {
    return len(c.queue)
}

func (c *customQueue) Empty() bool {
    return len(c.queue) == 0
}

func main() {
    customQueue := &customQueue{
        queue: make([]string, 0),
    }

    fmt.Printf("Enqueue: 1\n")
    customQueue.Enqueue("1")
    fmt.Printf("Enqueue: 2\n")
    customQueue.Enqueue("2")
    fmt.Printf("Len: %d\n", customQueue.Size())

    for customQueue.Size() > 0 {
        frontVal, _ := customQueue.Front()
        fmt.Printf("Front: %s\n", frontVal)
        fmt.Printf("Dequeue: %s\n", frontVal)
        customQueue.Dequeue()
     }
    fmt.Printf("Len: %d\n", customQueue.Size())
}

Production:

Enqueue: 1
Enqueue: 2
Len: 2
Front: 1
Dequeue: 1
Front: 2
Dequeue: 2
Len: 0

Implémentation de la file d’attente à l’aide de container/list dans Golang

On peut utiliser une structure de données dynamique liste chaînée pour éviter les fuites de mémoire.

Exemple 1:

package main

import (
    "container/list"
    "fmt"
)

func main() {
    // new linked list
    queue := list.New()

    // Simply append to enqueue.
    queue.PushBack(10)
    queue.PushBack(20)
    queue.PushBack(30)

    // Dequeue
    front := queue.Front()
    fmt.Println(front.Value)
    // This frees up memory and prevents memory leaks.
    queue.Remove(front)
}

Production:

10

Exemple 2 :

package main

import (
    "container/list"
    "fmt"
)

type customQueue struct {
    queue *list.List
}

func (c *customQueue) Enqueue(value string) {
    c.queue.PushBack(value)
}

func (c *customQueue) Dequeue() error {
    if c.queue.Len() > 0 {
        ele := c.queue.Front()
        c.queue.Remove(ele)
    }
    return fmt.Errorf("Pop Error: Queue is empty")
}

func (c *customQueue) Front() (string, error) {
    if c.queue.Len() > 0 {
        if val, ok := c.queue.Front().Value.(string); ok {
        return val, nil
        }
        return "", fmt.Errorf("Peep Error: Queue Datatype is incorrect")
    }
    return "", fmt.Errorf("Peep Error: Queue is empty")
}

func (c *customQueue) Size() int {
    return c.queue.Len()
}

func (c *customQueue) Empty() bool {
    return c.queue.Len() == 0
}

func main() {
    customQueue := &customQueue{
        queue: list.New(),
    }
    fmt.Printf("Enqueue: A\n")
    customQueue.Enqueue("A")
    fmt.Printf("Enqueue: B\n")
    customQueue.Enqueue("B")
    fmt.Printf("Size: %d\n", customQueue.Size())
    for customQueue.Size() > 0 {
        frontVal, _ := customQueue.Front()
        fmt.Printf("Front: %s\n", frontVal)
        fmt.Printf("Dequeue: %s\n", frontVal)
        customQueue.Dequeue()
    }
    fmt.Printf("Size: %d\n", customQueue.Size())
}

Production:

Enqueue: A
Enqueue: B
Size: 2
Front: A
Dequeue: A
Front: B
Dequeue: B
Size: 0