Alphabetizing stacks

[Blair P. Houghton]

In article <1991Apr21.121232.2659 at jack.sns.com> jtanner at jack.sns.com (Jason Tanner) writes:
>
>  I have been faced with an interesting dilema. in a
>program I am writing I need to alphabetize a Stack (of any
>length). The alphabetizing will occur after the stack is
>entered (push) and before I start removing things from it
>(pop).  The only pointers in the stack are ptrtop (top of
>stack) and ptrnext(used to point to each members next
>member) and ptrnew but this is used just for pushing on new
>members of the stack.  Any ideas on aplhabetizing stacks
>please post here.  If anyone has actuall example sourc-code
>of this please send it via private mail

What you need to do is create more stacks and solve
the Generalized, Infinite-Disc Tower of Hanoi problem. :-)

Actually, if you can't alphabetize it while entering elements,
and you can't use qsort(3) (which you can't do because you
have a linked-list and not an array), you'll have to create
another list, pop from the stack and enter into the list in
reverse-alphabetic order, then run through the list pushing
the elements onto the stack (reversing them back to alphabetical
order).

What I don't get is why there's a "ptrnew".  If it's a holder
for the newly-malloc'ed stack member _before_ you've pushed
it onto the stack, then it makes sense.  Otherwise it's got
to be redundant for something (barring the fact that what you
have isn't really a stack).

Here's one for the final exam:
If you're allowed to abuse ptrnew (not by casting, but
by using it for elements already in the middle of the
stack), can you alphabetize the stack in-situ?

When all else fails, get a copy of Knuth's _Searching_and_Sorting_
or _Sorting_and_Searching_, or vol. III, or whatever...

				--Blair
				  "I may be smiling, but I'm not kidding."