NOIP 提高 2014 第一轮 第 30 题：完善程序（双栈模拟数组）第 4 空

题目

（双栈模拟数组）只使用两个栈结构 $\mathrm{stack1}$ 和 $\mathrm{stack2}$，模拟对数组的随机读取。作为栈结构，$\mathrm{stack1}$ 和 $\mathrm{stack2}$ 只能访问栈顶（最后一个有效元素）。栈顶指针 $\mathrm{top1}$ 和 $\mathrm{top2}$ 均指向栈顶元素的下一个位置。

输入第一行包含的两个整数，分别是数组长度 $n$ 和访问次数 $m$，中间用单个空格隔开。

第二行包含 $n$ 个整数，一次给出数组各项（数组下标从 $0$ 到 $a-1$）。第三行包含 $m$ 个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。

#include <stdio.h>
const int	SIZE = 100;
int		stack1[SIZE], stack2[SIZE];
int		top1, top2;
int		n, m, i, j;
void clearStack()
{
	int i;
	for ( i = top1; i < SIZE; i++ )
		stack1[i] = 0;
	for ( i = top2; i < SIZE; i++ )
		stack2[i] = 0;
}

int main()
{
	scanf( "%d,%d", &n, &m );

	for ( i = 0; i < n; i++ )
		scanf( "%d", &stack1[i] );
	top1	=  （1）;
	top2	=  （2）;
	for ( j = 0; j < m; j++ )
	{
		scanf( "%d", &i );
		while ( i < top1 - 1 )
		{
			top1--;
			( 3 ) ;
			top2++;
		}
		while ( i > top1 - 1 )
		{
			top2--;
			( 4 ) ;
			top1++;
		}
		clearstack();
		printf( "%d\n", stack1[( 5 ) ] );
	}
	return(0);
}

第 4 空应填（ ）

答案

stack1[top1]=stack2[top2]

题解

考点定位

本题（双栈第④空）考「回退转移」,对应大纲 3.2.1 栈（难度【3】）。

解题过程

④处 i>top1−1 时反向转移（从 stack2 取回 stack1）：

``cpp stack1[top1] = stack2[top2]; ``

答案：stack1[top1]=stack2[top2]。

易错提醒

① 两个 while 互为镜像；② 访问目标 stack1[i] 在两栈平衡后达成。