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

题目

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

第 1 空应填（ ）

答案

n

题解

考点定位

本题（完善程序「双栈模拟数组」第①空）考「栈顶初始化」,对应大纲 3.2.1 栈（难度【4】）。

程序思路：stack1 正向存数组前段、stack2 逆向存后段，随机访问 k 时倒腾元素。top1/top2 指向栈顶元素的下一个位置。

解题过程

①处 top1 初始 = 装满数据后的栈顶下一位置：

``cpp top1 = n; ``

答案：n。

易错提醒

① 「指向栈顶的下一个」语义：有效元素是 stack1[0..top1−1]；② top2 = SIZE（从数组另一端开始）。