Stack implementation in C++

Question

I'm trying to implement a stack class as a learning exercise. This is my StackNode class,

template <typename T>
class StackNode{
public:
    T data_{};
    StackNode<T> next_;

    StackNode() : data_(nullptr), next_(nullptr){}
    StackNode(const T& data_) : data_(data_),next_(nullptr) {}

};

I use this node to create a Stack, this is the code,

template <typename T>
class Stack{
private:

    StackNode<T> top_;
    std::size_t size_{};

public:
    Stack() : top_(nullptr), size_ (0){}
    void push(const T& item){
        StackNode<T> p{item};
        p.next_ = top_;
        top_ = p;
    }

    T pop(){
       StackNode<T> p = top_;
        top_ = top_.next_;
        return p;
    }

    T peek(){
        return top_.data_;
    }

};

This is the calling Client,

Stack<int> stack{};
stack.push(12);
stack.push(13);
std::cout << stack.peek() << std::endl;
stack.pop();
std::cout << stack.peek() << std::endl;

I get the following compilation errors

In file included from /Users/mstewart/Dropbox/codespace/private/cpp-drive/data-structures/main.cpp:2:
In file included from /Users/mstewart/Dropbox/codespace/private/cpp-drive/data-structures/Stack.hpp:5:
/Users/mstewart/Dropbox/codespace/private/cpp-drive/data-structures/StackNode.h:12:18: error: field has incomplete type 'StackNode<int>'
    StackNode<T> next_;
                 ^
/Users/mstewart/Dropbox/codespace/private/cpp-drive/data-structures/Stack.hpp:13:18: note: in instantiation of template class 'StackNode<int>' requested here
    StackNode<T> top_;
                 ^
/Users/mstewart/Dropbox/codespace/private/cpp-drive/data-structures/main.cpp:6:16: note: in instantiation of template class 'Stack<int>' requested here
    Stack<int> stack{};
               ^
/Users/mstewart/Dropbox/codespace/private/cpp-drive/data-structures/StackNode.h:9:7: note: definition of 'StackNode<int>' is not complete until the closing '}'
class StackNode{
      ^

Can someone help me understand what I'm doing wrong. I'm new to C++

[Get a good beginners book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) and read about *pointers* and *lists*. — Some programmer dude, Dec 29 '17 at 19:10
*I'm trying to implement a stack class as a learning exercise* -- You would have better luck if you just used a `std::deque` as a member, and just call those functions in the deque to `push`, `pop`, etc. — PaulMcKenzie, Dec 29 '17 at 19:11
I suspect that you already know about [`std::stack`](http://en.cppreference.com/w/cpp/container/stack), don't you? If you're forced to create that on your own (i.e. reinvent the wheel), you can have an orientation about your compiler's implementation of that standard class. It's usually disclosed. — user0042, Dec 29 '17 at 19:13
@user0042 I've found that library code isn't as readable as one would like, at least Microsoft's version. — Mark Ransom, Dec 29 '17 at 19:20
The problem is that so many new programmers think that doing this in C++ is something that can be learned in a day. Not so. You have to learn pointer, memory management, how to implement correct copy semantics, all *on top of* trying to get the basic data structure details in place. This is not a trivial exercise. — PaulMcKenzie, Dec 29 '17 at 19:21
@user673679 -- What I'm saying is that to give an answer to these questions require writing the entire class for them to study. Are you prepared to do that? It's not as if most if these questions just need a tweak here or there to solve the problem. On rare occasions, I take them to a link with code I've written, and stated "please study how xyz class should be written", only because the poster's attempt is so far off the mark. — PaulMcKenzie, Dec 29 '17 at 20:46
@PaulMcKenzie Well, I guess I wasn't fair on your "[you could use the std library internally]" comment. It just seems like a basic "you seem to be trying to do this do you want to [x]" paperclip answer would be better than "[don't do it]" in the comments. — user673679, Dec 29 '17 at 21:33

user673679 · Answer 1 · 2017-12-29T21:26:57.377

"A class instance cannot contain an instance of itself" - Oliver Charlesworth, The Comment Section.

As mentioned elsewhere, the class is not fully defined at the point of use (see the last line in the compiler error message), and would have problems with memory layout.

You therefore need to use pointers to manage the items in the array. One relatively straightforward adjustment to your code is to use std::unique_ptr instead (avoiding manual memory management with new and delete).

IDEOne link w/ code

Note the ownership semantics where the stack owns the top node, which owns the node underneath, etc. You could emulate this with manually with raw pointers using new in the push function, and delete in the pop function.

Stack implementation in C++

1 Answers1