defstruct(queue(in=[], out=[]))$

enqueue(x, q) := (q@in: cons(x, q@in), done)$

dequeue(q) := (if not emptyp(q@out) then first([first(q@out), q@out: rest(q@out)])
elseif emptyp(q@in) then 'fail
else (q@out: reverse(q@in), q@in: [], first([first(q@out), q@out: rest(q@out)])))$

q:new(queue);    /* queue([], []) */
enqueue(1, q)$
enqueue(2, q)$
enqueue(3, q)$
dequeue(q);      /* 1 */
enqueue(4, q)$
dequeue(q);      /* 2 */
dequeue(q);      /* 3 */
dequeue(q);      /* 4 */
dequeue(q);      /* fail */