(新壳栈)小 Z 设计了一种新的数据结构“新壳栈”。首先,它和传统的栈一样支持压入、弹出操作。此外,其栈顶的前 c 个元素是它的壳,支持翻转操作。其中,c > 2 是一个固定的正整数,表示壳的厚度。小 Z 还希望,每次操作,无论是压入、弹出还是翻转,都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗?
程序期望的实现效果如以下两表所示。其中,输入的第一行是正整数 c,之后每行输入都是一条指令。另外,如遇弹出操作时栈为空,或翻转操作时栈中元素不足 c 个,应当输出相应的错误信息。
const NSIZE = 100000; CSIZE = 1000; var n, c, r, tail, head : longint; s : array[1..NSIZE] of longint; //数组s模拟一个栈,n为栈的元素个数 q : array[1..CSIZE] of longint; //数组q模拟一个循环队列,tail为队尾的下标,head为队头的下标 direction, empty : boolean; function previous(k : longint) : longint; begin if direction then previous := ((k + c - 2) mod c) + 1; else previous := (k mod c) + 1; end; function next(k : longint) : longint; begin if direction then 1 else next := ((k + c - 2) mod c) + 1; end; procedure push; var element : longint; begin read(element); if next(head) = tail then begin inc(n); 2; tail := next(tail); end; if empty then empty := false else head := next(head); 3 := element; end; procedure pop; begin if empty then begin writeln('Error: the stack is empty!'); exit; end writeln( 4 ); if tail = head then empty := true else begin head := previous(head); if n > 0 then begin tail := previous(tail); 5 := s[n]; dec(n); end; end; end; procedure reverse; var temp : longint; begin if 6 = tail then begin direction := not direction; temp := head; head := tail; tail := temp; end else writeln('Error:less than', c, ' elements in the stack!'); end; begin readln(c); n := 0; tail := 1; head := 1; empty := true; direction := true; repeat read(r); case r of 1 : push; 2 : pop; 3 : reverse; end; until r = 0; end.