(新壳栈)小 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) 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 << "Error: the stack is empty!" << endl; return; } cout << 4 << endl; 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 << "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; }