TAOCP 2.2.2 Exercise 2

Section 2.2.2: Sequential Allocation

Exercise 2. [22] Generalize the method of (6a) and (7a) so that it will apply to any deque with fewer than $M$ elements. In other words, give specifications for the other two operations, "delete from rear" and "insert at front."

Verified: no
Solve time: -

Solution

In addition to the front pointer F and rear pointer R, introduce the convention that the deque occupies the circular array X[1],\ldots,X[M], with F pointing to the front element and R to the rear element whenever the deque is nonempty. As in (6a) and (7a), the condition F = R will represent the empty deque. Since one array position must remain unused in order to distinguish emptiness from fullness, the deque can contain fewer than $M$ elements.

The operations already given are:

Insert at rear

$$ X \Leftarrow Y: \begin{cases} \text{if } R=M,\text{ then }R\leftarrow1,\text{ otherwise }R\leftarrow R+1;\ \text{if } R=F,\text{ then OVERFLOW;}\ X[R]\leftarrow Y. \end{cases} $$

Delete from front

$$ Y \Leftarrow X: \begin{cases} \text{if } F=R,\text{ then UNDERFLOW;}\ \text{if } F=M,\text{ then }F\leftarrow1,\text{ otherwise }F\leftarrow F+1;\ Y\leftarrow X[F]. \end{cases} $$

The remaining two operations are obtained by symmetry.

For deletion from the rear, first test whether the deque is empty. If it is not empty, remove the element currently indexed by R, then move R one position backward around the circle:

$$ Y \Leftarrow X \text{ (delete from rear): } \begin{cases} \text{if } F=R,\text{ then UNDERFLOW;}\ Y\leftarrow X[R];\ \text{if } R=1,\text{ then }R\leftarrow M,\text{ otherwise }R\leftarrow R-1. \end{cases} $$

For insertion at the front, move F one position backward around the circle, test whether this causes coincidence with R, and if not, store the new item in the newly created front position:

$$ X \Leftarrow Y \text{ (insert at front): } \begin{cases} \text{if } F=1,\text{ then }F\leftarrow M,\text{ otherwise }F\leftarrow F-1;\ \text{if } F=R,\text{ then OVERFLOW;}\ X[F]\leftarrow Y. \end{cases} $$

These four specifications together implement all deque operations on a circular array of size $M$, with overflow occurring precisely when the insertion would eliminate the single unused position that separates the empty and full states.

$$ \boxed{ \begin{aligned} &\text{Delete from rear:}\ &\qquad \begin{cases} \text{if }F=R,\text{ then UNDERFLOW;}\ Y\leftarrow X[R];\ \text{if }R=1,\text{ then }R\leftarrow M,\text{ otherwise }R\leftarrow R-1; \end{cases} \[2ex] &\text{Insert at front:}\ &\qquad \begin{cases} \text{if }F=1,\text{ then }F\leftarrow M,\text{ otherwise }F\leftarrow F-1;\ \text{if }F=R,\text{ then OVERFLOW;}\ X[F]\leftarrow Y. \end{cases} \end{aligned} } $$