NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 28 题

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

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

  

#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 ele

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是数据结构组合与循环队列模拟。拿到题先想：栈底存数据，栈顶c个存壳，用方向变量控制壳的翻转。push时壳空就进栈，壳满就进队列；pop同理；reverse只改方向。

最容易错在把循环队列的next和previous搞反，导致翻转后指针移动方向错误；其次是在判断壳满时写成tail==head（那是壳空的条件）；还有push时忘记先判断next(head)==tail就溢出，没把元素从q[tail]移回s[n]；以及pop时顺序颠倒，先写q[head]再写q[tail]导致壳里元素错位。

这道题考查的是数据结构组合与循环队列模拟。核心在于理解“新壳栈”的运作机制：栈底存数据，栈顶c个存壳，用方向变量控制壳的翻转。拿到题先想：push时壳空就进栈，壳满就进队列；pop同理；reverse只改方向。具体怎么算？看下面逐空推导。

先看几个关键概念。s[]是普通栈，n是元素个数；q[]是循环队列，模拟壳，head和tail分别指向队头和队尾的下一个位置；direction控制壳是正向还是反向。previous(k)和next(k)根据direction返回循环队列中的前驱/后继位置，注意下标从1开始，所以结果要+1。

现在逐个填空。

①处是next函数在direction为false时的返回值。previous在false时是(k%c)+1，next和previous互逆，所以next在false时应该是((k+c-2)%c)+1；反之，next在true时是(k%c)+1。因此①填return(k%c)+1。

②处是push函数中，当壳已满（next(head)==tail）时的处理。此时要把壳的队尾元素移到栈底，因为栈底是s[n]，而队尾元素在q[tail]，所以填s[n]=q[tail]。

③处是push的正常流程。如果壳未满，元素直接进壳的队头，即q[head]=element。所以填q[head]。

④处是pop函数输出弹出的元素。弹出时先输出壳的队头元素，即q[head]。所以填q[head]。

⑤处是pop中，当壳不为空且n>0时，要把栈顶元素移到壳的队尾。栈顶元素是s[n]，壳队尾是q[tail]，所以填q[tail]=s[n]。

⑥处是reverse函数判断壳是否已满。壳满的条件是tail的predecessor等于head，即next(head)==tail。所以填next(head)。

再看几个易错点。previous和next互为反函数，方向改变后行为互换，这里必须严格对应。判断壳满时用if(next(head)==tail)，别写成tail==head（那是壳空的条件）。push时先判断next(head)==tail，避免溢出；pop时顺序是输出q[head]，再移动head，如果n>0再移动tail并写入q[tail]，千万别把q[head]和q[tail]写反。

关于考频趋势，线性表在题库共考过7题，覆盖2009-2022年，NOIP提高组初赛仅1次（就是本题），但栈和队列是高频考点。栈共89题，队列46题，近年2024-2026年考频明显上升（栈25题/15题/9题，队列12题/13题/9题），说明这类组合数据结构题越来越受命题人青睐。未来可能继续以“栈+循环队列/双向队列”的形式出现，甚至加入更复杂的翻转或合并操作，难度会有所提升。

综上，本题答案依次是：①return(k%c)+1，②s[n]=q[tail]，③q[head]，④q[head]，⑤q[tail]=s[n]，⑥next(head)。