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

题目

（双栈模拟数组）只使用两个栈结构 $\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);
}

第 3 空应填（ ）

答案

stack2[top2]=stack1[top1]

题解

考点定位

本题（双栈第③空）考「向 stack2 压栈」,对应大纲 3.2.1 栈（难度【3】）。

解题过程

③处把 stack1 顶部转移进 stack2：

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

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

易错提醒

① i<top1−1 时需把 stack1 顶部移入 stack2，使 stack1 顶逼近 i；② top2++ 在其后由外层完成。