CODEWITHSUNDEEP
c++stack
Syntactic Fructose
Syntactic Fructose

Reputation: 20114

Writing an operator== for a singly linked stack

I'm having a lot of trouble writing an operator== function for my stack class, I just can't seem to get the logic down. Currently I have:

template<class myType>
bool linkedStack<myType>::operator==(const linkedStack<myType>& op)
{
    linkedStack<myType> stackA, stackB;
    bool res = false;
    stackA.copyStack(this);
    stackB.copyStack(op);

    while(!stackA.isStackEmpty() && !stackB.isStackEmpty())
    {
        if (stackA.peek() == stackB.peek()) {
            stackA.pop();
            stackB.pop();
            if (stackA.isStackEmpty() && stackB.isStackEmpty())
                res = true;
        } else
            res = false;
    }
    return res;
}

the problem being I cannot copy the current class stack into stackA, because this is a const pointer and my copyStack spews out compiler errors. There must be an easier solution to this, could someone point me in the right direction? Thanks!

EDIT: a revised portion of my code:

template<class myType>
bool linkedStack<myType>::operator==(const linkedStack<myType>& op)
{
    nodeType<myType> *current, *opcurrent;
    current = stackTop;
    opcurrent = op.stackTop;

    while(current != NULL && opcurrent != NULL)
    {
        if (current->info != opcurrent->info) {
            return false;
        }
        current = current->link;
        opcurrent = opcurrent->link;
    }
    return true;
}

Upvotes: 0

Views: 124

Answers (3)

didierc
didierc

Reputation: 14750

You don't need to go through all the stack once you've discovered a difference, at which point you may return false directly.

while(!stackA.isStackEmpty() && !stackB.isStackEmpty())
{
    if (stackA.peek() == stackB.peek()) {
        stackA.pop();
        stackB.pop();
    } else
        return false;
}
return stackA.isStackEmpty() && stackB.isStackEmpty();

On a more general note, if you're operating from within the class, you may as well use the internal data of the class directly, rather than make copies (which will incur copies of all the data held by the stacks as well). You should use a couple of pointers to follow the internal lists. This code can be easily derived from the above code, which should give something along the lines of:

node *a_ptr = head_ptr;
node *b_ptr = op.head_ptr;
while(!(a_ptr == tail || b_ptr == tail)
{
    if (a_ptr->data == b_ptr->data) {
        a_ptr = a_ptr->next;
        b_ptr = b_ptr->next;
    } else
        return false;
}
return (a_ptr == tail && b_ptr == tail);

depending on your implementation details.

Upvotes: 1

gxtaillon
gxtaillon

Reputation: 1076

First calling comparison methods should not modify the object(s) it's being called on. Declare it const.

Second I think copying your objects like this is not a good idea since with very large stacks it could cause performance issues (I assume a generic usage).

But most importantly, if this is your implementation of a stack, why don't you use your internal data instead of calling public methods like this?

For instance, the Microsoft's STD uses a deque as the internal data representation for the stack and the operator== is simply defined as :

template<class _Ty,
    class _Container> inline
    bool operator==(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test for stack equality
    return (_Left._Get_container() == _Right._Get_container());
    }

Upvotes: 1

Captain Obvlious
Captain Obvlious

Reputation: 20073

You are making local copies of both this and op. This is unnecessary and you can do the comparisons directly between the data in this and op instead. It looks like you are trying to pass a const-object to a function taking a non-const parameter. copyStack should take a const reference or pointer.

Upvotes: 0

Related Questions