Stack

[fiji885]

Well, one of my assignments is to reverse a stack via recursion and meet some requirements. OK, sounds fair enough. I should be reversing a stack, but it's not being reversed at all.

I have to reverse a stack using only one additional stack and non-array variables. So I thought "OK, this is a recursive question". ezpz, or so I thought.

The second parameter is just the size of the stack when first invoked.

void ReverseStack(std::stack<int>& S, size_t size) {
  /* Here is a cheeky way way that doesn't really meet requirements. But it
   *   works
   *
   *      static std::stack<int> ss;
   *      std::swap(ss, S);
   *      while(!ss.empty()) {
   *        S.push(ss.top());
   *        ss.pop();
   *      }
   *
   */

  static std::stack<int> ss;
  if(size == 0) return;
  ss.push(S.top());
  S.pop();
  int tmp = ss.top();
  ReverseStack(S, size-1);
  S.push(tmp);

}

I thought this would reverse the stack, but when I go through it, the output is

The stack is as follows
15 27 14 8 21 48 1 17 32 27 

Here is the stack after reversing
15 27 14 8 21 48 1 17 32 27 

Help would be greatly appreciated!

[jonnin]

your recursion is reversing your reverse, putting it back like it was originally.
if not asking for recursion, don't use it maybe. but if you must, try moving the push tmp before the recursive call.

do you see it? for a stack 1234
tmp is 1, 2, 3, 4
but doing it after the recursive calls, the first one to push is 4, then 3 (34) then 2 (234) then 1 (1234)

[fiji885]

jonnin, thank you for replying.

jonnin wrote:

try moving the push tmp before the recursive call

I originally thought of that too, but it the results were still the same. I am not sure why.

I managed to get it working with this:

void ReverseStack(std::stack<int>& S, size_t size) {
  static std::stack<int> ss;
  static bool moved = false;
  if(!moved) {
    while(!S.empty()) { 
      ss.push(S.top());
      S.pop();
    }
    moved = true;
  }
  if(size == 0) return;
  int tmp = ss.top();
  ss.pop();
  ReverseStack(S, size-1);
  S.push(tmp);
}

The stack is as follows
1 2 3 4 

Here is the stack after reversing
4 3 2 1