四、实现数组队列ArrayQueue
队列先进先出，和栈操作顺序相反，我们这里只实现入队，和出队操作，其他操作和栈一样。
package mainimport "sync"// 数组队列，先进先出
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)//队中元素数量+1queue.size += 1}//直接将元素放在数组最后面即可，和栈一样，时间复杂度为：O(n)。//出队操作func (queue *ArrayQueue) Pop() string {queue.lock.Lock()queue.lock.Unlock()//如果队列为空的话if queue.size == 0 {panic("队列已空")}//取出队列最前端的数据，但你要考了不后续元素补位问题v := queue.array[0]/*相当于处理方式1直接原位进行移动，但缩容的后续的空间不会被释放for i := 0; 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//然后队中元素数量-1queue.size = queue.size - 1return v
}
func main() {}注意：
出队，把数组的第一个元素的值返回，并对数据进行空间挪位，挪位有两种：
- 原地挪位，依次补位
queue.array[i-1] = queue.array[i]，然后数组缩容：queue.array = queue.array[0 : queue.size-1]，但是这样切片缩容的那部分内存空间不会释放。 - 创建新的数组，将老数组中除第一个元素以外的元素移动到新数组。
时间复杂度是：O(n)。
五、实现链表队列LinkQueue
队列先进先出，和栈操作顺序相反，无非和上述实现方式不一样罢了
package mainimport "sync"//链表队列，先进先出type LinkQueue struct {root *LinkNode //链表起点size intlock sync.Mutex
}
type LinkNode struct {next *LinkNodeValue 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.rootfor nowNode.next != nil {newNode = nowNode.next}//然后将新节点放在链表末尾nowNode.next = newNode}//队中元素数量+1queue.size = queue.size + 1
}//将元素放在链表的末尾，所以需要遍历链表，时间复杂度为：O(n)。//出队操作
func (queue *LinkQueue) Remove() string {queue.lock.Lock()defer queue.lock.Unlock()//队列元素已为空if queue.size == 0 {panic("队列为空")}//出队操作topNode := queue.rootv := topNode.Value//然后将顶部元素的后续链接连接上queue.root = topNode.next//并且队中元素数量-1queue.size = queue.size - 1return v}
//链表第一个节点出队即可，时间复杂度为：O(1)。
func main() {}
