STL Stack Implementation

Question

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 T>
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 <iostream>
#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 <class T>
bool stack<T>::empty() { return (root_node == nullptr); }

/* FUNCTION: Returns current size of the stack */
template <class T>
int stack<T>::size() { return elements; }


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

template <class T>
void stack<T>::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++;
 }
}

/* FUNCTION: Removes element at the top of the stack */
template <class T>
void stack<T>::pop() {

if (size() > 1) {
node *temp_node = new node;
temp_node = root_node->next;

root_node = temp_node;
elements--;
 }

else if (size() == 1) {
root_node = nullptr;
elements--;
}

else {cout << "\nOperation pop() failed: Stack is empty!" << endl;}
}

/* FUNCTION: Retrieves element at the top of the stack */
template <class T>
T stack<T>::top() {
if (!empty()) {return root_node->node_data;}
else {cout << "\nOperation top() failed: Stack is empty!" << endl; return -1;}
}

/* FUNCTION: Prints the stack contents */
template <class T>
void stack<T>::print() {
int index = size();
for (int i = 1; i < index; i++) {
        cout << "Element " << i << ": " << "  "  << top() << endl;
        pop();
        }
}

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

Answer 1

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<typename T>
void stack<T>::push(T data) // pass by value here
{
    root = new node{ std::move(data), root }; // and move the value here
    ++elements;
}

template<typename T>
const T&                // return a const T&
stack<T>::top() const   // and function is const               
{
    if (!root)
        throw std::runtime_error("stack<T>::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 T>
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 <class T>
void stack<T>::pop() {
    if(empty())
        throw std::runtime_error{"stack<T>::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).

Answer 2

As noted by @Jamal in the comments.
You should probably move to a more standard indentation scheme.

Looking at node

It is common to name types with a leading capitol letter (to distinguish them from objects).

struct node {

Also the * is part of the type and thus placed next to the type info.

node *next;

Note: Your usage is very "C" like. But "C++" is a different language.

I hate these comments.

    //default ctor
    //default dtor

They provide no extra information. Comments that do not help can become out of date and this makes it hard to justify. Comments are better used to explain why (or intricate details). The how is well documented by the code itself (making comments repeat the code is usless). So unless your comments can be best described as "Why" comments don't use them.

This looks wrong.

    ~node() { delete root_node; }

You are deleting the root_node of the parent. That seems to be an inversion of the ownership principle. I would say the parent owns the root_node. And each node owns the node linked by next. Thus you should not be deleting the other way up the chain.

looking at stack

Prefer to include things from most specific to most general. This will stop you polluting the name space of header files that don't need them.

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

Here I would reverse the order.
Put "stack.h" first it is the most specific. Then you can include things needed in the header file and they become available here.

I prefer not to do this.

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

If you are passing big items as data.

void stack<T>::push(T data) {

Then passing by value will cause it to be copied. You should pass it by const reference.

The following forces contruction by default constructor. Folloed by a copy.

root_node = new node;         // `node` contains a T and it must be 
                              // be created by default construction.

root_node->node_data = data;  // Force a copy of the object into node.

The other side of the else is even worse with even more copies of the data being done.

The actual body of push can be made much simpler.

void stack<T>::push(T data) {
    root_node = new node(data, root_node);
    elements++;
}

That should be all you need (just make a better constructor to node).

Here we are leaking memory:

node *temp_node = new node;    // Create a node we don't need.
temp_node = root_node->next;   // Then we leak it the net line.

Then we leak the root node.

root_node = temp_node;         // The old value of root node was just
                               // lost and no way to delete it.

A better pop is like this:

void stack<T>::pop() {
    node* tmp = root_node;       // Keep track of the old root.
    root_node = root_node->next; // Remove the root node from the list.
    elements--;
    delete tmp;                  // delete the old root.
}

Your print() only prints to std::cout. That might not be flexible enough. So I would pass the stream you want to print on as a parameter. You can default to std::cout.

void print(std::ostream& stream = std::cout);

Also your print seems to destroy the stack (by calling pop()). Since the print has access to the internal members of the stack I don't really see the need for this.

General Comments

If there is an error don't print the error as part of the stack. The user of your stack may not want to output an error message here.

else {cout << "\nOperation top() failed: Stack is empty!" << endl; return -1;}

I would just throw an exception.

else { throw std::runtime_error("XXXX");}

Prefer pre-increment to post increment.
Technically for integers/pointers there is no difference. But sometimes code changes and the underlying types becomes something else (like an iterator). In this situation it is more effecient to use pre-increment. So just get into the habbit of using pre-increment.

When a method does not modify the state of an object then it should be marked const. This allows you to use the object in a const context. This is referred to as const correctness.

class Stack
{
   public:
      bool empty() const;
      int  size()  const;

It is normal to put template code in a header file. This is because the definition of the code is required at the point of use. Personally I still don't put the code into the class (unless it is very small) because it clutters the interface declaration.

This is what I would do:

#ifndef STACK_H
#define STACK_H

#include <iostream>
#include <stdexcept>

template <typename T>
class Stack {

        struct Node {    
            T       data;
            Node*   next;

            Node(T const& data, Node* next)
                : data(data)
                , next(next)
            {}
            Node(T&& data, Node* next)   // With C++11 allow move construction
                : data(std::move(data))
                , next(next)
            {}
        };

    public:
        ~Stack();
        void push(T const& data);
        void push(T&& data);     // WIth C++ 11 allow move construction
        bool empty() const;
        int  size()  const;
        T    top()   const;
        void pop();
        void print(std::ostream& str = std::cout) const;


    private:
        Node*   root     = nullptr;
        int     elements = 0;
};

template<typename T>
Stack<T>::~Stack()
{
    Node* next;
    for(Node* loop = root; loop != nullptr; loop = next)
    {
        next = loop->next;
        delete loop;
    }
}
template<typename T>
void Stack<T>::push(T const& data)
{
    root = new Node(data, root);
    ++elements;
}
template<typename T>
void Stack<T>::push(T&& data)
{
    root = new Node(std::forward(data), root);
    ++elements;
}
template<typename T>
bool Stack<T>::empty() const
{
    return root == nullptr;
}
template<typename T>
int Stack<T>::size() const
{
    return elements;
}
template<typename T>
T Stack<T>::top() const
{
    if (root == nullptr)
    {   throw std::runtime_error("Invalid Action");
    }
    return root->data;
}
template<typename T>
void Stack<T>::pop()
{
    if (root == nullptr)
    {   throw std::runtime_error("Invalid Action");
    }
    Node*   tmp = root;
    root    = root->next;
    --elements;
    delete tmp;
}
template<typename T>
void Stack<T>::print(std::ostream& str) const
{
    int id = 0;
    for(Node* loop=root; loop != nullptr; loop=loop->next, ++id)
    {
        str << "Element: " << id << "  = " << loop->data << "\n";
    }
}

#endif