不是VIP会员,不能显示答案

题目解答

题目:
(新壳栈)小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.
考点: 0
分析:
解答: 完善特殊栈的入栈、出栈、栈顶C个元素翻转操作
评论:
老师: 0