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