Anyone can help me with this algorithm?

1 set up stack in and print it
2 while stack in is not empty repeat
2.1 max = in.pop
2.2 while there are still element in stack in repeat
2.2.1 value = in.pop
2.2.2 if value > max
2.2.2.1 temp.push(max)
2.2.2.2 max = value
2.2.3 else
2.2.3.1 temp.push(value)
2.3 in = temp
2.4 out.push(max)
2.5 temp.clear
3 print sorted stack

Below is my code but it does not working....

#include <iostream>
#include <stack>
using namespace std;

int main ()
{
stack <int> in,out,temp;

int num[] = {50,10,60,40,80,20,70};

cout<<"Unsorted numbers in stack in :"<<endl;

for (int i=0; i<7; i++)
{
in.push(num[i]); 
cout<<in.top()<<endl; //print stack in
}

cout << endl;

while (!in.empty())
{
int max=in.top();

while (!in.empty())
{
in.pop();
int value=in.top();

if (value > max)
{
temp.push(max);
max=value;
}
else
{
temp.push(value);
}
}
in = temp;
out.push(max);
// temp->clear();
}

cout<<"Sorted numbers in stack out :";

for (int i=0; i<7; i++)
{ 
cout<<out.top()<<endl; //print stack in
out.pop();
}

return 0;
}

Edited 5 Years Ago by WaltP: Added CODE Tags -- please use them

I'm taking a look at this program, and the instructions. I'm not sure what "in = temp" is supposed to mean, but I think it's putting you into an infinite loop. (This doesn't appear to be your only bug, though.)

Also, as you appear to have discovered, there's no clear() function for stacks. I'm not sure what your teacher wants this to do.

Also, are you supposed to be using the STL stack implementation, or is the purpose of your assignment to create your -own- stack implementation?

If the former, no problem, you may just need to manually clear your temp stack. How would you go about getting rid of each value on a stack, if you no longer need any of them? Also, the line [code]in = temp;
[/icode] may or may not do what you need, but we can get to that if we need to. More importantly, what do you mean by "my code isn't working"? Are you getting compiler errors? Does it run but not print what you expect to see? We can't see your screen (or read minds); you have to tell us specifically what's going wrong.

When you re-post your revised code, please select it all and click the "[ CODE ]" button at the top of the editor (which will put "[ CODE ]" in front of it and "[ /CODE ]" after it [both without the embedded spaces]). This maintains your formatting and adds the nice line numbers, so we can all better read and comment on your code. Thanks!

Edited 5 Years Ago by raptr_dflo: more input

Hey, raptr -

I've been thinking about this problem on and off a lot today. On the one hand, at first glance, it looks really dumb: I mean, who sorts a *stack?*

On the other hand, though, it is somewhat interesting from an algorithmic perspective. But for the life of me, I can't figure out a way to do it with only the stack data structure. Obviously, there are lots of ways to "cheat," such as dump the stack into an array, linked list or some other structure that lends itself to a sort, but...just within the stack structure, I'm coming up empty.

By the way, what *does* a statement like:

in = temp;

do, anyway?

I'm looking at it. Is the algorithm in your first post from an instructor, or is it yours? (I assume that this is an assignment.) I ask because I'm still trying to figure out why anyone would want to sort a stack. Does the assignment say that you must solve this using only stacks (no arrays, lists, etc), or are you permitted to use other data structures?

Ya..This is my assignment from lecturer...actually my lecturer said can use linked list to do it... but i dont know how.

OK, well that makes a little more sense. What you have to do is:

1. load up your stack (as you're currently doing)
2. pop elements off the stack and insert them into a linked list. You need to insert them in a sorted fashion...I suggest you do a little reading up on them. They're really not that hard to use, and you'll need them at some point in your programming career.
3. load the stack again, this time with the sorted values from the linked list.

This will be MUCH easier than trying to do this with stacks only (which I'm still not sure is even possible).

Take a try at linked lists and come back with whatever problems you encounter.

How? I can't get what you mean..cause I just start learn in this subject.

mzimmers, the algorithm isn't really "sorting a stack", it's using three stacks to sort an arbitrarily-ordered input sequence. Step 2.1 and 2.2.* basically say "transfer all elements except the largest from stack 'in' to stack 'temp' (order doesn't matter here). The rest of step 2.* is "push the largest onto stack 'out'", and move everything from 'temp' back to 'in'". The last bit of that isn't a typical stack operation, but could just as easily be addressed by repeating step 2, only moving all but the largest element from 'temp' back to 'in' and pushing that next-largest value onto 'out'. If you want your head to start spinning, take a look at the PostScript programming language -- it's all about manipulating a stack, with almost no ability to define scopes! :(

fanfunstar, I suspect you're doing fine the way you are, and that the instruction to "use linked lists" means to implement your own stack. If you don't understand how to implement a stack using a linked-list, then just stick with what you're doing for now. But my questions from my original response still hold: What specific errors or incorrect output are you seeing? Can you figure out how to "clear" a stack by yourself? Also, I think your statements are reversed at lines 27-28 in the code you posted originally (though you may have changed it by now). With any luck, that will be enough to get you running.

This article has been dead for over six months. Start a new discussion instead.