Golang学习-队列（Queue）

队列Queue一、队列的核心概念队列是一种先进先出FIFO, First In First Out的线性数据结构。就像排队买票——先排队的人先买到票后到的人排在队尾。队列有两端队尾Rear/Tail入队操作Enqueue发生的一端队头Front/Head出队操作Dequeue发生的一端栈 vs 队列维度栈队列出入规则LIFO 后进先出FIFO 先进先出开放端一端栈顶两端队头出队尾入典型应用函数调用、DFS、Undo任务调度、BFS、消息队列队列的典型应用场景BFS 广度优先搜索逐层访问图/树的节点任务调度操作系统进程调度、线程池任务队列消息队列生产者-消费者模式中的缓冲区打印队列先提交的文档先打印限流滑动窗口限流算法二、普通队列的问题假溢出如果用数组实现队列维护front和rear两个下标指针初始: [_ _ _ _ _] front0, rear0 入队 ABCD: [A B C D _] front0, rear4 出队 AB: [_ _ C D _] front2, rear4 入队 E: [_ _ C D E] front2, rear5 入队 F: ??? rear5 已经越界但前面还有空闲空间这就是假溢出问题数组前面有空间但 rear 指针已到达末尾无法继续入队。解决方案方案思路缺点元素搬迁每次出队后把所有元素前移O(n) 出队效率差循环队列让 rear 绕回数组开头需处理空满判断循环队列是最优解下面重点讲解。三、循环队列3.1 核心思想将数组视为一个首尾相连的环形结构。当rear或front到达数组末尾时通过取模运算绕回开头rear (rear 1) % capacity front (front 1) % capacity容量为 5 的循环队列: [0] - [1] - [2] ^ | | v [4] - [3] - front 和 rear 在环上循环移动3.2 空满判断难题循环队列面临一个棘手问题front rear既可以表示队空也可以表示队满。两种解决方案方案一牺牲一个槽位推荐队空front rear队满(rear 1) % capacity front实际容量 capacity - 1方案二维护 size 计数器队空size 0队满size capacity实际容量 capacity但每次操作需维护 size3.3 完整实现packagemainimportfmt// CircularQueue 循环队列牺牲一个槽位方案typeCircularQueuestruct{data[]intfrontint// 队头指针rearint// 队尾指针指向下一个可写入位置capacityint// 数组总容量}// NewCircularQueue 创建容量为 capacity 的循环队列// 实际可存储 capacity-1 个元素funcNewCircularQueue(capacityint)*CircularQueue{ifcapacity2{panic(capacity must be at least 2)}returnCircularQueue{data:make([]int,capacity),front:0,rear:0,capacity:capacity,}}// Enqueue 入队 O(1)func(q*CircularQueue)Enqueue(valint)bool{// 判满(rear1) % capacity frontif(q.rear1)%q.capacityq.front{returnfalse// 队列已满}q.data[q.rear]val q.rear(q.rear1)%q.capacityreturntrue}// Dequeue 出队 O(1)func(q*CircularQueue)Dequeue()(int,bool){// 判空front rearifq.frontq.rear{return0,false// 队列为空}val:q.data[q.front]q.front(q.front1)%q.capacityreturnval,true}// Front 查看队头元素 O(1)func(q*CircularQueue)Front()(int,bool){ifq.frontq.rear{return0,false}returnq.data[q.front],true}// IsEmpty 判空func(q*CircularQueue)IsEmpty()bool{returnq.frontq.rear}// IsFull 判满func(q*CircularQueue)IsFull()bool{return(q.rear1)%q.capacityq.front}// Size 返回当前元素个数 O(1)func(q*CircularQueue)Size()int{return(q.rear-q.frontq.capacity)%q.capacity}// AllElements 返回队列中所有元素从队头到队尾func(q*CircularQueue)AllElements()[]int{result:make([]int,0,q.Size())i:q.frontfori!q.rear{resultappend(result,q.data[i])i(i1)%q.capacity}returnresult}funcmain(){// 容量 5实际可存 4 个元素q:NewCircularQueue(5)// 入队 1,2,3,4q.Enqueue(1)q.Enqueue(2)q.Enqueue(3)q.Enqueue(4)fmt.Println(入队4个:,q.AllElements())// [1 2 3 4]fmt.Println(队满?,q.IsFull())// true// 第5个入队失败ok:q.Enqueue(5)fmt.Println(第5个入队成功?,ok)// false// 出队 2 个v,_:q.Dequeue()fmt.Println(出队:,v)// 1v,_q.Dequeue()fmt.Println(出队:,v)// 2fmt.Println(剩余:,q.AllElements())// [3 4]// 再入队 5,6复用前面释放的空间解决假溢出q.Enqueue(5)q.Enqueue(6)fmt.Println(入队5,6后:,q.AllElements())// [3 4 5 6]fmt.Println(队满?,q.IsFull())// true// 全部出队fmt.Print(全部出队: )for!q.IsEmpty(){v,_:q.Dequeue()fmt.Print(v, )// 3 4 5 6}fmt.Println()fmt.Println(队空?,q.IsEmpty())// true}运行结果入队4个: [1 2 3 4] 队满? true 第5个入队成功? false 出队: 1 出队: 2 剩余: [3 4] 入队5,6后: [3 4 5 6] 队满? true 全部出队: 3 4 5 6 队空? true四、链式队列链式队列用链表实现不存在假溢出问题也不需要预分配固定容量。packagemainimportfmt// queueNode 链式队列节点typequeueNodestruct{dataintnext*queueNode}// LinkedQueue 链式队列typeLinkedQueuestruct{front*queueNode// 队头指针出队端rear*queueNode// 队尾指针入队端lenint}funcNewLinkedQueue()*LinkedQueue{returnLinkedQueue{}}// Enqueue 入队 O(1) — 尾插法func(q*LinkedQueue)Enqueue(valint){newNode:queueNode{data:val}ifq.rearnil{// 空队列q.frontnewNode q.rearnewNode}else{q.rear.nextnewNode q.rearnewNode}q.len}// Dequeue 出队 O(1) — 头删法func(q*LinkedQueue)Dequeue()(int,bool){ifq.frontnil{return0,false}val:q.front.data q.frontq.front.nextifq.frontnil{// 队列已空重置 rearq.rearnil}q.len--returnval,true}func(q*LinkedQueue)IsEmpty()bool{returnq.frontnil}func(q*LinkedQueue)Size()int{returnq.len}func(q*LinkedQueue)AllElements()[]int{result:make([]int,0,q.len)cur:q.frontforcur!nil{resultappend(result,cur.data)curcur.next}returnresult}funcmain(){q:NewLinkedQueue()q.Enqueue(10)q.Enqueue(20)q.Enqueue(30)fmt.Println(入队3个:,q.AllElements())// [10 20 30]v,_:q.Dequeue()fmt.Println(出队:,v)// 10fmt.Println(剩余:,q.AllElements())// [20 30]// 不受容量限制继续入队fori:0;i10;i{q.Enqueue(i*100)}fmt.Println(继续入队10个:,q.AllElements())fmt.Println(队列大小:,q.Size())}运行结果入队3个: [10 20 30] 出队: 10 剩余: [20 30] 继续入队10个: [20 30 0 100 200 300 400 500 600 700 800 900] 队列大小: 12五、两种实现对比维度循环队列数组链式队列链表EnqueueO(1)O(1)DequeueO(1)O(1)容量限制固定预分配无限制按需分配内存连续性好缓存友好差指针跳转假溢出已解决取模绕回不存在此问题适用场景容量已知的场景容量不确定的场景六、双端队列Deque简介双端队列Double-Ended Queue是队列的扩展版本两端都可以进行入队和出队操作。它同时具备栈和队列的能力头部入队/出队 → 栈的 Push/Pop尾部入队/出队 → 队列的 Enqueue/DequeueGo 标准库container/list可以直接用作双端队列的实现。七、循环队列的关键公式速查判空front rear 判满(rear 1) % capacity front 元素个数(rear - front capacity) % capacity 入队后 rear 移动rear (rear 1) % capacity 出队后 front 移动front (front 1) % capacity理解要点取模运算是循环队列的灵魂。它让线性数组在逻辑上变成环形指针到达末尾后自动绕回开头。所有 O(1) 操作都建立在取模绕回这一机制上。八、Go 标准库的选择在实际工程中如果不需要固定容量Go 的切片就能很好地充当队列// 简易切片队列queue:[]int{}queueappend(queue,1)// Enqueueval:queue[0]// Frontqueuequeue[1:]// Dequeue注意频繁操作会导致内存泄漏但queue queue[1:]会导致底层数组前端的空间无法被 GC 回收。更安全的做法是用环形队列或链式队列或者使用copy手动搬移。生产环境推荐container/list或成熟的第三方队列库。九、总结操作循环队列链式队列EnqueueO(1)O(1)DequeueO(1)O(1)FrontO(1)O(1)容量固定动态假溢出取模绕回解决不存在队列的核心是 FIFO——先进先出。理解循环队列的关键在于掌握取模运算如何让线性数组在逻辑上变成环形以及牺牲一个槽位区分空满状态的技巧。链式队列则更直观通过头尾指针实现 O(1) 的入队出队且不受容量限制。