c++ - 添加堆栈中的每个值

Question

我正在尝试找出一种方法来将堆栈中的每个值相加。

目标是使用该值来确定堆栈中的所有值是否都是偶数。我已经编写代码来执行此操作

template <class Object>
bool Stack<Object>::objectIsEven( Object value ) const {
     bool answer = false;
     if (value % 2 == 0)
          answer = true;
     return( answer );
}

但是，我对如何在单独的方法中添加所有堆栈的值感到困惑

堆栈.cpp

#ifndef STACK_CPP
#define STACK_CPP

#include "Stack.h"

namespace cs20 {

template <class Object>
Stack<Object>::Stack() {
    topNode = NULL;
}

template <class Object>
Stack<Object>::Stack( const Stack<Object>& rhs ) {
    topNode = NULL;
    *this = rhs;
}

template <class Object>
Stack<Object>::~Stack() {
    makeEmpty();
    delete topNode;
}

template <class Object>
bool Stack<Object>::isEmpty() const {
    return( (topNode == NULL) );
}

template <class Object>
bool Stack<Object>::even() const
    {

    }
// template Object must support the % operator which ints do
template <class Object>
bool Stack<Object>::objectIsEven( Object value ) const {
    bool answer = false;
    if (value % 2 == 0)
        answer = true;
    return( answer );
}


template <class Object>
void Stack<Object>::makeEmpty() {
    while (!isEmpty()) {
        pop();
    }
}


template <class Object>
void Stack<Object>::push( const Object& data ) {
    StackNode<Object>* newNode = new StackNode<Object>( data, topNode );
    topNode = newNode;
}

template <class Object>
void Stack<Object>::pop() {
    if (isEmpty()) {
        throw EmptyStack();
    }
    StackNode<Object> *oldTop = topNode;
    topNode = topNode->getNext();
    delete oldTop;
}

template <class Object>
const Object& Stack<Object>::top( ) const {
    if (isEmpty()) {
        throw EmptyStack();
    }
    StackNode<Object> node = *topNode;
    return( node.getElement() );
}

template <class Object>
Object Stack<Object>::topAndPop( ) {
    Object o = top();
    pop();
    return( o );
}

// Deep copy of linked Stack
template <class Object>
const Stack<Object>& Stack<Object>::operator =( const Stack<Object>& rhs ) {
    if (this != &rhs) {
        makeEmpty();
        if (!(rhs.isEmpty())) {
            StackNode<Object> * rhsTopNode = rhs.topNode;
            StackNode<Object> * myTopNode = new StackNode<Object>( rhsTopNode->getElement() );
            topNode = myTopNode;

            rhsTopNode = rhsTopNode->getNext();
            while (rhsTopNode != NULL) {
                myTopNode->setNext( new StackNode<Object>( rhsTopNode->getElement() ) );
                myTopNode = myTopNode->getNext();
                rhsTopNode = rhsTopNode->getNext();
            }
        }
    }
    return( *this );
}

template <class Object> 
std::ostream& Stack<Object>::printStack( std::ostream& outs ) const {
    if (isEmpty()) {
        outs << "Empty Stack";
    }
    else {
        outs << "TOP: ";
        StackNode<Object> * node = topNode;
        while (node != NULL) {
            outs << node->getElement();
            outs << "\n     ";           /// for visual alignment
            node = node->getNext();
        }
    }
    return( outs );
}

}

#endif

Answer 1

您不能在堆栈实现中定义您的 getSum() 函数吗？或者有什么限制吗？

太阳一号:

template <class Object> 
Object Stack<Object>::getSum( ) {
    Object sum = 0;  // or memset or other stuffs
    StackNode<Object> * node = topNode;
    while (node != NULL) {
        sum += node->getElement();
        node = node->getNext();
    }
    return sum;
}

正如 Gary 提到的，您还可以通过在每次推送或弹出时缓存总和值来提高效率(即更改堆栈)Sol-2:

添加一个表示总和的成员属性(例如，g - 总和)

template <class Object>
Stack<Object>::Stack() {
    topNode = NULL;
    this->sum = 0; // initialize or new object
}

每当一个对象被压入时更新总和

template <class Object>
void Stack<Object>::push( const Object& data ) {
    StackNode<Object>* newNode = new StackNode<Object>( data, topNode );
    topNode = newNode;
    this->sum = this->sum + data;
}

每当删除对象时，pop() 都会进行相同的更新

template <class Object>
void Stack<Object>::pop() {
    if (isEmpty()) {
        throw EmptyStack();
    }
    StackNode<Object> *oldTop = topNode;
    topNode = topNode->getNext();
    this->sum = this->sum - oldTop->getElement();
    delete oldTop;
}

现在你的最后一个函数 getSum()

template <class Object> 
    Object Stack<Object>::getSum( ) {
        return this->sum;
    }

Sol-1 的成本为 O(N) = N，而 Sol-2 的成本为 O(N) = 1

现在你应该可以使用 pStack->objectIsEven(pStack->getSum());

我认为您不需要关心堆栈实现中的线程，否则您应该在插入/删除操作时使用某种同步机制以使堆栈保持一致。

希望这对您有所帮助。问候，