Zdroj



% sestrojte FIFO frontu s konstantním časem na operaci
%  (push a pop můžou být destruktivní, stačí amortizovaně)

% fifo_new(-Fronta)

% fifo_peek(+Fronta, -PrvekNaŘadě)

% fifo_push(+Fronta, +Prvek, -VýslednáFronta)

% fifo_pop(+Fronta, -Prvek, -VýslednáFronta)


% 1. možnost: fronta je rozdílový seznam
%  (s přidávnáním na konec)
fifo_new(K-K).

fifo_peek(S-_, P) :- nonvar(S), S = [P|_].

fifo_push(S-K1, P, S-K2) :- K1 = [P|K2].

fifo_pop(S1-K, P, S2-K) :- nonvar(S1), S1 = [P|S2].


% 2. možnost: amortizovaně a nedestruktivně,
%  se dvěma obyčejnými seznamy které reprezentují
%  výstupní konec fronty v pořadí výstupu
%  a vstupní konec fronty v obráceném pořadí

Dotazy



?- fifo_new(F).
F = _G3011-_G3011.

?- fifo_new(F), fifo_peek(F,V).
false.

?- fifo_new(F), fifo_pop(F,V,F2).
false.


?- fifo_new(F0),
   fifo_push(F0, 1, F1),
   fifo_peek(F1, V1),
   fifo_push(F1, 2, F2), fifo_push(F2, 3, F3),
   fifo_pop(F3, I1, F4), I1==1,

   fifo_push(F4, 4, F5), fifo_push(F5, 5, F6),
   fifo_pop(F6, 2, F7), fifo_pop(F7, 3, F8),
   fifo_pop(F8, 4, F9), fifo_pop(F9, 5, F10),
   \+ fifo_peek(F10, _),

   fifo_push(F10, 10, F11),
   fifo_peek(F11, 10),
   fifo_pop(F11, 10, V).
F0 = [1, 2, 3, 4, 5, 10|_G156]-[1, 2, 3, 4, 5, 10|_G156],
%....
V1 = I1, I1 = 1,
V = _G156-_G156.