深耕专业教研，探索前沿技术
信息技术来源：2025学年第二学期北斗星盟高三适应性联考

第 12 题

答案与解析

本题解析

参考答案

D

程序分析

que = [5,9,8,10,3,4,6,1,2,7]
n = len(que)
st = [0] * (n//2)
top1 = -1 ; top2 = 5
head = 4 ; tail = 3
while head != tail and top1 + 1 != top2:
    x = que[head]
    if x % 2 == 0:
        ...
    else:
        ...

n=10，st 有5个位置，下标为0至4。程序从 head=4 开始取出 que[head]，按 x 的奇偶性进入不同分支；每轮开始都要求 head!=tail 且 top1+1!=top2。两个分支如何改变这些变量，是判断停止位置的关键。

if x % 2 == 0:
    if top1 < 0 or x > st[top1]:
        top1 += 1
        st[top1] = x
    head = (head + 1) % n

x 为偶数时，若 top1<0，或 x 大于 st[top1]，就先将 top1 加1，再把 x 写入对应位置。top1 从-1开始，首次写入 st[0]，以后向下标增大的方向存放；因此，top1 是左侧栈的栈顶指针，-1表示空栈。只有空栈或新偶数大于栈顶值时才入栈，栈内元素从栈底到栈顶严格递增。

head 的更新位于内层 if 之外，因此无论是否入栈，当前元素都会被处理完并移向下一位置；取模使下标从9回到0。

else:
    if top2 >= len(st) or x > st[top2]:
        top2 -= 1
        st[top2] = x
    head = (head + 1) % n

x 为奇数时，top2 初值5等于 len(st)，第一次满足条件后先减为4，再写入 st[4]；以后每次入栈都令 top2 减1，向下标减小的方向存放。因此，top2 是右侧栈的栈顶指针，5表示空栈，入栈条件同样是空栈或新奇数大于栈顶值。奇数分支也总会推进 head，未入栈的数不会留待下轮处理。

整体功能

que 按循环队列方式访问，head 指向下一个待处理元素，tail 是有效数据的结束边界，head=tail 表示数据已处理完。st 供两个栈共享：偶数从左端入栈，奇数从右端入栈，各自只接收比当前栈顶更大的数。左栈占用0至 top1，右栈占用 top2 至4；当 top1+1=top2 时，中间已无空位，循环也会停止。

从 que[4] 开始按循环下标依次处理数据：

取数下标 head x 处理结果 top1 top2
4 3 右栈为空，写入 st[4] -1 4
5 4 左栈为空，写入 st[0] 0 4
6 6 6>4，写入 st[1] 1 4
7 1 1<3，不入栈 1 4
8 2 2<6，不入栈 1 4
9 7 7>3，写入 st[3] 1 3
0 5 5<7，不入栈 1 3
1 9 9>7，写入 st[2] 1 2

处理9后，head 变为2，虽然还未到 tail=3，但 top1+1=2=top2，共享空间已满，循环结束。que[2] 中的8不会再被处理。最终 st=[4,6,9,7,3]，st[2] 为9。