C++

Forum

 
Reverse Stack

Mar 11, 2012 at 6:50pm
DocCeaser (43)
I'm trying to reverse this linked list stack but I don't really know how to go about. The question says that I should copy the elements of stack 1 into stack 2 in reverse order. Then the old contents of stack 2 are destroyed and stack 1 is unchanged. I was thinking that it might be possible to just pop the elements into another stack. I tried to push the popped element into another stack but I don't know how to write it correctly.
.cpp file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <iostream>
using namespace std;
#include "linkedStackType.h"

int main()
{
 
    linkedStackType stack1;
    linkedStackType stack2;
    
    stack1.push(7);
    stack1.push(12);
    stack1.push(8);
    cout<<stack1.top()<<endl;
    
    //stack2.copyStack(stack1);
    stack1.reverseStack(stack2);
    cout<<stack2.top()<<endl;
    
 
    
    system("pause");
return 0;
}
Edit & run on cpp.sh

.h file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
struct nodeType
{
       int info;
       nodeType *link;
};
class linkedStackType
{
      private:
              nodeType *stackTop;
              
      public:
             linkedStackType();
             bool isEmptyStack();
              bool isFullStack();
              void initializeStack();
              void push(int);
              int top();
              void pop();
              void copyStack(linkedStackType, linkedStackType);
              void reverseStack(linkedStackType);
};
linkedStackType::linkedStackType()
{
     stackTop=NULL;
}
void linkedStackType::push(int n)
{
     nodeType *newNode;
     
     newNode=new nodeType;
     
     newNode->info=n;
     newNode->link=stackTop;
     stackTop=newNode;
}
bool linkedStackType::isEmptyStack()
{
        return(stackTop==NULL);
}
void linkedStackType::initializeStack()
{
     nodeType *temp;
     while(stackTop!=NULL)
     {
        temp=stackTop;
        stackTop= stackTop->link;
        delete temp;
        }
}
bool linkedStackType::isFullStack()
{
      return false;
}
int linkedStackType::top()
{
       assert(stackTop !=NULL);
       return stackTop->info;
}
void linkedStackType::pop()
{
        nodeType *temp;
        
        if(stackTop !=NULL)
        {
        temp=stackTop;
        stackTop=stackTop->link;
        
        }
        else
        cout<<"empty list"<<endl;
} 
void linkedStackType::copyStack(linkedStackType stack2)
{
     nodeType *newNode, *current, *last;
     
     if(stackTop !=NULL)
     initializeStack();
     if(stack2.stackTop==NULL)
     stackTop=NULL;
     else
     {
         current=stack2.stackTop;
         stackTop=new nodeType;
         
         stackTop->info=current->info;
         stackTop->link=NULL;
         last=stackTop;
         current=current->link;
     
     while(current !=NULL)
     {
      newNode=new nodeType;
      
      newNode->info=current->info;
      newNode->link=NULL;
      last->link=newNode;
      last=newNode;
      current=current->link;
      }
      }
}
void linkedStackType::reverseStack(linkedStackType stack1, linkedStackType stack2)
{
      nodeType *newNode, *current, *first, *temp;
      
      while(!stack2.isEmptyStack())
      {
         stack1.pop();
         stack2.push(temp);
      }
}
Mar 11, 2012 at 8:01pm
Texan40 (645)
May not be terribly efficient but perhaps this:

1
2
3
4
5
6
7
8
9
10
 
linkedStackType::reverseStack(linkedStackType stack2)
{
  linkedStackType tmp;
  tmp.copyStack(*this);
  while(!tmp.isEmptyStack())
  {
    stack2.push(tmp.top());
    tmp.pop();
  }
}


The current stack will remain untouched and stack2 will be a reversed copy of it.
Last edited on Mar 11, 2012 at 8:01pm
Mar 11, 2012 at 8:16pm
DocCeaser (43)
what is *this?
Mar 11, 2012 at 8:24pm
Stewbond (2827)
this is a pointer to the current object that has called this class function. *this is the object itself.
Mar 11, 2012 at 8:46pm
DocCeaser (43)
thank you.
Mar 13, 2012 at 2:03am
DocCeaser (43)
Ok I still can't reverse this stack. Can someone please tell me what linkedStackType tmp; and *this are in relation to my program?
Mar 13, 2012 at 2:27am
Texan40 (645)
`linkedStackType tmp' is a temporary stack. Calling `tmpl.copyStack(*this)' puts the contents of the current stack (in this context, stack1) in tmp. You can then unwind tmp (filling stack2 as you go) to have stack1 be untouched and stack2 the reverse of stack1.
Mar 13, 2012 at 2:37am
DocCeaser (43)
When I return the top of stack2 it still says 8 when it should be 7. I don't get why its not reversing.
Mar 13, 2012 at 2:57am
Texan40 (645)
I think this may work without making the copy:
1
2
3
4
5
6
7
8
9
10
11
 
void linkedStackType::reverseStack(linkedStackType stack2)
{
  nodeType *tmp = this->stackTop; // pointer to current stack top
  while(tmp->link != NULL) // unwind till link is null
  {
    stack2.push(tmp->info); // push current element info to stack2
    tmp = tmp->link; // fall back one level
    if(tmp->link == NULL) // last element in stack
      stack2.push(tmp->info); // push last element
  }
}
Mar 13, 2012 at 3:04am
DocCeaser (43)
thank you for helping.
Topic archived. No new replies allowed.