Node stack class (peer review required)

Question

I recently wrote a node stack class, in accordance with the instructions (specifications in the comments before the code, taken from the forum post). I was told to send it here for a review by one of the friendlier members of the SO community, so here it is. For simplicity: I put the definitions in the implementation. I understand when to use header files =)

Basically, I want to know how much I use deletion. I'm still not sure of myself when it comes to using destructors; the specifications made it sound ONLY the time when I should delete nodes, it should be during pop music, and everything else is unsafe. I also don't understand the use of constructor constructor / copy assignment here.

In any case, any errors or comments about the code will be great.

/*stack class

Background: the specs for this are, verbatim: 

"Write a node-based stack class smile.gif

The stack is one of the most fundamental data structures used in computer science.

A stack has three basic operations:

push(value) - puts a value on the top of the stack
pop() - removes and returns the value that on the top of the stack
peek() - return (but does not remove) the value off the top of the stack

Before creating the stack, you first have to create a Node class, which is a 
very basic class with just two member variables: the value of the node, and a 
pointer to the previous node in the stack.

Your stack should have only one member variable: the top node of the stack. 
When you push, you add a node with the new value, with it previous pointer 
pointing towards the current stack top item. When you pop, you delete the top 
node and then set the top of the stack to whatever that node previous node 
pointer was.

push, pop, and peek must all run in constant time.

You should write it so that it can only push (and pop/peek) ints."
*/

#include <string>
#include <iostream>

class Node
{
    private:
        int value;
        Node* prev;

    public:
        int returnValue() { return value; }
        Node* returnPtr() { return prev; }

        /* constructors and destructors */

        Node(int val, Node* ptrToLast) 
        {
            value = val;            
            prev = ptrToLast; 
        }
};

class Stack
{
    private:
        Node* top;
        int size;

    public:
        Stack() { size = 0; top = NULL; }
        //added this after told the need for a destructor; not sure if it works
        ~Stack() {   
                    while (top != NULL) 
                    {  
                        Node* tempPtr = top.returnPtr();
                        delete top;
                        top = tempPtr;
                    }
                 }     

        Node* returnTopPtr() { return top; }

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

        //bonus; figured it might be worth knowing how many
        //nodes are in a given stack 
        int returnSize();
};

int Stack::returnSize()
{
    return size; 
}

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

int Stack::peek()
{
    return top->returnValue();
}


int Stack::pop()
{    
    const std::string throwStr = "You are trying to access/delete a node that doesn't exist. Seriously. ";

    if (size == 0)
    {
        throw(throwStr);
    }

    --size; 

    Node* tempPtr = top->returnPtr();
    int tempVal = top->returnValue();
    delete top;
    top = tempPtr;

    return tempVal;    
}

Answer 1

First , a few general comments that in this case do not cause problems, but some can do this in other situations:

You should only throw exceptions derived from the class std::exception. C ++ allows you to throw any type (e.g. a string in your case), but this is a really bad idea.

, : ( . , , , . -, , )

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

return* . size() topPtr(), , , getSize() getTopPtr()

, .;) -, .:)

, , :

, :

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

, node ( ):

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

:

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

:

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

t.returnSize() 1, t.top node s, . (, , node) :

Stack(const Stack& s);

, , . :

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. node s t, . ( , , Stack. , , , )

, , :

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

, node (, . , ). , . s 2, top node , , , . , , , int.

, , node, . . , , .

" " . , , ? ? ( ). - ( , ), , ? , ? ( , )

- , . , . sometihng , , ++.:)

Bonus:

, , RAII, : -, , , , , . -, , , . . ( , getSize): ( live - , . Stack, , , , . , 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 - , , , , , . , Stack 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 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 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 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 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. Node , . top node... . , Stack.push , Node ., , , node.

Stack still needs to access the tail_ member of Node `, accessor , . , , .

#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

, , . Node , push/pop/peek. Stack - . . Stack Node, . node, - node , , node. .

, 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;
};

, ++ - , , !

:)

Answer 2

- . , - ( , .)

1 - , , , , ! . , node, NULL- > returnValue(). .

2 - temp, push, , .

3 - / , . , , , ++ . , . (IE: node.)

4 - returnTopPointer - - ​​ , .

, .

Answer 3

Stack:: push() ( ), . , .

NULL, , peek(), -, . . , pop() push().

, :

   Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}

Answer 4

, - , , , , , , - undefined. , , , , , , ( , ) - - , .

, , , , ( ), :

    
class Stack
{
  // a nested implementation class that the client needs to know nothing about
  struct Node
  {
     Node* prev;
     int value;
     Node(Node* prev, int value) : prev(prev), value(value) { }
     Node() : prev(0), value(0) { } 
     ~Node() { delete prev; }  // clean up after yourself

     // copy recursively until you hit a null pointer
     Node(const Node& o) : value(o.value), prev( prev ? new Node(*prev) : 0 ) { }
  };

  Node* head_;
  int size_;

public:  

  Stack() : head_(0), size_(0) { }
  ~Stack() { delete head_; }

  // copy recursively until null
  Stack(const Stack& o) : head_(o.head_ ? new Node(*o.head_) : 0) { }

  // use copy constructor to do assignment
  Stack& operator=(const Stack& o)
  {
    Stack copy(o);
    Node* cur = head_;

    head_ = copy.head_;
    size_ = copy.size_;

    copy.head_ = cur;  // copy destructor will delete
    return *this;
  }

  void push(int value)
  {
    head_ = new Node(head_,value);
    ++size_;
  }
  int peek() const
  {
    if (!head_) throw "Attempting to peek off an empty stack!";
    return head_->value;
  }
  int pop()
  {
    if (!head_) throw "Attempting to pop off an empty stack!";
    int ret = head_->value;

    Node* cur = head_;    // hold on to it so we can delete it
    head_ = head_->prev;  // adjust my pointer
    cur->prev = 0;        // if this is not set to 0, all nodes will be deleted

    delete cur;
    --size_;
    return ret;
  }
  int size() const { return size_; }
};



// -- an easier way to write a stack of ints ;)
struct VecStack
{
    std::vector<int> vec;

    void push(int x)
    {
        vec.push_back(x);
    }
    int peek() const
    {
        if(vec.empty()) throw "Is Empty";
        return *--vec.end(); // you may prefer vec[vec.size() - 1];
    }
    int pop() 
    { 
        if (vec.empty()) throw "Is Empty";
        int ret = *--vec.end();
        vec.pop_back();
        return ret;
    }
    int size() const { return vec.size(); }
};

Answer 5

- :

Node* tempPtr = top;
top = new Node(value, tempPtr);

top = new Node(value, top); 

, . , :

Node* oldTopPtr = top;
top = new Node(value, oldTopPtr);  

Answer 6

, () . , copy-and-swap =, , - , . jalf =, , std:: swap; -)

jalf. , - , , ; -).

RAII, , jalf-, con/destructors. , "" , . SafeNode , , , .

#include <stdexcept>
#include <algorithm>

class Stack {
    private:
    struct Node {
        Node *prev;
        int value;
        Node(int v, Node *p = 0): value(v), prev(p) { ++live; }
        ~Node() { --live; }
    };

    public:
    Stack() : top(0), size(0) { }
    Stack &operator=(const Stack &rhs) {
        if (this != &rhs) {
            Stack s(rhs);
            swap(s);
        }
        return *this;
    }

    public:
    void push(int value) {
        top.node = new Node(value, top.node);
        ++size;
    }

    int pop() {
        // get node and value at the top of the stack
        Node *thisnode = top.get();
        int retval = thisnode->value;

        // remove top node from the stack and delete it
        top.node = thisnode->prev;
        --size;
        delete thisnode;

        return retval;
    }

    int peek() const {
        return top.get()->value;
    }

    size_t getSize() {
        return size;
    }

    void swap(Stack &rhs) {
        top.swap(rhs.top);
        std::swap(size, rhs.size);
    }

    private:
    struct SafeNode {
        Node *node;
        SafeNode(Node *n) : node(n) {}
        SafeNode(const SafeNode &rhs_) : node(0) {
            const Node *rhs = rhs_.node;
            if (rhs == 0) return;
            SafeNode top(new Node(rhs->value));
            Node *thisnode = top.node;
            while(rhs = rhs->prev) {
                thisnode->prev = new Node(rhs->value);
                thisnode = thisnode->prev;
            }
            swap(top);
        }
        ~SafeNode() {
            while (node != 0) {
                Node *nextnode = node->prev;
                delete node;
                node = nextnode;
            }
        }
        void swap(SafeNode &rhs) { std::swap(node, rhs.node); }
        Node *get() const {
            if (node == 0) throw std::logic_error("Empty stack");
            return node;
        }
        private: SafeNode &operator=(const SafeNode &);
    };

    private:
    SafeNode top;
    size_t size;

};

namespace std {
    template <>
    void swap<Stack>(Stack &lhs, Stack &rhs) {
        lhs.swap(rhs);
    }
}

Answer 7

, getter, ctor dtor, , , .

, :

/*stack class

Background: the specs for this are, verbatim: 

"Write a node-based stack class smile.gif

The stack is one of the most fundamental data structures used in computer science.

A stack has three basic operations:

push(value) - puts a value on the top of the stack
pop() - removes and returns the value that on the top of the stack
peek() - return (but does not remove) the value off the top of the stack

Before creating the stack, you first have to create a Node class, which is a 
very basic class with just two member variables: the value of the node, and a 
pointer to the previous node in the stack.

Your stack should have only one member variable: the top node of the stack. 

ADDENDUM: also a size variable is allowed.

When you push, you add a node with the new value, with it previous pointer 
pointing towards the current stack top item. When you pop, you delete the top 
node and then set the top of the stack to whatever that node previous node 
pointer was.

push, pop, and peek must all run in constant time.

You should write it so that it can only push (and pop/peek) ints."
*/

#include <string>
#include <iostream>


class Stack
{
    private:
        struct Node
        {
            public:
               /* constructors and destructors */        
               Node(int value, Node* prev) : value_(value), prev_(prev) { }
               Node(Node const& other) { value_ = other.value_; prev_ = other.prev_; }
               //there is no ~Node, because the Stack does all the manual management

            /* private data members */
            private:
               /* the value of the node */
               int value_;
               /* a pointer to the previous node on the stack */
               Node* prev_;

            /* getter functions */
            public:
               int value() { return value_; }
               Node* prev() { return prev_; }
        };

    public:
        /* constructors and destructors */
        Stack() : size_(0), top_(0) { }
        ~Stack();     


    private:
        /* pointer to the very top node; important to LIFO phil */
        Node* top_;
        /* size of the stack (main value is whether stack is empty */
        int size_;

    public: 
        //not for public use
        void setTop(Node *top) { top_  = top;  }
        void setSize(int size) { size_ = size; }
        Node* top() { return top_;  }
        int size()  { return size_; }


    public:
        /* insertion, deletion, and traversal functions */
        void push(int);
        int pop();
        int peek();
};

Stack::~Stack() 
{ 
    while (top() != NULL)
    { 
        Node* tempPtr = top()->prev();
        delete top_;
        setTop(tempPtr);
    }
} 

void Stack::push(int value)
{ 
    setSize(size() + 1);
    Node *newTop = new Node(value, top());
    setTop(newTop);
}

int Stack::peek()
{
    return top()->value();
}


int Stack::pop()
{    
    if (size() == 0)
    {
        throw; //up
    }

    setSize(size() - 1);

    Node* tempPtr = top()->prev();
    int tempVal = top()->value();
    delete top();
    setTop(tempPtr);

    return tempVal;    
}

Answer 8

• push(value) -
• pop() - removes and returns the value that is at the top of the stack
• peek() - returns (but does not delete) the value from the top of the stack