Queue

先进先出，先进队的数据先出来。在英文的意思里，queue 和现实世界的排队意思一样，这个排列是水平的，先排先得。

实现数组队列 ArrayQueue

队列先进先出，和栈操作顺序相反，我们这里只实现入队，和出队操作，其他操作和栈一样。

// 数组队列，先进先出
type ArrayQueue struct {
array []string   // 底层切片
size  int        // 队列的元素数量
lock  sync.Mutex // 为了并发安全使用的锁
}

入队

// 入队
func (queue *ArrayQueue) Add(v string) {
queue.lock.Lock()
defer queue.lock.Unlock()

    // 放入切片中，后进的元素放在数组最后面
    queue.array = append(queue.array, v)

    // 队中元素数量+1
    queue.size = queue.size + 1
}

直接将元素放在数组最后面即可，和栈一样，时间复杂度为：O(n)。

出队

// 出队
func (queue *ArrayQueue) Remove() string {
queue.lock.Lock()
defer queue.lock.Unlock()

    // 队中元素已空
    if queue.size == 0 {
        panic("empty")
    }

    // 队列最前面元素
    v := queue.array[0]

    /*    直接原位移动，但缩容后继的空间不会被释放
        for i := 1; i < queue.size; i++ {
            // 从第一位开始进行数据移动
            queue.array[i-1] = queue.array[i]
        }
        // 原数组缩容
        queue.array = queue.array[0 : queue.size-1]
    */

    // 创建新的数组，移动次数过多
    newArray := make([]string, queue.size-1, queue.size-1)
    for i := 1; i < queue.size; i++ {
        // 从老数组的第一位开始进行数据移动
        newArray[i-1] = queue.array[i]
    }
    queue.array = newArray

    // 队中元素数量-1
    queue.size = queue.size - 1
    return v
}

//出队，把数组的第一个元素的值返回，并对数据进行空间挪位，挪位有两种：
//
//    原地挪位，依次补位 queue.array[i-1] = queue.array[i]，
//    然后数组缩容：queue.array = queue.array[0 : queue.size-1]，
//    但是这样切片缩容的那部分内存空间不会释放。

//    创建新的数组，将老数组中除第一个元素以外的元素移动到新数组。
//
//时间复杂度是：O(n)。

实现链表队列 LinkQueue

队列先进先出，和栈操作顺序相反，我们这里只实现入队，和出队操作，其他操作和栈一样。

// 链表队列，先进先出
type LinkQueue struct {
root *LinkNode  // 链表起点
size int        // 队列的元素数量
lock sync.Mutex // 为了并发安全使用的锁
}

// 链表节点
type LinkNode struct {
Next  *LinkNode
Value string
}

入队

// 入队
func (queue *LinkQueue) Add(v string) {
queue.lock.Lock()
defer queue.lock.Unlock()

    // 如果栈顶为空，那么增加节点
    if queue.root == nil {
        queue.root = new(LinkNode)
        queue.root.Value = v
    } else {
        // 否则新元素插入链表的末尾
        // 新节点
        newNode := new(LinkNode)
        newNode.Value = v

        // 一直遍历到链表尾部
        nowNode := queue.root
        for nowNode.Next != nil {
            nowNode = nowNode.Next
        }

        // 新节点放在链表尾部
        nowNode.Next = newNode
    }

    // 队中元素数量+1
    queue.size = queue.size + 1
}

//将元素放在链表的末尾，所以需要遍历链表，时间复杂度为：O(n)。

出队

// 出队
func (queue *LinkQueue) Remove() string {
queue.lock.Lock()
defer queue.lock.Unlock()

    // 队中元素已空
    if queue.size == 0 {
        panic("empty")
    }

    // 顶部元素要出队
    topNode := queue.root
    v := topNode.Value

    // 将顶部元素的后继链接链上
    queue.root = topNode.Next

    // 队中元素数量-1
    queue.size = queue.size - 1

    return v
}

//链表第一个节点出队即可，时间复杂度为：O(1)。