• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting a stack  RSS feed

 
Cody Peterson
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All. For homework, we have been given an assignment which requires us to create a static method which takes a stack and a series of auxiliary stacks and sort the stack such that the smallest thing is at the top of the stack. Now, my first thought is that sorting a stack seems weird, but I get that it's homework and it's the brain exercise that counts.

While it's not much, what I have so far is below.



Based on my reasoning, it seems like it would be easiest to read through the unsortedStack, copy its contents to an array, sort the array, and push the array contents in order, onto sortedStack, but I think that's cheating since the professor said he wanted the stack to extend comparable. And that's where I am running into problems.

First, how do you have a stack that implements comparable?

Second, how should you actually sort this? Between push() pop() peek() and empty(), I am not sure how to sort the items then push them on to a new stack.

Thanks!
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It doesn't make sense for the Stack to implement Comparable. You would want the things in the stack to implement Comparable, so that the sort routine could compare one to the other to see which is "less", or, possibly, the Stack could implement Comparator, so that the sort routine can ask the Stack to compare to items.

Note that using Comparable doesn't contraindicate sorting the array. If you're going to sort it using Arrays.sort(), you have to have a Comparable or Comparator. If you write your own sort routine, you don't have to use C'able/C'ator, but it would still be a reasonable approach. Note that if you're calling Arrays.sort(), you'll define the compareTo() or compare(), but you'll never call them yourself--the sort() method does.

Having said all that, I don't know what the actual parameters to the assignment are, so I can't advise you which specific approach you should take.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Cody Peterson wrote:
Second, how should you actually sort this? Between push() pop() peek() and empty(), I am not sure how to sort the items then push them on to a new stack.
Thanks!


Again, not knowing the specific requirements of the assignment, it's hard to say. Those would be the public methods of the Stack, but maybe it has a private method for sorting. Or maybe, as you said, you pop from one stack into some other structure, such as a List, and then sort the List and push back into the stack, or into a different Stack.
 
Cody Peterson
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for your input, Jeff.

I received a little clarification from the professor and he told me that we can use multiple stacks, like was mentioned before, and that the only requirement is that whatever you store must extend/implement comparable. That doesn't really help much but maybe it helps someone around here understand better.

I don't think he wants us to dump the items into a different data structure to sort so with that being said, how would you sort using only two stacks? I keep trying to use the analogy of taking a stack of 10 playing cards in random order, and having "two stacks, " one of them is unsorted (the original stack) and the other is empty. Even in following this line of thinking, if I were to sort them, the first thing I would do is unstack them (like dump them into a list or an array) and then put them back into a stack once sorted.
 
Campbell Ritchie
Marshal
Posts: 56546
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another way to do it is to design a tree list structure, which adds items to lists in a tree. You sort them as you pop them from the stack and add them to the list, then you do an in-order depth first traversal of the tree, pushing all the elements of all the lists back onto a stack.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Cody Peterson wrote:Thanks for your input, Jeff.

I received a little clarification from the professor and he told me that we can use multiple stacks, like was mentioned before, and that the only requirement is that whatever you store must extend/implement comparable. That doesn't really help much but maybe it helps someone around here understand better.

I don't think he wants us to dump the items into a different data structure to sort so with that being said, how would you sort using only two stacks? I keep trying to use the analogy of taking a stack of 10 playing cards in random order, and having "two stacks, " one of them is unsorted (the original stack) and the other is empty. Even in following this line of thinking, if I were to sort them, the first thing I would do is unstack them (like dump them into a list or an array) and then put them back into a stack once sorted.


I'm not sure what he's suggesting the second stack for. Maybe you're supposed to leave the original stack untouched, (or rather, restore it to its original state after copying it) and create the second stack in sorted order. If this is the case, then I would go with a List as an intermediate data structure.

The only other reason I can imagine using it is if the stack internally sorts items as they are added. But that makes for weird, non-stack-like push() behavior. Sounds like a bizarre assignment, and I'm not really sure what he's driving at or what concepts he's trying to drill on.

What don't you understand about having the Stack's elements implement Comparable?
 
Campbell Ritchie
Marshal
Posts: 56546
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is slightly more complicated than it seems. You can make a List<Comparable> or a Stack<Comparable> etc. But Comparable is itself parameterised. It’s not Comparable, but Comparable<T>. And the compareTo method is inherited. So the comparable might be in a superclass of T. And you might be storing a subclass of T. So you have to declare your stack like this
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Normally i would recommend that you do the ole paper and pencil thing, but with stacks, i always suggest real physical, stackable things like coasters or paper plates or 3x5 cards -- anything you can stack.

Now - assuming one input stack, one output stack, one holding stack and one temp stack. Ok if we (one at a time, as that is all we have) pop a plate from the input stack to the temp stack (do this until the input stack is empty). At this point the temp stack has all of the items that used to be in the input stack, in the same relative order, but reversed (i.e.: top of the original input is now the bottom of temp and bottom of original input is now the top of temp). Ok, now pop all of the temp items and push onto the hold stack -- hold now has the nodes in the same order as the original input. And we can do it once more from hold to temp to output. Now the output stack has the contents of the original input stack. --- nothing great here, just that we can copy and keep the order as expected.

while this wasn't very exciting, you now know that you take an input stack - copy (or move) it to a holding stack, and then copy the holding stack to an output stack and return that value.

Now for the fun part:

Lets create two temp stacks and assume that we have populated the hold stack.

Now pop the top value from the hold stack with your left hand and move it to the left stack. Now compare the top of the hold stack to the left stack if the top of hold is greater than the node on the left stack push it on the left stack - and compare the next top of hold with left. If it is smaller - pop it and push it on the right stack. Ok - now compare top of left to top of right. Take the biggest pop it - push it on hold. And while there are still plates on both left and right - get the largest, pop and push on hold.

what you have now is a partial ordering of the stack (or said another way, you have increased the partial ordering of the stack by 1.

Now do it again - pop from hold to left - smaller on goes on right - until there is no plate on the right -- then simply pop left to the output stack and you are done.

 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!