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

题目

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

第 5 空应填（ ）

答案

top1-1

题解

考点定位

本题（双栈第⑤空）考「访问下标」,对应大纲 3.2.1 栈（难度【2】）。

解题过程

⑤处平衡后访问目标元素：

``cpp printf("%d\n", stack1[top1 - 1]); ``

（top1 指向栈顶的下一位置 ⇒ 实际栈顶是 top1−1。）答案：top1−1。

易错提醒

① 「指向栈顶的下一个位置」⇒ 取值 −1；② clearStack 清理的是两栈外围的无效区。