program deck_dyn;
uses CRT;

type pt = ^elem;
     elem = record
           info : byte;
           next,prev : pt;
     end;

function getelem:byte;
var s:byte;
begin
	write('vvedite chislo : ');
	readln(s);
	getelem:=s;
end;

procedure pushbegin(var root,tail:pt;info:byte);
var newelem:pt;
begin
	new(newelem);          (* Sozdat v pamyati novyi element *)
	newelem^.info:=info;
	newelem^.next:=root;   (* Prisoedinit ochered k etomu elementu *)
	newelem^.prev:=NIL;
	if (root<>NIL) then			(* esli ochered ne pusta *)
		root^.prev:=newelem			(* prisoedinit etot element k nachalu ocheredi *)
	else						(* inache *)
		tail:=newelem;				(* sozdat novuyu ochered *)
	root:=newelem;          
end;

procedure popbegin(var root,tail:pt);
var temp:pt;
begin
	if (root<>NIL) then			(* esli ochered ne pusta *)
		begin						
			temp:=root;				(* sohranit adres pervogo elementa *)
			root:=root^.next;		(* otrezat pervyi element ot ocheredy *)
			if (root=NIL) then		
				tail:=NIL		
			else
				root^.prev:=NIL;
			writeln('izvlechennoe znachenie : ',temp^.info); (* vyvesty na ekran znachenie poslednego elementa *)
			dispose(temp);			(* ubrat pervyi element iz pamyati *)
		end
	else						(* inache, esli ochered pusta *)
		Writeln('deq pust');
end;

procedure pushend(var root,tail:pt;info:byte);
var newelem:pt;
begin
	new(newelem);          (* Sozdat v pamyati novyi element *)
	newelem^.info:=info;
	newelem^.next:=NIL;   (* prisoedinit etot element k ocheredi *)
	newelem^.prev:=tail;
	if (tail<>NIL) then			(* esli ochered ne pusta *)
		tail^.next:=newelem			(* prisoedinit etot element k nachalu ocheredi *)
	else						(* inache *)
		root:=newelem;				(* sozdat novuyu ochered *)
	tail:=newelem;
end;

procedure popend(var root,tail:pt);
var temp:pt;
begin
	if (tail<>NIL) then			(* esli ochered ne pusta *)
		begin						
			temp:=tail;				(* sohranit adres poslednego elementa *)
			tail:=tail^.prev;		(* otrezat posledniy element ot ocheredy *)
			if (tail=NIL) then		
				root:=NIL		
			else
				tail^.next:=NIL;
			writeln('izvlechennoe znachenie : ',temp^.info); (* vyvesty na ekran znachenie poslednego elementa *)
			dispose(temp);			(* ubrat posledniy element iz pamyati *)
		end
	else						(* inache, esli ochered pusta *)
		Writeln('deq pust');
end;

procedure showmenu;
begin
	Writeln (' 1) Push v nachalo');
	Writeln (' 2) Pop iz nachala');
	Writeln (' 3) Push v konec');
	Writeln (' 4) Pop iz konca');
	Writeln (' 5) vyhod');
	Write(' -> ');
end;

var root,tail: pt;
	selection : byte;

begin
	Writeln ('deq. dinamicheskaya realizaciya ');
	root:=NIL;
	repeat				
		showmenu;
		readln(selection);	
		case selection of
			1: pushbegin(root,tail,getelem);
			2: popbegin(root,tail);
			3: pushend(root,tail,getelem);
			4: popend(root,tail);
			5: clrscr;
		end;
	until selection=5;	
end.