NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 27 题

（双栈模拟数组）只使用两个栈结构 $\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初始指向n，top2初始为0。当目标下标i小于top1-1时，需要把栈顶元素移到stack2；反之则把stack2栈顶移回stack1。移动完再清空栈，最后访问stack1[top1-1]即可。

最容易栽跟头的地方是top1的初始值。很多考生看到数组有n个元素就填n-1，或者填0，完全忽略了题目里top1和top2的定义——它们都指向“下一个空闲位置”。所以stack1装n个元素后，top1自然就是n，stack2空着就是0。另外，移动逻辑里两个while循环的方向容易搞反：i比top1-1小，说明目标在stack1的下方，得把stack1栈顶弹出来塞进stack2；i比top1-1大，就得把stack2弹回stack1。最后输出位置是top1-1，别写成top1或者top1-2。

双栈模拟数组随机读取

考点与概念

本题考查栈（stack）的基本操作，特别是如何用两个栈模拟数组的随机访问。栈只能访问栈顶，top1和top2均指向栈顶元素的下一个位置（即空闲位置）。数组下标从0到n-1，我们需要通过移动栈顶元素，让目标下标i始终位于stack1的top1-1处，然后输出stack1[top1-1]。