Queue-Implementierung in Golang

Jay Singh 30 Januar 2023

Go Go Queue

Queue-Implementierung mit slice in Golang
Queue-Implementierung mit container/list in Golang

Eine Warteschlange ist wie ein Stapel eine typische Datenstruktur, die Dinge in einer logischen Reihenfolge anordnet. Eine Warteschlange verwendet den FIFO-Mechanismus (First In First Out), bei dem das Erste, was in die Warteschlange gestellt wird, auch das Erste ist, das aus der Warteschlange entfernt wird.

Sie können eine einfache Warteschlange in Golang erstellen, indem Sie:

Scheibe
Container-/Listenpaket

Queue-Implementierung mit `slice` in Golang

Dequeue- und Enqueue-Aktionen können wie folgt durchgeführt werden, da eine Warteschlange einer FIFO-Struktur (First-In-First-Out) folgt:

Verwenden Sie zum Enqueue die eingebaute add-Funktion.
Um die Warteschlange zu entfernen, slice das Anfangsstück ab.

Beispiel 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())
}

Ausgabe:

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

Beispiel 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())
}

Ausgabe:

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

Queue-Implementierung mit `container/list` in Golang

Wir können eine dynamische Datenstruktur verkettete Liste verwenden, um Speicherlecks zu vermeiden.

Beispiel 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)
}

Ausgabe:

Beispiel 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())
}

Ausgabe:

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

Queue-Implementierung mit slice in Golang

Queue-Implementierung mit container/list in Golang

Queue-Implementierung mit `slice` in Golang

Queue-Implementierung mit `container/list` in Golang