  Following the footprints of what have been done with the algorithm Stacksort,
we investigate the preimages of the map associated with a slightly less well
known algorithm, called Queuesort. After having described an equivalent version
of Queuesort, we provide a recursive description of the set of all preimages of
a given permutation, which can be also translated into a recursive procedure to
effectively find such preimages. We then deal with some enumerative issues.
More specifically, we investigate the cardinality of the set of preimages of a
given permutation, showing that all cardinalities are possible, except for 3.
We also give exact enumeration results for the number of permutations having
0,1 and 2 preimages. Finally, we consider the special case of those
permutations $\pi$ whose set of left-to-right maxima is the disjoint union of a
prefix and a suffix of $\pi$: we determine a closed formula for the number of
preimages of such permutations, which involves two different incarnations of
ballot numbers, and we show that our formula can be expressed as a linear
combination of Catalan numbers.
