TAOCP 2.2.2 Exercise 19
With $0$-origin indexing, the available array positions are X[0], X[1], \ldots, X[M-1].
Section 2.2.2: Sequential Allocation
Exercise 19. [16] (0-origin indexing.) Experienced programmers learn that it is generally wise to denote the elements of a linear list by $X[0], X[1], \ldots, X[n-1]$, instead of using the more traditional notation $X[1], X[2], \ldots, X[n]$. Then, for example, the base address $L_0$ in (1) points to the smallest cell of the array.
Revise the insertion and deletion methods (2a), (3a), (6a), and (7a) for stacks and queues so that they conform to this convention. In other words, change them so that the list elements will appear in the array $X[0], X[1], \ldots, X[M-1]$, instead of $X[1], X[2], \ldots, X[M]$.
Verified: no
Solve time: 45s
Solution
With $0$-origin indexing, the available array positions are
$$ X[0], X[1], \ldots, X[M-1]. $$
The stack pointer should therefore indicate the index of the current top element, and an empty stack should satisfy $T=-1$. Likewise, the circular queue should use indices modulo $M$ in the range $0,\ldots,M-1$.
The revised algorithms are obtained by replacing the bounds $1$ and $M$ by $0$ and $M-1$ respectively, and by changing the initial conditions so that the empty structures are represented correctly.
For a stack:
$$ X \Leftarrow Y \text{ (insert into stack): } \begin{cases} T \leftarrow T + 1;\ \text{if } T \ge M,\text{ then OVERFLOW;}\ X[T] \leftarrow Y. \end{cases} $$
The empty stack has $T=-1$. After the first insertion, $T=0$, and the item is stored in $X[0]$. After $M$ successful insertions, $T=M-1$ and the stack occupies exactly the cells $X[0],\ldots,X[M-1]$. Any further insertion gives $T=M$ and causes overflow.
For deletion from a stack:
$$ Y \Leftarrow X \text{ (delete from stack): } \begin{cases} \text{if } T < 0,\text{ then UNDERFLOW;}\ Y \leftarrow X[T];\ T \leftarrow T - 1. \end{cases} $$
When the stack contains exactly one item, $T=0$; deletion removes $X[0]$ and restores the empty-stack condition $T=-1$.
For a queue, let the initial setting be
$$ F=R=0. $$
The condition $F=R$ then signifies an empty queue. Insertion advances $R$ one step around the circle before storing the new item:
$$ X \Leftarrow Y \text{ (insert into queue): } \begin{cases} \text{if } R = M-1,\text{ then } R \leftarrow 0,\text{ otherwise } R \leftarrow R + 1;\ \text{if } R = F,\text{ then OVERFLOW;}\ X[R] \leftarrow Y. \end{cases} $$
Deletion is correspondingly
$$ Y \Leftarrow X \text{ (delete from queue): } \begin{cases} \text{if } F = R,\text{ then UNDERFLOW;}\ \text{if } F = M-1,\text{ then } F \leftarrow 0,\text{ otherwise } F \leftarrow F + 1;\ Y \leftarrow X[F]. \end{cases} $$
These formulas are the exact analogues of (6a) and (7a), with the circular indexing changed from the range $1,\ldots,M$ to the range $0,\ldots,M-1$. The queue can contain at most $M-1$ items, since one position must remain unused in order to distinguish the conditions $F=R$ (empty) and overflow.
The revised initial conditions are therefore
$$ T=-1 $$
for stacks, and
$$ F=R=0 $$
for queues.
Hence the required $0$-origin versions are
$$ \boxed{ \begin{aligned} &X \Leftarrow Y\ \text{(stack insertion):}\ &T\leftarrow T+1;\ \text{if }T\ge M\text{ then OVERFLOW;}\ X[T]\leftarrow Y; \[6pt] &Y \Leftarrow X\ \text{(stack deletion):}\ &\text{if }T<0\text{ then UNDERFLOW;}\ Y\leftarrow X[T];\ T\leftarrow T-1; \[6pt] &X \Leftarrow Y\ \text{(queue insertion):}\ &\text{if }R=M-1\text{ then }R\leftarrow0\text{ otherwise }R\leftarrow R+1;\ &\text{if }R=F\text{ then OVERFLOW;}\ X[R]\leftarrow Y; \[6pt] &Y \Leftarrow X\ \text{(queue deletion):}\ &\text{if }F=R\text{ then UNDERFLOW;}\ &\text{if }F=M-1\text{ then }F\leftarrow0\text{ otherwise }F\leftarrow F+1;\ &Y\leftarrow X[F]. \end{aligned} } $$
$$ \boxed{T=-1,\qquad F=R=0.} $$