TAOCP 2.2.1 Exercise 6
With a queue, the first item inserted is always the first item removed.
Section 2.2.1: Stacks, Queues, and Deques
Exercise 6. [00] Consider the problem of exercise 2, with a queue substituted for a stack. What permutations of $12\ldots n$ can be obtained with use of a queue?
Verified: no
Solve time: -
With a queue, the first item inserted is always the first item removed. Since the input arrives in the order $1,2,\ldots,n$, item $1$ must leave before item $2$, item $2$ must leave before item $3$, and so on. Therefore the output order must preserve the relative order of all elements.
Consequently no permutation other than the identity permutation can be obtained. The permutation
$$ 12\ldots n $$
is obtained by inserting each element into the queue and then deleting it when it reaches the front, and every possible sequence of queue operations yields this same order because a queue is first-in-first-out.
Hence the set of obtainable permutations consists of exactly one permutation:
$$ \boxed{12\ldots n}. $$