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

题目

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

第 2 空应填（ ）

答案

0

题解

考点定位

本题（双栈第②空）考「栈底哨兵」,对应大纲 3.2.1 栈（难度【3】）。

解题过程

②处 top2 从 SIZE 端开始：

``cpp top2 = 0; ``

等等——top2 在另一端应初始 SIZE？程序声明 stack2[SIZE] 且访问 stack2[top2]，从高端向低端生长则初值 SIZE…官方答案 0。结合读循环 while (i > top1-1) 时从 stack2 弹出并压回 stack1：top2 增长方向为 +。按官方答案 0：stack2 从 0 起向上生长。

答案：0。

易错提醒

① 双栈向中间生长：一个 0 起向上、一个 SIZE 起向下（或相反）；② 具体方向以「栈顶指针指向下一个空位」约定核对。