  We provide the first algorithm that under minimal assumptions allows to
simulate the stationary waiting-time sequence of a single-server queue
backwards in time, jointly with the input processes of the queue (inter-arrival
and service times). The single-server queue is useful in applications of DCFTP
(Dominated Coupling From The Past), which is a well known protocol for
simulation without bias from steady-state distributions. Our algorithm
terminates in finite time assuming only finite mean of the inter-arrival and
service times. In order to simulate the single-server queue in stationarity
until the first idle period in finite expected termination time we require the
existence of finite variance. This requirement is also necessary for such idle
time (which is a natural coalescence time in DCFTP applications) to have finite
mean. Thus, in this sense, our algorithm is applicable under minimal
assumptions.
