STL Stack Implementation

I implemented std::stack from the STL for deeper understanding of the language and memory since I still am only a beginner. I implemented the stack using a singly linked list.

Header file:

/* Header file for abstract data type "STACK" implemented using a linked list  */

#ifndef STACK_H
#define STACK_H

template 
class stack {

public:
void push(T);     //Function that inserts elements into the stack
bool empty();     //Function to test whether the stack is empty
T top();          //Returns top element of stack
void pop();       //Removes element at the top of the stack
int size();       //Returns size of stack
void print();     //Prints stack contents

struct node {     //Definition of node structure with constructor and destructor

T node_data;
node *next;

//default ctor
node() { next = nullptr;  }

//default dtor
~node() { delete root_node; }
};

private:
node *root_node = nullptr;
int elements = 0;
};

#endif //STACK_H

And here is the actual implementation file:

```
/ Definitons of the STACK data structure implemented using a linked list /

#include
#include "stack.h"

using std::cout;
using std::endl;

/ FUNCTION: Test to check if the stack is empty or has at least one element /

template
bool stack::empty() { return (root_node == nullptr); }

/ FUNCTION: Returns current size of the stack /
template
int stack::size() { return elements; }

/ FUNCTION: Adds nodes to the stack with one argument which is the data to be inserted /

template
void stack::push(T data) {

//Operation to preform if the stack is empty.
//Root element is popped off last (First in, Last out)
if ( empty() ) {
root_node = new node;
root_node->node_data = data;
root_node->next = nullptr;
elements++;
}

//Operation to preform if stack is not empty.
//Elements inserted into stack with dynamic allocation.
else {
node *new_node = new node;
new_node = root_node;
root_node->next = new_node;
root_node->node_data = data;

elements++;

I would appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.

First, (contrary to Loki Astari's answer) I think your style is correct (i.e. please do not capitalize the first letter of your classes - keep them matching the std:: style).

Regarding the APIs of your code:

-
Your code doesn't enforce const correctness

-
For argument types, consider the following convention:

-
Observed parameter (no modification of the value in the function)

void function(const argument& a);

-
I/O parameter (function modifies the parameter, not owner):

void function(argument& a); // a is modified in the function (I/O parameter)

-
Owned parameter:

void function(argument a); // function "owns" a (gets it's own exclusive copy)

Following this, push() and top() should be written like this:

template
void stack::push(T data) // pass by value here
{
    root = new node{ std::move(data), root }; // and move the value here
    ++elements;
}

template
const T&                // return a const T&
stack::top() const   // and function is const               
{
    if (!root)
        throw std::runtime_error("stack::top: empty stack");
    return root->data;
}

Taking a parameter by value in push has these advantages:

• specifies ownership in the interface

• enables you to use all constructors of type T here

-
is exception safe (if the instance of the arg cannot be created, code will fail before entering the function body).

-
The size API:

int size();

Should be:

std::size_t size() const;

The print API has more problems:

-
It clears the list (either rename to "destructive_print", or ensure the iteration is not destructive). If you implement it in a non-destructive way, mark it const.

-
It introduces a dependency on std::cout that has nothing to do with the functionality of objects. Ideally, it shouldn't be a member. If you still want to have it as a member, pass the output stream instance as a parameter.

The constructor of the node class should construct a fully valid instance in one step. To decide on it's parameters, you should look at how you use it:

Usage example (your old code):

root_node = new node;
root_node->node_data = data;
root_node->next = nullptr;

Optimal example (new client code):

root_node = new node{ std::move(data), root_node }; // use std::move on the data

implies the node should be implemented like this:

template 
class stack {
    // ...
    struct node { // struct, because it is internal and only
                  // access will be in stack
                  // (i.e. we can guarantee correct use in client code)

         T *node_data;
         node* next;
    };
}

The size should also be of std::size_t type.

Your stack doesn't have a destructor. The destructor should call delete on each node, in an iteration).

Your print element skips the last element in the list, as you begin indexing from 1 instead of 0, to less than number of elements. This means you iterate [elements - 1] times.

The pop() implementation can be written with no special case for one element:

template 
void stack::pop() {
    if(empty())
        throw std::runtime_error{"stack::pop(): empty stack"};

    node* new_root = root_node->next;
    delete root_node;
    root_node = new_root;
    --elements;
}

Regarding the implementation of your class:

Do not print error messages, throw exceptions (this allows client code to decide what to do in case of an error, instead of forcing client code to get messages printed into it's application's output stream).

StackExchange Code Review Q#51794, answer score: 11