Отслеживание размера стека в связанном списке реализации стека C++

Question

Я работаю над реализацией связанного списка стека значений ItemType (в настоящее время их можно удвоить, но их можно изменить). Хотя мой код компилируется отлично, я понял, что мой метод размера довольно неэффективен, так как он использует итерацию для получения размера связанного списка - O (n) сложности времени - когда он может просто хранить размер как поле узла , обновите его в моих других методах, затем верните это значение - улучшите метод, чтобы он имел сложность времени O (1). Однако, к сожалению, у меня возникают некоторые проблемы с тем, как интегрировать это новое поле размера, в частности, как инициализировать его значение, а мой компилятор продолжает говорить мне, что он не может быть отредактирован. Итак, мой вопрос заключается в том, как я могу реализовать размер как поле класса node (или должен ли я его реализовать в другом месте?), И где в моем коде я должен инициализировать и обновлять его?

Ниже мой файл заголовка для связанного стека списка:

#ifndef DBLSTACK_H 
#define DBLSTACK_H 


typedef double ItemType; // stack currently holds doubles 


class DblStack 
{ 
private: 
    //Node class 
    class Node 
    { 
    public: 
     double data; 
     Node *next; 

     // Node constructor 
     Node(double value, Node * link = 0) 
     { 
      data = value; 
      next = link; 
     } 
    }; 

    typedef Node * NodePtr; 

    // Data members 
    NodePtr myTop; //points to top of stack 

    public: 
    // Class Constructor 
    DblStack(); 

    // Copy Constructor 
    DblStack(const DblStack& rhs); 

    // Class Deconstructor 
    ~DblStack(); 

    // Assignment operator 
    // Assigns a stack to another 
    const DblStack& operator= (const DblStack& rhs); 

    // isEmpty 
    // Checks if the stack is empty 
    bool isEmpty() const; 

    // push 
    // Pushes an item on top of the stack. 
    void push(const ItemType& item); 

    // pop 
    // Pops the top item off the stack. 
    void pop(); 

    // top 
    // Returns the top item of the stack without popping it. 
    ItemType top() const; 

    // size 
    // Returns the number of items on the stack. 
    size_t size() const; 

}; 

#endif 

А вот мой исходный файл:

#include <cstddef> //for NULL 
#include <stdexcept> 
#include "DblStack.h" 
using namespace std; 

// Class Constructor 
DblStack::DblStack() 
: myTop(0) 
{ 
} 


// Copy Constructor 
DblStack::DblStack(const DblStack& rhs) 
{ 
    myTop = 0; 
    if (!rhs.isEmpty()) 
    { 
     // Copy first node 
     myTop = new DblStack::Node(rhs.top()); 

     // Set pointers to run through stack 
     DblStack::NodePtr lastPtr = myTop; 
     DblStack::NodePtr origPtr = rhs.myTop->next; 
     while (origPtr != 0) 
     { 
      lastPtr->next = new DblStack::Node(origPtr->data); 
      lastPtr = lastPtr->next; 
      origPtr = origPtr->next; 
     } 
    } 
} 



// Class Deconstructor 
DblStack::~DblStack() 
{ 
    // Set pointers to run through stack 
    DblStack::NodePtr curr = myTop, next; 
    while (curr != 0) 
    { 
     next = curr->next; 
     delete curr; 
     curr = next; 
    } 
} 


// Assignment operator 
// Assigns a stack to another 
const DblStack& DblStack::operator= (const DblStack& rhs) 
{ 
    if (this != &rhs) 
    { 
     this->~DblStack(); 
     if (rhs.isEmpty()) 
     { 
      myTop = 0; 
     } 
     else 
     { 
      DblStack tmp(rhs); // Call copy constructor 
      std::swap(myTop, tmp.myTop); 
     } 
    } 
    return *this; 
} 


// isEmpty 
// Checks if the stack is empty 
bool DblStack::isEmpty() const 
{ 
    return (myTop == 0); 
} 


// push 
// Pushes an item on top of the stack. 
void DblStack::push(const ItemType& item) 
{ 
    myTop = new DblStack::Node(item, myTop); 
} 


// pop 
// Pops the top item off the stack. 
void DblStack::pop() 
{ 
    if (!isEmpty()) 
    { 
     DblStack::NodePtr ptr = myTop; 
     myTop = myTop->next; 
     delete ptr; 
    } 
    else 
    { 
     throw std::underflow_error("Stack is empty"); 
    } 
} 


// top 
// Returns the top item of the stack without popping it. 
ItemType DblStack::top() const 
{ 
    if (!isEmpty()) 
    { 
     return myTop->data; 
    } 
    else 
    { 
     throw std::underflow_error("Stack is empty"); 
    } 
} 


// size 
// Returns the number of items on the stack. 
size_t DblStack::size() const 
{ 
    size_t size = 0; 
    DblStack::NodePtr ptr; 
    for (ptr = myTop; ptr != 0; ptr = ptr->next) 
    { 
     size++; 
    } 
    return size; 
} 

Совершенствуя мой метод размер является основной целью этого вопроса, я «Также оцените любые другие предложения, которые могут вам помочь в оптимизации моего кода. Спасибо!

Answer 1

Вы хотите добавить размер переменной в члена к классу DblStack:

class DblStack 
{ 
private: 
    size_t size; 
// ... 
} 

Когда вы первый построить DblStack, она не имеет ничего его, так что его размер должен быть 0:

DblStack::DblStack() 
    : myTop(0) 
    , size(0) 
{ } 

Теперь вам нужно подумать о том, когда размер изменится! Вы должны обнаружить, что единственные случаи, которые он изменил, - это когда предметы выталкиваются или выталкиваются из стека. Следовательно, вы хотите, чтобы ваши нажимные и поп-метода, чтобы отразить это:

// Push increases stack size 
size++; 

// Pop decreases stack size 
size--; 

Наконец, вы можете изменить способ размера() просто возвращает размер:

size_t size() const { return size; } 

Answer 2

Включите размер как член DblStack и измените его другие методы, чтобы поддерживать его в актуальном состоянии.