用不可变数组实现栈和队列

一、换个思路:不是「改容器」,是「换容器」

栈(Stack)后进先出,像叠盘子:新盘子摞顶上,取也从顶上取。队列(Queue)先进先出,像排队领装备:从队尾进,从队头出。传统语言靠 push / pop / dequeue 这些「原地修改」方法实现;Verse 数组是不可变值,一个原地方法都没有——但没关系,思路一换就通:每次操作都造一个新数组,整体替换 var 里的旧值。

栈(Stack)后进先出,像叠盘子:新盘子摞顶上,取也从顶上取。队列(Queue)先进先出,像排队领装备:从队尾进,从队头出。别处一般靠 push / pop / dequeue 这些「原地改」的手段来做;Verse 数组是「值」、一个原地改的办法都没有——但没关系,思路一换就通:每次操作都造一排新的,整排替换掉变量里那排旧的。

对照表先立起来:入栈 / 入队 = 尾部拼接 set Xs += array{X};出栈 = 读最后一件 Xs[Xs.Length - 1],再用 Slice[0, Length - 1] 切掉尾巴;出队 = 读第一件 Xs[0],再用 Slice[1, Length] 保留其余。Epic 官方文档有专门一页《Stacks and Queues in Verse》讲这套玩法;下面的实现代码是该主题的通行写法,细节请以官方页面为准。

二、栈:一个「撤销系统」

游戏里最经典的栈就是撤销:每做一步操作压栈,按撤销键弹出最近一步。注意 Pop 的签名——它读了下标、又调了 Slice,两个都可能失败,所以整个函数标 <transacts><decides>,调用时用方括号 Pop[]。空栈时 Stack[Stack.Length - 1] 即 Stack[-1],必然失败,整个 Pop 跟着失败——「栈空不能弹」这条业务规则,一行防御代码都没写,自己从语义里长出来了。

游戏里最经典的栈就是撤销:每做一步操作就压进栈,按撤销键弹出最近一步。注意 Pop 这个函数——它先取一格、又调了 Slice,两步都可能做不成,所以整个函数门牌标上 <transacts><decides>,调用时用方括号 Pop[]。栈空的时候,Stack[Stack.Length - 1] 就是 Stack[-1],必然取不到,整个 Pop 跟着走不通——「栈空了不能弹」这条规则,你一行防御判断都没写,它自己就从机制里长出来了。

using { /Fortnite.com/Devices }
using { /UnrealEngine.com/Temporary/Diagnostics }

undo_stack_device := class(creative_device):

    # 栈:后进先出,尾部是「顶」
    var Stack:[]string = array{}

    Push(Item:string):void =
        set Stack += array{Item}

    Pop()<transacts><decides>:string =
        Top := Stack[Stack.Length - 1]
        set Stack = Stack.Slice[0, Stack.Length - 1]
        Top

    OnBegin<override>()<suspends>:void =
        Push("挖墙")
        Push("搭板")
        Push("放门")
        if (Undone := Pop[]):
            Print("撤销了:{Undone}")
        Print("栈里还剩 {Stack.Length} 步")
        if (A := Pop[], B := Pop[]):
            Print("再撤销:{A} 和 {B}")
        if (Empty := Pop[]):
            Print("到不了这里")
        else:
            Print("栈空了,Pop 失败——不崩,只是失败")

跑一遍脑内模拟:三次 Push 后栈是「挖墙、搭板、放门」;第一次 Pop[] 弹出压轴的「放门」;接着 A、B 依次弹出「搭板」「挖墙」;最后一次 Pop[] 面对空栈,干脆利落地失败,走 else。还有个隐藏彩蛋:if (A := Pop[], B := Pop[]) 里如果 B 失败,A 那次已经弹出的操作会被事务回滚塞回栈里——绝不会出现「弹了一半」的中间态(细节见拔高篇)。

跑一遍脑内模拟:三次 Push 后栈里是「挖墙、搭板、放门」;第一次 Pop[] 弹出压轴的「放门」;接着 A、B 依次弹出「搭板」「挖墙」;最后一次 Pop[] 面对空栈,干脆利落地走不通,拐去 else。还有个隐藏彩蛋:if (A := Pop[], B := Pop[]) 里如果 B 那步没走通,A 那次已经弹出的操作会被整个撤回、塞回栈里——绝不会出现「弹了一半」的中间状态(原理见拔高篇)。

三、队列:一个「匹配等待室」

队列换个方向:进还是从尾巴进,出改从头出。典型场景是排队匹配——先来的玩家先进对局:

using { /Fortnite.com/Devices }
using { /UnrealEngine.com/Temporary/Diagnostics }

match_queue_device := class(creative_device):

    # 队列:先进先出,头部是 0 号格
    var Queue:[]string = array{}

    Enqueue(Item:string):void =
        set Queue += array{Item}

    Dequeue()<transacts><decides>:string =
        First := Queue[0]
        set Queue = Queue.Slice[1, Queue.Length]
        First

    OnBegin<override>()<suspends>:void =
        Enqueue("泡泡")
        Enqueue("阿呆")
        if (Next := Dequeue[]):
            Print("{Next} 进入对局")
        Print("还在排队:{Queue.Length} 人")

Dequeue 的两步:Queue[0] 读排头,Slice[1, Queue.Length] 保留 1 号格到末尾的所有人——正好是「除排头外的其余」。空队列时 Queue[0] 失败,整个 Dequeue 失败,和栈一样零防御代码。要说代价,也有:每次出队都整体新建数组,队伍极长时不是最省的做法——但对关卡逻辑这个量级,清晰压倒一切。

Dequeue 的两步:Queue[0] 读排头,Slice[1, Queue.Length] 留下 1 号格到末尾的所有人——正好是「除排头外的其余」。空队列时 Queue[0] 取不到,整个 Dequeue 跟着走不通,和栈一样一行防御判断都不用写。要说代价,也有:每次出队都整排新建数组,队伍极长时不是最省的做法——但对关卡逻辑这个量级,清晰压倒一切。

四、随堂测验

来源与延伸

本文主题来自 Epic 官方文档《Stacks and Queues in Verse》(dev.epicgames.com ↗);文中实现代码为该主题的通行写法,具体细节以官方页面为准。想继续深挖「失败即业务规则」的写法,请移步本课的拔高篇《为什么越界不抛异常》。