Author: Stan Eisenstat
Subject: Re: [Cs223] clarification in walkthrough
Date: Saturday, 21 Mar 2020, 06:33:25

    > Message Posted By: Unknown
    >
    > could you or Chris explain what is meant in the spec:
    >
    > Notice that without a time constraint, this is trivial - simply use two
    > stacks as an "array." Seek through "array" by popping from one stack and
    > pushing to the other.

Any algorithm that sorts the elements in an array A[]
can access the elements of the array only by reading
(... = A[i]) or writing (A[i] = ...).  Thus for the
case where the elements to sort are on a stack with
the top element being A[0], it suffices to explain how
to read or write the i-th element (i.e., A[i]).

To read A[i] into S:
* Pop and push the top i elements from the stack to
    another stack.
* Pop the top element into S.
* Push S back onto the stack.
* Pop and push the top i elements from the other stack
    to the stack.

To write S to A[i]:
* Pop and push the top i elements from the stack to
    another stack.
* Pop the top element and discard it.
* Push S back onto the stack.
* Pop and push the top i elements from the other stack
    to the stack.

--Stan-