(新壳栈)小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
next:=k mod c+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);
s[n]:=q[tail] ;
tail := next(tail);
end;
if empty then
empty := false
else
head := next(head);
q[head] := element;
end;
procedure pop;
begin
if empty then
begin
writeln('Error: the stack is empty!');
exit;
end:
writeln( q[head] );
if tail = head then
empty := true
else
begin
head := previous(head);
if n > 0 then
begin
tail := previous(tail);
q[tail] := s[n];
dec(n);
end;
end;
end;
procedure reverse;
var
temp :longint;
begin
if next(head) = 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.