Inheritance using Stack Class Problem

I am having problems implementing a SearchableStack Class as a subclass of Stack class.

Here is the design:

List Class -->(composition)-->Stack Class-->(inheritance)-->SearchableStack Class

Ok, we are not allowed to use "protected" fields, thus not allowing me to access the private data members of the parent class (yes this is stupid, but so is college).. We do this for security reasons, so I have to use the public functions in which I created for for the Stack to achieve the search..

My code is not returning correct results, when I search for something in the stack, and it is returned - the stack for some reason now has a 0 (zero) in the last stack memory location. And other various bugs.

Any help would be greatly appreciated.

SearchableStack.h

Code:

---

#include "Stack.h"

using namespace std;

class SearchableStack : public Stack
{
        public:
                                SearchableStack();
                bool        find(int);

        private:
                Stack tempStack;
}

---

SearchableStack find function:

Code:

---

bool SearchableStack::find(int n)
{
        int temp;
        //Stack tempStack2;

        cout<<"In Find"<<endl;

        while(!isEmpty())
        {
                cout<<"in FIRST while"<<endl;

                temp = pop();
                tempStack.push(temp);
               
                if(temp == n)
                {
                        cout<<"in FIRST if"<<endl;

                        while(!tempStack.isEmpty())
                        {
                                cout<<"in SECOND while"<<endl;
                                push(tempStack.pop());
                        }

                        return true;
                }
        }

        while(!tempStack.isEmpty())
        {
                cout<<"in THIRD while"<<endl;
                push(tempStack.pop());
        }
        cout<<"@@@ END OF FUNCTION hmm, no return before here?"<<endl;
        return false;

}

---

ALSO, I tried not haveing the private data member tempStack -- and just created one in the member function, and that was no dice either..

Thanks

Difficult to say with the limited code posted. It would be nice to see the List and Stack class code as well and also the initial values you are pushing onto the stack and the value you are searching for.

>> yes this is stupid, but so is college
It is proper C++ design to not allow access to the parent class data members.

>> I tried not haveing the private data member tempStack -- and just created one in the member function
Even if it didn't solve your problem, it is better to make it local to the function.

I don't see what the problem is at quick glance. What does the isEmpty() function look like?

Quote:

---

Originally Posted by hk_mp5kpdw

Difficult to say with the limited code posted. It would be nice to see the List and Stack class code as well and also the initial values you are pushing onto the stack and the value you are searching for.

---

Agreed. The algorithm is sound. Substituting std::stack<int> for your Stack works, so the problem is in your Stack class, not SearchableStack.

I don't see your problem, but I was wondering if its better to have it sort of easier to read, or just make it:

Code:

---

bool SearchableStack::find(int n)
{
        int temp;
        //Stack tempStack2;

        cout<<"In Find"<<endl;

        while(!isEmpty() && !(temp == n))
        {
                cout<<"in FIRST while"<<endl;

                temp = pop();
                tempStack.push(temp);
        }

        while(!tempStack.isEmpty())
        {
                cout<<"in SECOND while"<<endl;
                push(tempStack.pop());
        }

        if(temp == n)
                return true;

        cout<<"@@@ END OF FUNCTION hmm, no return before here?"<<endl;
        return false;
}

---

You'd probably want to initialize temp in that code and make sure you initialize it to something other than n.

Quote:

---

My code is not returning correct results, when I search for something in the stack, and it is returned - the stack for some reason now has a 0 (zero) in the last stack memory location. And other various bugs.

---

Really would be helpful to see your stack implentation and maybe the list implementation as well.

My guess is that your tempstack is adding a 0 at the beginning when it's constructed but without the code, it's just a guess.

Also without knowing more about the stacks public members I can't suggest any alternatives.

Ok, I updated the SearchableStack Class using the local value since its better practice.

Here is everything you should need - and thanks for helping!

Test #1 (finding something in the stack):
I Push: 1, 2, 3, 4 onto the stack.
Then I Print and its correct: 1234
Then I find: 3
Output:
Enter item to find: 3
In Find
in FIRST while
in FIRST if
in SECOND while
Item IS in the Stack!

But then when I print the Stack after this "find"
Output:
Enter item to find: 3
1
2
3
0

Yikes!

Test #2 (find something not in Stack):
I Push: 1, 2, 3, 4 onto the stack.
Then I Print and its correct: 1234
Then I find: 9
Output:
Enter item to find: 9
Enter item to find: 9
In Find
in FIRST while
in FIRST while
in FIRST while
in FIRST while
in THIRD while
in THIRD while
in THIRD while
in THIRD while
@@@ END OF FUNCTION hmm, no return before here?
Item is NOT in the Stack!

Then I print:
But then when I print the Stack after this "find"
Output:
Enter item to find: 3
3
2
1
0


My Code:


SearchableStack.h

Code:

---

//SearchableStack.h

#include "Stack.h"

using namespace std;

class SearchableStack : public Stack
{
        public:
                                SearchableStack();
                bool        find(int);

        private:
                //Stack tempStack;
}

---

Stack.h:

Code:

---


//Stack.h
//Stack Wrapper Class

#include <iostream>
#include "LList.h"


class Stack
{
        public:

                                Stack();
                bool        isEmpty();
                bool        isFull();
                void        push(int);
                int                pop();
                void        print();

        protected:
                int                current;
                LList        list;

};

---

LList.h:

Code:

---


//Linked List
//LList.h

#include <iostream>
//#include "Stack.h"

using namespace std;

//const int SIZE = 5;

struct intNode;

typedef intNode* intNodePtr;

struct intNode
{
        int value;
        intNodePtr next;
};

class LList
{

        public:
                                LList();
                                ~LList();
                bool        IsEmpty();
                void        MakeEmpty();
                int                Length();
                int                GetItem(int loc);
                void        Add(int item);
                bool        DeleteItem(int loc);
                void    Print();

        private:
                intNodePtr        list;       
                int                        size;
};

---

SearchableStack.cpp

Code:

---

//SearchableStack.cpp

#include <iostream>
#include "SearchableStack.h"
; //i have no freaking clue...
using namespace std;

SearchableStack::SearchableStack()
{
        while(isEmpty() != true)
        {
                pop();
        }
}

bool SearchableStack::find(int n)
{
        int temp;
        Stack tempStack2;

        cout<<"In Find"<<endl;

        while(!isEmpty())
        {
                cout<<"in FIRST while"<<endl;

                temp = pop();
                tempStack2.push(temp);
               
                if(temp == n)
                {
                        cout<<"in FIRST if"<<endl;

                        while(!tempStack2.isEmpty())
                        {
                                cout<<"in SECOND while"<<endl;
                                push(tempStack2.pop());
                        }

                        return true;
                }
        }

        while(!tempStack2.isEmpty())
        {
                cout<<"in THIRD while"<<endl;
                push(tempStack2.pop());
        }
        cout<<"@@@ END OF FUNCTION hmm, no return before here?"<<endl;
        return false;

}

---

Stack.cpp

Code:

---

//Stack.cpp
//Stack Wrapper Class

#include "Stack.h"

Stack::Stack()
{
        current = 0;
        list.MakeEmpty();

}
bool Stack::isEmpty()
{
        if(list.IsEmpty() == true)
                return true;
        else
                return false;
}
bool Stack::isFull()
{
        return false;
}
int Stack::pop()
{
        if(current == 0)
                return 0;

        list.DeleteItem(current);
        current--;
        return current;

       
}
void Stack::push(int item)
{
        current++;
        list.Add(item);
}
void Stack::print()
{
        list.Print();
}

---

LList.cpp

Code:

---

//Linked List
//LList.cpp

#include "LList.h"

LList::LList()
{
        list = NULL;
        size = 0;
}

LList::~LList()
{
        MakeEmpty();
}

bool LList::IsEmpty()
{
        if(list == NULL)
                return true;
        else
                return false;
}

void LList::MakeEmpty()
{
        intNodePtr tempPtr;

                while(list != NULL)
                {
                        tempPtr = list;
                        list = list->next;
                        delete tempPtr;
                }

        size = 0;
}

int LList::Length()
{
        return size;
}

int LList::GetItem(int loc)
{
        if(loc > size || loc == 0)        // If location is out of the list range
                return -1;                                        // Exit the function

        intNodePtr tempPtr;
        int tempCounter = 1;        //Temp Counter to keep track of how many nodes we have passed

        tempPtr = list;

        if(loc == 1)                                //If we are looking for the first item in the list
                return tempPtr->value;        //Return the value of the first one
        else
        {       
                while(tempCounter < loc)
                {
                        tempPtr = tempPtr->next;
                        tempCounter++;
                }

                return tempPtr->value;
        }
}

void LList::Add(int item)
{
        size++;

        if(list == NULL)
        {
                list = new intNode;
                list->value = item;
                list->next = NULL;
        }
        else
        {
                intNodePtr tempPtr;
                tempPtr = list;

                        while(tempPtr->next != NULL)
                        {
                                tempPtr = tempPtr->next;
                        }

                tempPtr->next = new intNode;

                tempPtr = tempPtr->next;
                tempPtr->value = item;
                tempPtr->next = NULL;
        }

}

bool LList::DeleteItem(int loc)
{
        intNodePtr tempPtr1 = list;
        intNodePtr tempPtr2 = list;

        for(int i = 0; i < loc - 2; i++)//make this loc -1 if need be (dierbach responce)
        {
                if (tempPtr2 != NULL)
                {
                        tempPtr2 = tempPtr2->next;
                }
        }
        if(tempPtr2 == NULL)
                return false;
        else
        {
                if(loc == 1)
                        list = list->next;
                else
                {
                        if (tempPtr1 != NULL)
                        {
                                tempPtr1 = tempPtr2->next;
                                tempPtr2->next = (tempPtr1->next);
                        }
                }
               
                size--;
                delete tempPtr1;
                return true;
        }
}
void LList::Print()
{
        if(size == 0)
        {
                cout<<"List is empty.."<<endl;
                return;
        }

        intNodePtr tempPtr;

        tempPtr = list;

        if(size == 1)
                cout<<tempPtr->value<<endl;
        else
        {
                cout<<tempPtr->value<<endl;

                while(tempPtr->next != NULL)
                {
                        tempPtr = tempPtr->next;
                        cout<<tempPtr->value<<endl;
                }
        }               
}

---

If you need anything else please ask.

Thanks!!

Also you may see the:

Code:

---

//SearchableStack.cpp

#include <iostream>
#include "SearchableStack.h"
; //i have no freaking clue...
using namespace std;

---

I was getting an error "missing ; before using" so i put in the ; and it worked - i have no clue why or what for, but it worked......?

Thanks.

Quote:

---

Originally Posted by Daved

You'd probably want to initialize temp in that code and make sure you initialize it to something other than n.

---

Of course other than n, haha. It would be so rare that the random number temp is would actually be n, but you're right, good eye. So initialized to 0, that would be a fine version? I just wanted to make sure it wasn't a problem readability-wise, since thats how I'd do it.

>> I was getting an error "missing ; before using"
That's because you are missing a semicolon at the end of the SearchableStack declaration.

Looking at that code, what is current supposed to be inside the Stack class? Is it the current location inside the List? If so, why are you returning it from pop()? Shouldn't pop() be returning the result of GetItem(current) before you decrement it?

Current is the number in which spot the top of the stack is.

So if the stack has: 333, 4, 44, 2
Current = 4

Quote:

---

If so, why are you returning it from pop()?

---

I was returning the next item in the stack..

Dont think this effects my issue - ?

Sure it does... you are returning current. The return value of pop is being pushed onto the Stack in the find function. Try inputting something other than 1234... like maybe 5678, then search for 6. It won't work because pop should return the next item on the stack, but instead is returning the next location in the list.

So I should change code around in the Stack Class pop() member function? Opposed to messing with the SearchableStack Class add() func.?

Thanks.

Crap.. Do you know of any way to accomplish this?

I thought this would work:

Code:

---

int Stack::pop()
{
        if(current == 0)
                return 0;
        else
        {
                list.DeleteItem(current);
                current--;
                return list.GetItem(current);
        }
       
}

---

But then it will still return a '-1' in the last spot?

Daved, you around?

It's a pretty simple solution. Think about what you're trying to do. The pop() method should remove the last item from the stack and return it while remembering that the next item below it is now the last item.

Your code removes the last item from the stack, updates current to refer to the new last location, then returns the item at that new location. All you've got to do is figure out how to return the item at the original "current" location instead of what it becomes after the delete and decrement.

Or you can look at your other thread, although 7stud's version is even a little more complicated than it needs to be.