I NEED HELP WITH A STACK UPDATING FUNCTION

Below is my class to create stackType objects, I have a problem in particular with the member function update(). update() is suppose to search the stack for parameter "t" -If found "t" must be removed from its location in the stack and put on top of the stack. -If not found, the bottom element in the stack must be removed and "t" put on top of the stack. I've tried everything I could to solve this one but I've failed. PLEASE HELP.
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
//Header file: myStack.h

#ifndef H_StackType
#define H_StackType
 
#include <iostream>
#include <cassert>

#include "stackADT.h"

using namespace std;

//*************************************************************
// Author: D.S. Malik
//
// This class specifies the basic operation on a stack as an 
// array.
//*************************************************************

template <class Type>
class stackType: public stackADT<Type>
{
public:
    const stackType<Type>& operator=(const stackType<Type>&); 
      //Overload the assignment operator.

    void initializeStack();
      //Function to initialize the stack to an empty state.
      //Postcondition: stackTop = 0;

    bool isEmptyStack() const;
      //Function to determine whether the stack is empty.
      //Postcondition: Returns true if the stack is empty,
      //    otherwise returns false.

    bool isFullStack() const;
      //Function to determine whether the stack is full.
      //Postcondition: Returns true if the stack is full,
      //    otherwise returns false.

    void push(const Type& newItem);
      //Function to add newItem to the stack.
      //Precondition: The stack exists and is not full.
      //Postcondition: The stack is changed and newItem is
      //    added to the top of the stack.

    Type top() const;
      //Function to return the top element of the stack.
      //Precondition: The stack exists and is not empty.
      //Postcondition: If the stack is empty, the program 
      //    terminates; otherwise, the top element of the stack
      //    is returned.

    void pop();
      //Function to remove the top element of the stack.
      //Precondition: The stack exists and is not empty.
      //Postcondition: The stack is changed and the top element is
      //    removed from the stack.
    
    void update(Type t);
    //Function to move t from whatever position in the stack to
    //the top of the stack.
    //Precondition: the stack exist and it is not empty.
    //Postcondition: t is moved from its position in the top to the 
    //top of the stack.


    stackType(int stackSize = 100); 
      //Constructor
      //Create an array of the size stackSize to hold 
      //the stack elements. The default stack size is 100.
      //Postcondition: The variable list contains the base address 
      //   of the array, stackTop = 0, and maxStackSize = stackSize

    stackType(const stackType<Type>& otherStack); 
      //Copy constructor

    ~stackType(); 
      //Destructor
      //Remove all the elements from the stack.
      //Postcondition: The array (list) holding the stack 
      //    elements is deleted.

private:
    int maxStackSize; //variable to store the maximum stack size
    int stackTop;     //variable to point to the top of the stack
    Type *list; //pointer to the array that holds the stack elements

    void copyStack(const stackType<Type>& otherStack); 
      //Function to make a copy of otherStack.
      //Postcondition: A copy of otherStack is created and assigned
      //    to this stack.
};

template <class Type>
void stackType<Type>::initializeStack()
{
    stackTop = 0;
}//end initializeStack

template <class Type>
bool stackType<Type>::isEmptyStack() const
{
    return(stackTop == 0);
}//end isEmptyStack

template <class Type>
bool stackType<Type>::isFullStack() const
{
    return(stackTop == maxStackSize);
} //end isFullStack

template <class Type>
void stackType<Type>::push(const Type& newItem)
{
    if (!isFullStack())
    {
        list[stackTop] = newItem;   //add newItem to the 
                                    //top of the stack
        stackTop++; //increment stackTop
    }
    else
        cout << "Cannot add to a full stack." << endl;
}//end push

template <class Type>
Type stackType<Type>::top() const
{
    assert(stackTop != 0);          //if stack is empty, 
                                    //terminate the program
    return list[stackTop - 1];      //return the element of the
                                    //stack indicated by 
                                    //stackTop - 1
}//end top

template <class Type>
void stackType<Type>::pop()
{
    if (!isEmptyStack())
        stackTop--;                 //decrement stackTop 
    else
        cout << "Cannot remove from an empty stack." << endl;
}//end pop

template<class Type>
void stackType<Type>::update(Type t)
{
     int temp = stackTop;
     
     while(list[stackTop] != t)
        stackTop--;
        
     if(list[stackTop] == t)   
     {   
         while(stackTop < temp)
         {
             list[stackTop] = list[stackTop+1];
             stackTop++;
         }
         
         list[stackTop] = t;
     }
}

template <class Type>
stackType<Type>::stackType(int stackSize) 
{
    if (stackSize <= 0)
    {
        cout << "Size of the array to hold the stack must "
             << "be positive." << endl;
        cout << "Creating an array of size 100." << endl;

        maxStackSize = 100;
    }
    else
        maxStackSize = stackSize;   //set the stack size to 
                                    //the value specified by
                                    //the parameter stackSize

    stackTop = 0;                   //set stackTop to 0
    list = new Type[maxStackSize];  //create the array to
                                    //hold the stack elements
}//end constructor

template <class Type>
stackType<Type>::~stackType() //destructor
{
    delete [] list; //deallocate the memory occupied 
                    //by the array
}//end destructor

template <class Type>
void stackType<Type>::copyStack(const stackType<Type>& otherStack)
{ 
    delete [] list;				   
    maxStackSize = otherStack.maxStackSize;		   
    stackTop = otherStack.stackTop;			   
	  
    list = new Type[maxStackSize];		   			   

        //copy otherStack into this stack
    for (int j = 0; j < stackTop; j++)  
        list[j] = otherStack.list[j];
} //end copyStack


template <class Type>
stackType<Type>::stackType(const stackType<Type>& otherStack)
{
    list = NULL;

    copyStack(otherStack);
}//end copy constructor

template <class Type>
const stackType<Type>& stackType<Type>::operator=
   					(const stackType<Type>& otherStack)
{ 
    if (this != &otherStack) //avoid self-copy
        copyStack(otherStack);

    return *this; 
} //end operator=         

#endif 


MAIN FUNCTION

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
#include <cstdlib>
#include <iostream>
#include "stackType.h"

using namespace std;

int main(int argc, char *argv[])
{
    stackType<int> stack(10);
    
    stack.push(1);
    stack.push(7);
    stack.push(2);
    stack.push(8);
    stack.push(4);
    
    stack.update(7);
    
    for(int i=0; i<5; i++)
    {
        cout << stack.top() <<endl;
        stack.pop();
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

There are two things to point out.
your update function will access the memory before your allocated array if the element is not present in your stack. Add a stackTop > 0 check in your first while loop in line 150. Also if you remove line 153 that will effectively accomplish the "not found" case as you described in the beginning of your post. You should also run the loop in line 155 not like while(stackTop < temp), but like while(stackTop < temp - 1), because the last valid element is temp - 1 will be copied when stackTop equals temp - 2.
Last edited on
@KRAkatau, changing the loop condition to stackTop > 0 at line 153 causes the stack to remove all its elements without checking if the "t" is in the stack.
same as above posts suggest, you can update the condition at line 153 to:

if( stackTop > 0 && list[stackTop] == t)
-If found "t" must be removed from its location in the stack and put on top of the stack. -If not found, the bottom element in the stack must be removed and "t" put on top of the stack.


If this is indeed what you want to do - then change the while in line 150 to while (stackTop > 0 && list[stackTop] != t) and remove the if in line 153.

@KRAkatau, changing the loop condition to stackTop > 0 at line 153 causes the stack to remove all its elements without checking if the "t" is in the stack.

I didn't say change the condition, I said add it... Please read more carefully.
Topic archived. No new replies allowed.