Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!uhccux!munnari.oz.au!cs.mu.oz.au!ok
From: ok@cs.mu.oz.au (Richard O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: The coding of Queue
Message-ID: <2104@munnari.oz.au>
Date: 14 Sep 89 08:36:06 GMT
References: <1713@thumper.bellcore.com>
Sender: news@cs.mu.oz.au
Lines: 20

In article <1713@thumper.bellcore.com>, yowjian@thumper.bellcore.com (Jian Lin) writes:
> 	queue_last(X, q(N,F,[X|B]), q(s(N),F,B)).
> It also implies that I should use only the mode queue_last(+, +, -).

Well, queue_last(?, +, -), but yes, you can't use this clause to pop things
off the end of a queue.
	queue_head(X, q(N,F,B), q(s(N),[X|F],B)).
_can_ be used both ways around, but not queue_last/3.  (The problem is
related to the fact that lists can share _suffixes_ but not _prefixes_.)

> Now, suppose that I want to use queue_last in various modes (e.g.
> queue_last(+, -, +) to undo the enqueue operation).
> Is there any way that I can issue and undo an enqueue operation using the
> same clause with different modes (in constant time)?

Those same course notes describe the well known "back to back lists"
implementation of queues which works in constant *average* time provided
you don't backtrack over a "flip" too often.  With that representation,
queues of ground terms are themselves ground, so you can "undo" a queueing
operation simply by keeping a copy of the original state.