(新壳栈) 小 Z 设计了一种新的数据结构“新壳栈”。首先,它和传统的栈一样支持 压入、弹出操作。此外,其栈顶的前 c 个元素是它的壳,支持翻转操作。其中, c > 2 是一个固定的正整数,表示壳的厚度。小 Z 还希望,每次操作,无论是压入、弹出还 是翻转,用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗? 程序期望的实现效果如以下两表所示。其中,输入的第一行是正整数 c ,之后每行输入都是一条指令。另外,如遇弹出操作时栈为空,或翻转操作时栈中元素不足 c 个, 应当输出相应的错误信息。 指令 涵义 1[ 空格 ]e 在栈顶压入元素 e 2 弹出(并输出)栈顶元素 3 翻转栈顶的前 c 个元素 0 退出 表 1 :指令的涵义 输入 输出 栈中的元素 ( 栈底,右为栈顶 ) 说明 3 输入正整数 c 1 1 1 压入元素 1 1 2 1 2 压入元素 2 1 3 1 2 3 压入元素 3 1 4 1 2 3 4 压入元素 4 3 1 4 3 2 翻转栈顶的前 c 个元素 1 5 1 4 3 2 5 压入元素 5 3 1 4 5 2 3 翻转栈顶的前 c 个元素 2 3 1 4 5 2 弹出栈顶元素 3 2 2 1 4 5 弹出栈顶元素 2 2 5 1 4 弹出栈顶元素 5 3 错误信息 1 4 由于栈中元素不足 c 个,无法翻转,故操 作失败,输出错误信息 2 4 1 弹出栈顶元素 4 2 1 空 弹出栈顶元素 1 2 错误信息 空 由于栈为空,无法弹出栈顶元素,故操作失败,输出错误信息 0 空 退出 表 2 :输入输出样例 #include 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) 1 ; else return ((k + c - 2) % c) + 1; } void push() { int element; cin>>element; if (next(head) == tail) { n++; 2 ; tail = next(tail); } if (empty) empty = false; else head = next(head); 3 = element; } void pop() { if (empty) { cout< } cout<< 4 < if (tail == head) empty = true; else { head = previous(head); if (n > 0) { tail = previous(tail); 5 = s[n]; n--; } } } void reverse() { int temp; if ( 6 == tail) { direction = !direction; temp = head; head = tail; tail = temp; } else cout< } 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; }