Here is a proposal for a queue implementation that no one will ever need It has been inspired by the discussed implementation in “The Art of Prolog” but is not identical.

```
:- module(queue,
[ empty_queue/1,
list_queue/2,
queue_head/3,
list_queue_head/3,
queue_last/3,
list_queue_last/3,
queue_length/2 ]).
/** <module> A queue implementation
This provides a queue data structure that allows constant-time
insertion from either the front or the back of the queue, and
constant-time removal of elements from the front.
The implementation is based on the code presented on pages 50-51
of "The Craft of Prolog" by O'Keefe (1990).
*/
:- begin_tests(queue).
test(empty,
[ true(L == []),
true(N == 0) ]) :-
empty_queue(Q),
list_queue(L, Q),
queue_length(Q, N).
test(empty_pop, [ fail ]) :-
empty_queue(Q),
queue_head(_, _, Q).
test(empty_and_pop, [ fail ]) :-
list_queue([a,b], Q0),
queue_head(_, Q1, Q0),
queue_head(_, Q2, Q1),
queue_head(_, _, Q2).
test(from_list,
[ true(X == a),
true(N == 2) ]) :-
list_queue([a,b,c], Q0),
queue_head(X, Q1, Q0),
queue_length(Q1, N).
test(to_list, [ true(L = [a,b,c]) ]) :-
empty_queue(Q0),
foldl(queue_last, [a,b,c], Q0, Q1),
list_queue(L, Q1).
test(stack, [ true(X == c) ]) :-
empty_queue(Q0),
foldl(queue_head, [a,b,c], Q0, Q1),
queue_head(X, _, Q1).
test(queue, [ true(X == a) ]) :-
empty_queue(Q0),
foldl(queue_last, [a,b,c], Q0, Q1),
queue_head(X, _, Q1).
test(pop_list_head, [ true(H == [x,y,a]) ]) :-
list_queue([x,y], Q0),
foldl(queue_last, [a,b,c], Q0, Q1),
length(H, 3),
list_queue_head(H, _, Q1).
test(push_list_head, [ true(X == x) ]) :-
list_queue([a,b,c], Q0),
list_queue_head([x,y,z], Q0, Q1),
queue_head(X, _, Q1).
test(backtrack_list_head,
[ all(H == [[], [a], [a,b]]) ]) :-
list_queue([a,b], Q),
list_queue_head(H, _, Q).
test(push_list_last,
[ true(X == x),
true(Y == y),
true(Z == a) ]) :-
list_queue([x,y], Q0),
list_queue_last([a,b,c], Q0, Q1),
queue_head(X, Q2, Q1),
queue_head(Y, Q3, Q2),
queue_head(Z, _, Q3).
:- end_tests(queue).
%! empty_queue(-Queue) is semidet.
%
% Queue is an empty queue.
empty_queue(q(0, B, B)).
%! queue_length(+Queue, -Length) is semidet.
%
% Length is the number of elements in Queue.
queue_length(q(S, F, B), N) :-
ql(S, F, B, Len_expr),
N is Len_expr.
ql(0, B, B, 0).
ql(s(S), [_|F], B, N+1) :-
ql(S, F, B, N).
%! list_queue(?List, ?Queue) is nondet.
%
% Two-way conversion between a list and a queue.
list_queue(L, q(S, F, B)) :-
lq(L, S, F, B).
lq([], 0, B, B).
lq([X|Xs], s(S), [X|F], B) :-
lq(Xs, S, F, B).
%! queue_head(?Head, ?Queue0, ?Queue1) is semidet.
%
% Queue0 with Head at the front is Queue1.
% Can be used to pop or push to the head of a queue.
queue_head(X, q(S, F, B), q(s(S), [X|F], B)).
%! list_queue_head(?List, Queue0?, Queue1) is semidet.
%
% Queue0 with List at the front is Queue1.
% Can be used to pop or push a list at the front of
% the queue.
list_queue_head(L, q(S0, F0, B), q(S, F, B)) :-
lqh(L, S0, F0, S, F).
lqh([], S, F, S, F).
lqh([X|Xs], S0, F0, s(S), [X|F]) :-
lqh(Xs, S0, F0, S, F).
%! queue_last(+Last, -Queue0, +Queue1) is semidet.
%
% Queue1 is Queue0 with Last inserted at its back.
queue_last(X, q(S, F, [X|B]), q(s(S), F, B)).
%! list_queue_last(+List, +Queue0, -Queue1) is semidet.
%
% Queue1 is Queue0 with List at its back.
list_queue_last(L, q(S0, F, B0), q(S, F, B)) :-
lql(L, S0, B0, S, B).
lql([], S, B, S, B).
lql([X|Xs], S0, [X|B0], s(S), B) :-
lql(Xs, S0, B0, S, B).
```