第 15 题

def arrive(car, brand, p):
    global h, t
    front = 0
    for b in order[h:t]:
        if b == brand:
            break
        front += length[b]
    front += length[brand]

题目规定 data 的每个结点保存 [车辆编号，品牌，同品牌下一辆车索引]，各品牌分别用链表连接自己的车辆。order[h:t] 保存当前仍有车辆的品牌及其排队顺序，h 指向队首品牌，t 指向下一次写入品牌的位置；length[b] 记录品牌 b 的车辆数。

for 循环按品牌顺序累加排在 brand 前面的各品牌车辆数，遇到 brand 时停止；随后加上 length[brand]，把同品牌的已有车辆也计入 front。这些车辆都排在新车前面。若当前没有该品牌，循环遍历全部有效品牌，而 length[brand] 为 0，得到的就是全队车辆数。

    if head[brand] == -1:
        head[brand] = p
        tail[brand] = p
        order[t] = brand
        t += 1
    else:
        data[tail[brand]][2] = p
        
    length[brand] += 1
    return front

head[brand]、tail[brand] 分别保存该品牌链表首、尾结点的下标，−1 表示空链表。品牌原来没有车辆时，将二者均设为新结点下标 p，并在 order[t] 登记该品牌，再让 t 增加 1，使新品牌排到品牌队列末尾。

品牌已有车辆时，data[tail[brand]][2]=p 将原尾结点的后继改为新结点；data[p][2] 初值为 −1，新结点没有后继。两条分支汇合后，length[brand] 增加 1，并返回入队前已算出的 front。

原尾结点已经连到新结点 p，此时 p 成为该品牌链表的尾结点，因此还需把尾指针更新为 p，填写 tail[brand]=p。否则下一辆同品牌车辆到达时，仍会修改旧尾结点的后继，覆盖本次建立的链接。

head[brand]==−1 表示该品牌链表为空，length[brand]==0 表示该品牌没有车辆。在头指针和车辆计数均按程序规则维护时，两者描述同一状态，因此能替换。这里的判断发生在新车插入及 length[brand] 增加 1 之前。

h = t = 0
head = [-1] * m; tail = [-1] * m; length = [0] * m
m = 3  # 品牌数量
n = 100  # 定义数组order的长度，即品牌顺序队列的最大容量，假设100足够大
order = [0] * n

h=t=0 表示品牌顺序队列初始为空；各品牌的头、尾指针初值为 −1，车辆数初值为0。order 保存品牌的排队顺序。

原代码应先定义 m，再创建三个品牌列表；若此前没有定义 m，列表初始化会报错。以下按 m=3、品牌列表已正确初始化分析。

def leave():  # 队首车辆离开
    global h
    brand = order[h]
    p = head[brand]
    ①
    length[brand] -= 1
    if head[brand] == -1:
        tail[brand] = -1
        ②
    return

brand=order[h] 取得队首品牌，p=head[brand] 取得该品牌首结点的下标，因此 p 指向本次离开的车辆。执行空①后，length[brand] 减少1；若此时 head[brand] 为 −1，已有语句将尾指针设为 −1，再执行空②。

for i in range(start, len(data)):
    vid = data[i][0]
    brand = data[i][1]
    front = arrive(vid, brand, i)
    print("前面有" + str(front) + "辆车在队伍中")
    left = leave()
    show_queue()  # 显示队伍中的车辆情况

每轮先调用 arrive，使新车完成入队并计算 front；输出前方车辆数后，再调用 leave，让队首车辆离开。因此调用 leave 时队列非空，正在装载且尚未离队的车辆仍计入 front。

p 是原首结点的下标，data[p][2] 保存它的同品牌后继结点下标。删除首结点只需让头指针指向这个后继，填写 head[brand]=data[p][2]。若原来只有一辆车，后继为 −1，更新后链表变空；data 中原结点的存储项无须删除。

该品牌已没有车辆，品牌顺序队列也应移到下一个品牌，填写 h += 1。若该品牌仍有车辆，就不进入此分支，h 保持不变，继续优先装载同品牌车辆。退出品牌留在 order 的旧存储位置不影响有效区间 order[h:t]；以后该品牌再有车辆到达时，由 arrive 将其重新加入队尾。