Golang的队列实现

前言

Golang中没有原生的队列实现，故实现了一个简单的队列，了解队列的工作方式。

互斥锁

互斥锁是并发控制常用的一种锁，保证了同一时刻同一个资源对象只有一个线程或协程访问，避免出现对变量进行拷贝再赋值导致的问题，而在队列中，使用互斥锁能够保证同一时刻只有入队或出队操作，避免出现混乱，简单的用法如下：

package main

import (
    "fmt"
    "sync"
)

func main() {
    // 互斥锁
    var locker sync.Mutex
    // 一个共享变量
    num := 0

    for i := 0; i < 114514; i++ {
        go func() {
            locker.Lock()
            num++
            locker.Unlock()
            fmt.Println(num)
        }()
    }
    for {
        if num >= 114514 {
            break
        }
    }
    fmt.Println("---------")
    fmt.Println(num)
}

可以尝试去除这个互斥锁运行，但你会发现最后num并没有达到114514，所以程序不会自动结束运行。

切片实现

队列的实现方式有很多种，使用链表性能更优，适合先进先出，但我这里使用了切片来实现，实现了入队出队操作，对内置切片进行维护，包括前移和增容操作。

package main

import (
    "fmt"
    "sync"
)

type Queue struct {
    // 内部维护的切片
    queueSlice []interface{}
    // 容量
    cap uint
    // 起始队列位置
    begin uint
    // 队列尾部位置
    end uint
    // 默认队列大小
    defaultLength uint
    // 并发互斥锁
    locker sync.Mutex
}

func QueueInit(defaultLength uint) *Queue {
    return &Queue{
        queueSlice:    make([]interface{}, defaultLength, defaultLength),
        cap:           defaultLength,
        begin:         0,
        end:           0,
        defaultLength: defaultLength,
        locker:        sync.Mutex{},
    }
}

func (q *Queue) Length() uint {
    // 通过队尾队列开始位置计算长度
    q.locker.Lock()
    length := q.end - q.begin
    q.locker.Unlock()
    return length
}

func (q *Queue) Push(value interface{}) {
    q.locker.Lock()
    // 未超出容量
    if q.end < q.cap {
        q.queueSlice[q.end] = value
        q.end++
    } else {
        // 当长度小于容量进行前移
        if q.end-q.begin < q.cap {
                    // 用for移动会更好
                    // copy,append 也是有开销的
            temp := q.queueSlice[q.begin:q.end]
            q.queueSlice = make([]interface{}, q.cap, q.cap)
            copy(q.queueSlice, temp)
            q.begin = 0
            q.end = uint(len(temp))
            q.queueSlice[q.end] = value
            q.end++
        }
        // 长度达到容量对切片进行扩容
        if q.end >= q.cap {
            temp := make([]interface{}, q.end-q.begin)
            copy(temp, q.queueSlice[q.begin:q.end])
                    // 扩增一倍容量
            q.queueSlice = make([]interface{}, q.cap+q.defaultLength, q.cap+q.defaultLength*2)
            q.cap = q.cap + q.defaultLength
            copy(q.queueSlice, temp)
            q.queueSlice[q.end] = value
            q.end++
        }
    }
    // fmt.Println("|-value", value, "cap", q.cap, "begin", q.begin, "end", q.end)
    q.locker.Unlock()
}

func (q *Queue) Get() interface{} {
    q.locker.Lock()
    if q.begin < q.end {
        value := q.queueSlice[q.begin]
        q.begin++
        q.locker.Unlock()
        return value
    }
    q.locker.Unlock()
    return nil
}

func main() {
    q := QueueInit(6)
    go func(queue *Queue) {
        for {
            value := queue.Get()
            if value == nil {
                continue
            }
            fmt.Println("out", value)
        }
    }(q)
    for i := 0; i <= 27; i++ {
        q.Push(i)
        fmt.Println("in", i)
    }
    for {
        if q.Length() == 0 {
            break
        }
    }
    fmt.Println("len", q.Length())
}

链表实现

package main

import (
    // container/list
    "fmt"
)

type Node struct {
    prev  *Node
    next  *Node
    value interface{}
}

type Queue struct {
    length uint
    // 始节点
    begin  *Node
    // 尾节点
    end    *Node
}

func (q *Queue) Push(value interface{}) {
    node := &Node{prev: nil, next: nil, value: value}
    if q.length == 0 {
        q.begin = node
        q.end = node
        q.length++
        return
    }
    q.end.next = node
    node.prev = q.end
    q.end = node
    q.length++
}

func (q *Queue) Get() interface{} {
    if q.length == 0 {
        return nil
    }
    value := q.begin.value
    q.begin = q.begin.next
    q.length--
    return value
}

func NewQueue() *Queue {
    return &Queue{
        length: 0,
        begin:  nil,
        end:    nil,
    }
}

func main() {
    q := NewQueue()
    go func(q *Queue) {
        for {
            value := q.Get()
            if value == nil {
                break
            }
            fmt.Println("out", value)
        }
    }(q)
    for i := 0; i < 100; i++ {
        q.Push(i)
        fmt.Println("in", i)
    }
    for {
        if q.length == 0 {
            break
        }
    }
}