Golang 中的佇列實現

  2. 貼士文章
  3. Go 貼士
  4. Golang 中的佇列實現
Jay Singh 2023年1月30日 2022年4月22日
Go Go Queue
  1. 在 Golang 中使用 slice 實現佇列
  2. 在 Golang 中使用 container/list 實現佇列
Golang 中的佇列實現

佇列，就像堆疊一樣，是一種以邏輯順序排列事物的典型資料結構。queue 採用 FIFO（先進先出）機制，其中第一個入隊的事物也是第一個出隊的事物。

你可以通過以下方式在 Golang 中建立基本佇列：

  1. 切片
  2. 容器/列表包

在 Golang 中使用 slice 實現佇列

由於佇列遵循 FIFO（先進先出）結構，因此可以按如下方式執行出隊和入隊操作：

  1. 要入隊，請使用內建的 add 函式。
  2. 要出列，從初始部分切片。

示例 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())
}

輸出：

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

示例 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())
}

輸出：

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

在 Golang 中使用 container/list 實現佇列

我們可以使用動態資料結構連結串列來避免記憶體洩漏。

示例 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)
}

輸出：

10

示例 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())
}

輸出：

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