jtanner@jack.sns.com (Jason Tanner) (04/21/91)
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 ientered (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 Thank you! -- |----------------------------------------------------------------------------| | jtanner@jack.sns.com - - Coke IS it! - - Ask me, I don't work here | | This space was intentionally left filled. | |------------------------------Dare to think!--------------------------------|
bhoughto@pima.intel.com (Blair P. Houghton) (04/22/91)
In article <1991Apr21.121232.2659@jack.sns.com> jtanner@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."
ptgarvin@corona.ecn.uoknor.edu (PTed Garvin) (04/22/91)
In article <1991Apr21.121232.2659@jack.sns.com> jtanner@jack.sns.com (Jason Tanner) writes: > [wants to alphabetize a Stack] Are you wanting to use any other data structures? Have you ever heard of the "Towers of Hanoi" problem? Essentially, that is an alphabetization problem, where one wants to have the disks ordered from largest to smallest. I'd pop all the items off the stack, put them in an array, alphabetize the array, then push them all back. Sounds nasty, especially if you do this every time you push. If an alphabetized list is important, a stack might not be the best data structure (assuming you only access one end). Perhaps some form of bastard stack, where you can insert in the middle, but remove only from the top. (Insertion sort). I refer you to book on Data Structures. -- "...just when I had you wriggling in the crushing grip of reason, too..." ptgarvin@aardvark.ucs.uoknor.edu / ptgarvin@uokmax.UUCP | Wassail! O in the Society: Padraig Cosfhota o Ulad / Barony of Namron, Ansteorra | Disclaimer: Fragile. Contents inflammable. Do not use near open flame. ___|___
jeenglis@alcor.usc.edu (Joe English) (04/22/91)
jtanner@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@alcor.usc.edu