The Power of the Queue
Ming Li, Luc Longpré, Paul M. B. Vitanyi · SIAM Journal on Computing · 1992
Queues, stacks, and tapes are basic concepts that have direct applications in compiler design and the general design of algorithms. Whereas stacks (pushdown store or last-in–first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-in-first-out storage). In this paper a comprehensive study comparing queues to stacks and tapes (off-line and with a one-way input tape) is presented. The techniques used rely on Kolmogorov complexity. In particular, one queue and one tape (or stack) are incomparable: (1) Simulating one stack (and hence one tape) by one queue requires $\Omega (n^{4/3} /\log n)$ time in both the deterministic and the nondeterministic cases. A corollary of this lower bound states that for this model of one-queue machines, nondeterministic linear time is not closed under complement. (2) Simulating one queue by one tape requires $\Omega (n^2 )$ time in the deterministic case and requires $\Omega (n^{4/3}/(\log n)^{2/3} )$ in the nondeterministic case. The paper further compares the relative power between different numbers of queues: (3) Simulating two queues (or two tapes) by one queue requires $\Omega (n^2 )$ time in the deterministic case, and $\Omega (n^2 /(\log ^2 n\log \log n))$ in the nondeterministic case. The deterministic bound is tight. The nondeterministic one is almost tight. The upper bounds for queues are also obtained.