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-PREV INDEX NEXT