TAOCP 2.2.1 Exercise 1

Section 2.2.1: Stacks, Queues, and Deques

Exercise 1. [06] An input-restricted deque is a linear list in which items may be inserted at one end but removed from either end; clearly an input-restricted deque can operate either as a stack or as a queue, if we consistently remove all items from one of the two ends. Can an output-restricted deque also be operated either as a stack or as a queue?

Verified: no
Solve time: -

Yes. Let the permitted insertion end be $L$, and let deletions be allowed at both $L$ and the opposite end $R$.

To operate as a stack, insert every item at $L$ and always delete from $L$. The most recently inserted item is then the first one removed, so the discipline is LIFO.

To operate as a queue, insert every item at $L$ and always delete from $R$. If the items are inserted in the order $x_1,x_2,\ldots,x_n$, then $x_1$ reaches end $R$ first and is deleted first; subsequently $x_2,x_3,\ldots,x_n$ are deleted in the same order in which they were inserted. Thus the discipline is FIFO.

Therefore an output-restricted deque can be operated either as a stack or as a queue. $\boxed{\text{Yes}}$