package zgo_algorithm import "sync" // 数组队列，先进先出 // 队列先进先出，和栈操作顺序相反，我们这里只实现入队，和出队操作，其他操作和栈一样。 type ArrayQueue struct { array []interface{} // 底层切片 size int // 队列的元素数量 lock sync.Mutex // 为了并发安全使用的锁 } // 入队 // 直接将元素放在数组最后面即可，和栈一样，时间复杂度为：O(n) func (queue *ArrayQueue) Push(v interface{}) { queue.lock.Lock() defer queue.lock.Unlock() // 放入切片中，后进的元素放在数组最后面 queue.array = append(queue.array, v) // 队中元素数量+1 queue.size = queue.size + 1 } // 出队，把数组的第一个元素的值返回，并对数据进行空间挪位 // 创建新的数组，将老数组中除第一个元素以外的元素移动到新数组 // 时间复杂度是：O(n) func (queue *ArrayQueue) Pop() interface{} { queue.lock.Lock() defer queue.lock.Unlock() // 队中元素已空 if queue.size == 0 { panic("队列元素为空") } // 队列最前面元素 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([]interface{}, 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 } // 获取队列最后一个元素 func (queue *ArrayQueue) Last() interface{} { // 栈中元素已空 if queue.size == 0 { panic("队列元素为空") } // 栈顶元素值 v := queue.array[queue.size-1] return v } // 获取队列第一个元素 func (queue *ArrayQueue) First() interface{} { // 栈中元素已空 if queue.size == 0 { panic("队列元素为空") } // 栈顶元素值 v := queue.array[0] return v } // 队列大小 // 时间复杂度都是：O(1) func (queue *ArrayQueue) Size() int { return queue.size } // 队列是否为空 // 时间复杂度都是：O(1) func (queue *ArrayQueue) IsEmpty() bool { return queue.size == 0 }