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.