C++

Forum

 
Reverse Stack

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;
}

.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);
      }
}
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
DocCeaser (43)
what is *this?
Stewbond (2827)
this is a pointer to the current object that has called this class function. *this is the object itself.
DocCeaser (43)
thank you.
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?
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.
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.
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
  }
}
DocCeaser (43)
thank you for helping.
Topic archived. No new replies allowed.