NOIP 提高 2012 第一轮 第 34 题：完善程序（排列数）第 3 空

题目

2.（新壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 $c$ 个元素是它的壳，支持翻转操作。其中，$c > 2$ 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 $c$ 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 $c$，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 $c$ 个，应当输出相应的错误信息。

![](http://luogu-ipic.oss-cn-shanghai.aliyuncs.com/youti/31.png)
![](http://luogu-ipic.oss-cn-shanghai.aliyuncs.com/youti/32.png)
![](http://luogu-ipic.oss-cn-shanghai.aliyuncs.com/youti/33.png)

#include < iostream >
using namespace std;
const int
NSIZE = 100000,
CSIZE = 1000;
int n, c, r, tail, head, s[NSIZE], q[CSIZE];
//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标
bool direction, empty;
int previous(int k) {
	if (direction)
		return ((k + c - 2) % c) + 1;
	else
		return (k % c) + 1;
}
int next(int k) {
	if (direction)
		①;
	else
		return ((k + c - 2) % c) + 1;
}
void push() {
	int element;
	cin >> element;
	if (next(head) == tail) {
		n++;
		②;
		tail = next(tail);
	}
	if (empty)
		empty = false;
	else
		head = next(head);
	③ = element;
}
void pop() {
	if (empty) {
		cout << "Error: the stack is empty!" << endl; return;
	}
	cout << 	④ << endl;
	if (tail == head)
		empty = true;
	else {
		head = previous(head);
	if (n > 0) {
		tail = previous(tail);
		⑤ = s[n];
		n--;
	}
}
}
void reverse() {
	int temp;
	if (	⑥ == tail) {
		direction =  ! direction;
		temp = head;
		head = tail;
		tail = temp;
	}
	else
		cout << "Error: less than " << c << " elements in the stack!" << endl;
}
int main() {
	cin >> c;
	n = 0;
	tail = 1;
	head = 1;
	empty = true;
	direction = true;
	do {
		cin >> r;
		switch (r) {
			case 1:push(); break;
			case 2:pop(); break;
			case 3:reverse(); break;
		}
	}while (r != 0);
	return 0;
}

③处应填（ ）

答案

q[head]

题解

考点定位

本题（新壳栈第③空）考「入壳写位」,对应大纲 3.2.1 数据结构（难度【4】）。

解题过程

③处新元素写入壳的队头：

``cpp q[head] = element; ``

（head 已先 next 步进到新位置。）答案：q[head]。

易错提醒

① push 总是写 head 位置（壳顶）；② 空/非空两种情形 head 步进规则不同（empty 时 head 不动）。