Alphabetizing stacks

[Joe English]

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

Sounds like you want a priority queue, not a stack.  The basic idea
behind a priority queue is that "pop" or "retrieve" always returns
the smallest element, so they can be used for sorting.

There's lots of ways to implement a pqueue;  using your current data
structure you can simply keep the linked list sorted by making "push"
move down the list until it finds the first element greater than the
one to be inserted and putting it there.  A series of N pushes take
on the order of N^2 operations on average, though; pops are still
constant time.

For the cost of an extra pointer per node, you can use a binary tree
to store the data, then rearrange it before retrieving elements.
This doesn't work quite as well if you want to intermix "push"
and "pop" calls, but the whole operation is O(N log N) average
case, O(N^2) worst case.

For the cost of an extra pointer and an integer per node, you can
implement a really neat structure called a "leftist heap."  This is
one of my personal favorites.

You can also use an array heap.  This is probably the best way to go,
since it's also O(N log N) for N insertions and N deletions and has a
low space overhead.  (The array would have to be dynamically resized,
though, and on average half the space is unused; if the keys are
small compared to the size of a pointer you still might save space.)

Of course, if you really *do* want a stack (i.e., if you want LIFO
behaviour for a while, then at some point need to sort whatever's
still in the stack) some modifications will be necessary.


Hope this helps.  E-mail me if you'd like more info...

--Joe English

  jeenglis at alcor.usc.edu