Основанный на узле класс стека (нуждаются в экспертной оценке),

Сначала , несколько общих комментариев, которые не вызывают проблем в этом случае, но некоторые могут сделать это в других ситуациях:

Вы должны генерировать исключения только, производные от класса std :: exception . C ++ позволяет использовать любой тип (например, строку в вашем случае), но это действительно плохая идея.

Члены класса должны быть инициализированы списками инициализаторов, как показано ниже: (в других случаях это может вызвать ошибки. Если вы не используете список инициализаторов, сначала создаются элементы по умолчанию, а затем оператор присваивания используется в теле конструктора для их перезаписи. Не все типы имеют оператор присваивания, или оператор присваивания может иметь нежелательные побочные эффекты, поэтому отказ от использования списков инициализаторов может быть проблематичным)

Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}
Stack() : size(0), top(NULL) {}

Именование ваших функций return * бессмысленно. Просто назовите их size () и topPtr () или, возможно, getSize () и getTopPtr ()

Second , вы не соблюдал правила. ;) или, возможно, getSize () и getTopPtr ()

Во-вторых , вы не следовали правилам. ;) или, возможно, getSize () и getTopPtr ()

Во-вторых , вы не следовали правилам. ;) Your stack class has two member variables, it was only allowed to have one. :)

Finally, things that break the stack:

This will crash, as you try to dereference a null pointer:

void test() {
  Stack s;
  s.peek(); // crashes
}

This will leak memory, as the allocated node is never deleted (the Stack destructor should do that):

void test() {
  Stack s;
  s.push(1);
}

The destructor should look something like this:

~Stack() {
  while (top != NULL){
    Node* next = top.returnPtr();
    delete top;
    top = next;
  }
}

This one should be fun too:

void test() {
  Stack s;
  s.push(1);
  Stack t(s);
  s.pop();
}

t.returnSize() will now return 1, but t.top points to the node in s that was just deleted. This should be fixed by defining a copy constructor and an assigment operator for the stack (and perhaps for the node class as well) The copy constructor would look like this:

Stack(const Stack& s);

and is called if you initialize one stack from another, like in the above. Оператор присваивания выглядит так:

Stack& operator= (const Stack& s);

и вызывается, если я назначаю один стек другому, после инициализации обоих:

Stack s;
Stack t;
t = s; // now both are already initialized, so the assigment operator is used, not the copy constructor

Роль этих функций состоит в том, чтобы гарантировать, что t станет копией с . Таким образом, каждый узел в s должен быть скопирован и назначен на t , чтобы они не указывали на одни и те же узлы. (Это замечательный пример вашего предыдущего вопроса о праве собственности, кстати. Узлы должны принадлежать ровно одному объекту Stack. Если он становится общим для нескольких, у вас есть проблема, и это лишь вопрос времени, прежде чем она превратится в сбой. )

И, наконец, если мы хотим немного поганить:

void test() {
  Stack s;
  s.push(1);
  s.push(2);
}

Что произойдет, если выделение памяти для второго узла не удастся (возможно, у нас закончилась память. Маловероятно, но это может случиться). Выдается исключение после увеличения размера. Размер s теперь будет 2, хотя top по-прежнему указывает на первый узел Если вы думаете, что это слишком маловероятная проблема, чтобы к ней относиться серьезно, представьте себе небольшое расширение вашего класса. Допустим, это был шаблон, чтобы он мог хранить другие типы, кроме int.

Это означает, что каждый раз, когда мы создаем узел, мы должны вызывать конструктор копирования типа значения. Это тоже может вызвать исключение. Мы не знаем, потому что не имеем ни малейшего понятия, какой тип пользователь может попытаться сохранить в стеке.

Понятие «безопасность исключений» важно, и его действительно очень сложно понять. В принципе, в каком состоянии находится ваш класс при возникновении исключения? Это все еще в действующем состоянии? (так должно быть всегда). Были ли потеряны какие-либо данные (в некоторых случаях это может быть неизбежно, в других этого можно избежать с осторожностью), и если данные были потеряны, были ли они удалены правильно? Деструкторы вызвали, память освободили? (очередной раз, так должно быть всегда)

И последнее, почему я был так уверен, что у вас будет хотя бы одна ошибка. Все ошибаются в вопросах безопасности исключений, включая меня большую часть времени. Написание правильной реализации такой простой вещи, как стек, в C ++ на удивление сложно. :)

Бонус:

В ответ на комментарии о конструкторах копирования, деструкторах и RAII, давайте просто сделаем все: Во-первых, позвольте мне сказать, что осталось, вероятно, одна или две ошибки, которых я не заметил. Во-вторых, вот код, который я тестировал, и все последующие его проходят. Не стесняйтесь запускать через него свой собственный код. (она должна работать как есть, за исключением того, что вам придется переименовать функцию getSize ): (переменная live - это та, которую я добавил для отладки. Я изменил свои реализации стека, поэтому что конструкторы увеличивают его, а деструкторы уменьшают его, просто чтобы убедиться, что количество построений и разрушений одинаково. Очевидно, это следует удалить из класса Stack, как только вы убедитесь, что он работает

Тестовый код

static int live; // debugging - keeps track of how many nodes have been allocated. Constructors add 1, destructors subtract. It should end in 0

#include "stack.h"
#include <iostream>
#include <cassert>

int main(){
    {
        // test stack creation + push
        Stack s;
        s.push(1);
        s.push(2);
        s.push(3);
        assert(s.getSize() == 3);

        Stack t;
        t.push(4);
        t.push(5);
        t.push(6);
        assert(t.getSize() == 3);

        // test assigment operator when both stacks contain data
        s = t;
        assert(s.getSize() == 3);
        assert(s.peek() == 6);
        assert(t.peek() == 6);

        Stack u(s);
        // test self assigment when stack contains data
        u = u;
        assert(u.getSize() == 3);
        assert(u.peek() == 6);


        Stack v;
        // test copy construction from stack with data
        Stack w(t);
        assert(w.getSize() == 3);
        assert(w.peek() == 6);
        assert(t.getSize() == 3);
        assert(t.peek() == 6);

        // test assignment operator when source is empty, destination contains data
        w = v;
        assert(w.getSize() == 0);
        assert(v.getSize() == 0);

        // test copy construction from empty stack
        Stack x(v);
        assert(x.getSize() == 0);
        assert(v.getSize() == 0);

        // test pop
        assert(t.pop() == 6);
        assert(t.pop() == 5);
        assert(t.pop() == 4);

        assert(s.pop() == 6);
        assert(s.pop() == 5);
        assert(s.pop() == 4);
    } // at this point, all allocated stacks go out of scope, so their destructors are called, so now is a good time to check for memory leaks:
    assert(live == 0);
}

---

Фиксированная реализация

Теперь сначала простое исправление. Конструктор копирования, оператор присваивания и деструктор были добавлены в класс Stack. Класс Node по-прежнему проблематичен, если используется изолированно, но пока он используется только через стек, мы можем обеспечить правильное копирование и удаление узлов. К сожалению, стеку теперь требуется доступ к Node.tail_ , чтобы копирование работало, поэтому я подружился с ним. Так что это работает, но не изящно.

#include <stdexcept> // for std::exception

class Stack;

class Node
{
    private: // changed naming to head/tail, which are commonly used in implementations of linked lists like this. The head is the current element, tail is a pointer to the remainder
        int head_;
        Node* tail_;

    public:
        friend class Stack; // this is necessary for the Stack copy constructor in order to modify the tail pointer after the node is created.
        // the elegant solution had been to define a copy constructor on the Node class as well, but we'll get to that

        int head() const { return head_; }
        Node* tail() const { return tail_; }

        Node(int val, Node* prev) : head_(val), tail_(prev) { ++live; } // use initializer list
        ~Node() { --live; }

        Node(const Node& other) : head_(other.head_), tail_(other.tail_){ ++live; }; // this could be omitted, but I use it to update 'live' for debugging purposes
};

class Stack
{
    private:
        Node* top;
//        int size; // we don't actually need the size at all, according to spec, so I removed it to keep things simple

        bool empty() const { return top == NULL;}

        void freeNodes() { // helper function to avoid duplicate code
            while (!empty()){
                pop();
            }
        }
    public:
        Stack() : top() {} // use initializer list
        ~Stack() { // destructor - the stack is being deleted, make sure to clean up all nodes
            freeNodes();
        }
        Stack(const Stack& other) : top() { // copy constuctor - we're being initialized as a copy of another stack, so make a copy of its contents
            if (other.empty()){
                return;
            }

            top = new Node(*other.top); // copy the first node, to get us started

            Node* otherNext = other.top->tail();            
            Node* current = top;

            while (otherNext != NULL){
                current->tail_ = new Node(*otherNext); // copy the current node
                current = current->tail(); // move to the next node
                otherNext = otherNext->tail();
            }
        }
        Stack& operator= (const Stack& other) {
            if (this == &other){ // If we assign this stack to itself (s = s), bail out early before we screw anything up
                return *this;
            }

            //now create the copy
            try {
                if (other.empty()){
                    freeNodes();
                    top = NULL;
                    return *this;
                }
                // naively, we'd first free our own stack's data before constructing the copy
                // but what happens then if an exception is thrown while creating the copy? We've lost all the current data, so we can't even roll back to a previous state
                // so instead, let's simply construct the copy elsewhere
                // this is almost straight copy/paste from the copy constructor. Should be factored out into a helper function to avoid duplicate code
                Node* newTop = new Node(*other.top); // copy the first node, to get us started

                Node* otherNext = other.top->tail();
                Node* current = newTop;

                while (otherNext != NULL){
                    current->tail_ = new Node(*otherNext); // copy the current node
                    current = current->tail(); // move to the next node
                    otherNext = otherNext->tail();
                }
                // once we're sure that we're able to create the copy of the other stack, we're ready to free the current one
                // this is a bit of duplicate code
                freeNodes();
                top = newTop;
                return *this;
            }
            catch (...){      // if an exception was thrown
                throw;        // and rethrow the exception so the application can deal with it
            }
        }

        // Node* returnTopPtr() { return top; } // not necessary. It's not a required part of the public interface, and class members can just access the top variable directly

        void push(int);
        int pop();
        int peek() const;

        int getSize() const{
            if (empty()){ return 0; }
            int i = 0;
            for (Node* cur = top; cur != NULL; cur = cur->tail_, ++i){}
            return i;
        }
};

void Stack::push(int value)
{ 
    Node* currentTop = top;
    top = new Node(value, currentTop); // this could throw an exception, but if it does, our stack will simply be left unchanged, so that's ok
}

int Stack::peek() const
{
    if (empty()){
        throw std::exception("Stack is empty");
    }
    return top->head();
}

int Stack::pop()
{    
    if (empty()){
        throw std::exception("Stack is empty");
    }

    Node* tail = top->tail();
    int result = top->head();
    delete top;
    top = tail;

    return result;
}

---

RAII v. 1

RAII - паршивое название для жизненно важной техники. Основная идея заключается в том, что каждое выделение ресурсов (включая, помимо прочего, выделение памяти с помощью new .) Должно быть заключено в класс, который при необходимости заботится о копировании или удалении ресурса. В нашем случае, вместо того, чтобы Stack отслеживать все узлы, мы могли бы немного упростить задачу, заставив класс Node выполнять большую часть этой работы. Теперь узел получил конструктор копирования, оператор присваивания и деструктор. Стек теперь просто должен отслеживать верхний узел ... почти. Это все еще немного сомнительно, потому что Stack.push выделяет новые узлы, но Узел теперь отвечает за большинство удалений. . Тем не менее, это позволяет нам избавиться от циклов, которые нам понадобились перед удалением или копированием списка узлов.

Стеку все еще требуется доступ к члену tail_ Node`, но на этот раз , Я сделал функцию доступа вместо того, чтобы сделать класс членом. В целом лучше, но я все еще недоволен.

#include <stdexcept>

class Node
{
private:
    int head_;
    Node* tail_;

public:
    int head() const { return head_; }
    Node* tail() const { return tail_; }
    Node*& tail() { return tail_; } // Another way to allow Stack to modify the tail. Needed for pop()


    Node(int val, Node* prev = NULL) : head_(val), tail_(prev) { ++live; }

    ~Node(){ --live; delete tail_; } // it is safe to call delete on a NULL pointer

    Node(const Node& other) : head_(other.head()), tail_(NULL) {
        ++live;
        if (other.tail() == NULL){
            return;
        }
        tail_ = new Node(*other.tail());
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }
        head_ = other.head();
        if (other.tail() != NULL){
            return *this;
        }

        Node* oldTail = tail_;

        try {
            tail_ = new Node(*other.tail());
        }
        catch(...){
            tail_ = oldTail;
            throw;
        }
    }
};

class Stack
{
private:
    Node* top;

    bool empty() const { return top == NULL;}

public:
    Stack() : top() {} 
    ~Stack() {
        delete top;
    }

    Stack(const Stack& other) : top(){
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other) {
        if (this == &other){
            return *this;
        }

        Node* oldTop = top;

        try {
            top = NULL;
            if (other.top != NULL){
                top = new Node(*other.top);
            }
            delete oldTop;
            return *this;
        }
        catch (...){ 
            delete top;
            top = oldTop;
            throw;  
        }
    }

    void push(int);
    int pop();
    int peek() const;

    int getSize() const{
        if (empty()){ return 0; }
        int i = 0;
        for (Node* cur = top; cur != NULL; cur = cur->tail(), ++i){}
        return i;
    }
};

void Stack::push(int value)
{ 
    Node* currentTop = top;
    top = new Node(value, currentTop);
}

int Stack::peek() const
{
    if (empty()){
        throw std::exception("Stack is empty");
    }
    return top->head();
}

int Stack::pop()
{    
    if (empty()){
        throw std::exception("Stack is empty");
    }

    Node* tail = top->tail();
    int result = top->head();
    if (top != NULL){
        top->tail() = NULL; // detach top from the rest of the list
        delete top;
    }

    top = tail;

    return result;
}

---

RAII v. 2

Для решения упомянутых выше проблем я решил немного изменить свою стратегию. Узел теперь выполняет всю тяжелую работу, включая операции push / pop / peek. Стек - это просто тонкая обертка вокруг них. Оказалось, что это решило большинство проблем. Стек больше не должен возиться с частными членами узла , и у нас есть более четкие правила владения. Стек владеет верхним узлом, и каждый узел, не являющийся верхним, принадлежит его родительскому узлу - и на этот раз владелец и создает, копирует и уничтожает узел. Гораздо более согласованный.

Чтобы реализовать это, мне пришлось добавить функцию isLast в класс Node, потому что иначе, Stack. pop не мог узнать, пора ли удалить top . Я тоже не на 100% доволен этим решением (и если бы я не удалил член размера из стека, я мог бы использовать его для решения проблемы)

Но в целом это решение и чище, и проще, чем вышеуказанные попытки. (Это единственный язык, на отладку которого я потратил меньше часа;))

#include <stdexcept>

class Node {
public:
    Node(int value, Node* prev = 0) : head(value), tail(prev) { ++live;}
    ~Node() { 
        --live;
        delete tail;
    }

    Node(const Node& other) : head(other.head), tail(0) {
        ++live;
        if (other.tail != 0){
            tail = new Node(*other.tail);
        }
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }

        Node* oldTail = tail;
        tail = new Node(*other.tail);
        delete oldTail;

        head = other.head;

        return *this;
    }

    void push(int val){
        tail = new Node(head, tail);
        head = val;
    }

    int peek(){
        return head;
    }
    void pop(){
        Node* oldTail = tail;
        head = tail->head;
        tail = tail->tail; // lol
        oldTail->tail = 0;
        delete oldTail;
    }

    bool isLast() { return tail == NULL; }

    int getSize() const{
        int i = 0;
        for (const Node* cur = this; cur != NULL; cur = cur->tail, ++i){}
        return i;
    }


private:
    Node* tail;
    int head;
};

class Stack {
public:
    Stack() : top(){}
    ~Stack() { delete top; }
    Stack(const Stack& other) : top() {
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other){
        if (this == &other){
            return *this;
        }

        Node* newTop = NULL;
        if (!other.empty()){
            newTop = new Node(*other.top);
        }
        delete top;
        top = newTop;

        return *this;
    }

    void push(int val){
        if (empty()) {
            top = new Node(val);
        }
        else {
            top->push(val); 
        }
    }

    int peek(){
        if (empty()){
            throw std::exception("Empty stack");
        }
        return top->peek();
    }
    int pop(){
        int result = peek();

        if (top->isLast()){
            delete top;
            top = NULL;
        }
        else {
            top->pop();
        }


        return result;
    }

    int getSize() const{
        if (empty()){ return 0; }
        return top->getSize(); 
    }

private:
    bool empty() const { return top == NULL; }
    Node* top;
};

Поскольку все это началось как попытка показать вам, почему C ++ не очень хороший язык для начинающих, я думаю, что могу с уверенностью сказать миссия выполнена!

:)

s единственный, на отладку которого я потратил меньше часа. ;))

#include <stdexcept>

class Node {
public:
    Node(int value, Node* prev = 0) : head(value), tail(prev) { ++live;}
    ~Node() { 
        --live;
        delete tail;
    }

    Node(const Node& other) : head(other.head), tail(0) {
        ++live;
        if (other.tail != 0){
            tail = new Node(*other.tail);
        }
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }

        Node* oldTail = tail;
        tail = new Node(*other.tail);
        delete oldTail;

        head = other.head;

        return *this;
    }

    void push(int val){
        tail = new Node(head, tail);
        head = val;
    }

    int peek(){
        return head;
    }
    void pop(){
        Node* oldTail = tail;
        head = tail->head;
        tail = tail->tail; // lol
        oldTail->tail = 0;
        delete oldTail;
    }

    bool isLast() { return tail == NULL; }

    int getSize() const{
        int i = 0;
        for (const Node* cur = this; cur != NULL; cur = cur->tail, ++i){}
        return i;
    }


private:
    Node* tail;
    int head;
};

class Stack {
public:
    Stack() : top(){}
    ~Stack() { delete top; }
    Stack(const Stack& other) : top() {
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other){
        if (this == &other){
            return *this;
        }

        Node* newTop = NULL;
        if (!other.empty()){
            newTop = new Node(*other.top);
        }
        delete top;
        top = newTop;

        return *this;
    }

    void push(int val){
        if (empty()) {
            top = new Node(val);
        }
        else {
            top->push(val); 
        }
    }

    int peek(){
        if (empty()){
            throw std::exception("Empty stack");
        }
        return top->peek();
    }
    int pop(){
        int result = peek();

        if (top->isLast()){
            delete top;
            top = NULL;
        }
        else {
            top->pop();
        }


        return result;
    }

    int getSize() const{
        if (empty()){ return 0; }
        return top->getSize(); 
    }

private:
    bool empty() const { return top == NULL; }
    Node* top;
};

Поскольку все это началось как попытка показать вам, почему C ++ не очень хороший язык для начинающих, я думаю, что могу с уверенностью сказать миссия выполнена!

:)

s единственный, на отладку которого я потратил меньше часа. ;))

#include <stdexcept>

class Node {
public:
    Node(int value, Node* prev = 0) : head(value), tail(prev) { ++live;}
    ~Node() { 
        --live;
        delete tail;
    }

    Node(const Node& other) : head(other.head), tail(0) {
        ++live;
        if (other.tail != 0){
            tail = new Node(*other.tail);
        }
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }

        Node* oldTail = tail;
        tail = new Node(*other.tail);
        delete oldTail;

        head = other.head;

        return *this;
    }

    void push(int val){
        tail = new Node(head, tail);
        head = val;
    }

    int peek(){
        return head;
    }
    void pop(){
        Node* oldTail = tail;
        head = tail->head;
        tail = tail->tail; // lol
        oldTail->tail = 0;
        delete oldTail;
    }

    bool isLast() { return tail == NULL; }

    int getSize() const{
        int i = 0;
        for (const Node* cur = this; cur != NULL; cur = cur->tail, ++i){}
        return i;
    }


private:
    Node* tail;
    int head;
};

class Stack {
public:
    Stack() : top(){}
    ~Stack() { delete top; }
    Stack(const Stack& other) : top() {
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other){
        if (this == &other){
            return *this;
        }

        Node* newTop = NULL;
        if (!other.empty()){
            newTop = new Node(*other.top);
        }
        delete top;
        top = newTop;

        return *this;
    }

    void push(int val){
        if (empty()) {
            top = new Node(val);
        }
        else {
            top->push(val); 
        }
    }

    int peek(){
        if (empty()){
            throw std::exception("Empty stack");
        }
        return top->peek();
    }
    int pop(){
        int result = peek();

        if (top->isLast()){
            delete top;
            top = NULL;
        }
        else {
            top->pop();
        }


        return result;
    }

    int getSize() const{
        if (empty()){ return 0; }
        return top->getSize(); 
    }

private:
    bool empty() const { return top == NULL; }
    Node* top;
};

Поскольку все это началось как попытка показать вам, почему C ++ не очень хороший язык для начинающих, я думаю, что могу с уверенностью сказать миссия выполнена!

:)