implementing stack with a linked list in C++ , copy constructor

Question

I am trying to implement a stack using a linked list in C++, and I don't know how to write correctly the copy constructor of the stack class.

I am using the following classes:

class Node{
    int m_num;
    Node* m_pNext;
public:
    Node();
    ~Node();
    //and the standard get&set functions..
}


class LinkedList{
    int m_size;
    Node* m_pHead;
public:
    LinkedList();
    LinkedList(const LinkedList& obj);
    ~LinkedList();
    //and the standard get&set functions..
}


class Stack{
    LinkedList m_stack;
public:
    Stack();
    Stack(const Stack& copyStack);
    ~Stack();
}

I did wrote the copy constructor of the LinkedList class, and it is working well. My problem is with the Stack class, there I cant get a copy of my current stack in order to search in the stack (involves pop() and so on).

I did try to write the following:

Stack::Stack(const Stack &copyStack){
    LinkedList m_stack = copyStack.m_stack;
}

and as I said, it doesnt work..

I am new to C++, and I guess I am missing something there..

Answer 1

If you're doing this to learn C++ as you should be using it for normal programming, consider taking a different route (e.g. try creating a simple program, not a data structure). That's because C++ already has standard library implementations for most things you'd use here, such as a pointer automatically managing memory deallocation (std::unique_ptr), a linked list (std::forward_list and std::list), and even a stack (std::stack).

To learn the language, you should learn using these first, before you dive into how they can be implemented.

---

If, on the other hand, you're doing this to learn about data structures and memory management (and C++ is just a tool in this regard), go ahead. But you'd be better off if you knew the language better before you dive into such low-level tasks.

Nevertheless, there are two problems in your code. One is that you declare a new local variable instead of assigning to a member. You probably meant this:

Stack::Stack(const Stack &copyStack){
    m_stack = copyStack.m_stack;
}

Second, this requires LinkedList to implement an appropriate copy assignment operator. Without this, the default-generated one will be used, which simply copies all members. That would result in a shallow copy only - both the newly constructed stack object and the original copyStack would point to the same nodes inside their LinkedList - probably not what you want.

Still, a better way to do this would be to initialise m_stack with the appropriate value; what you're doing now initialises m_stack to empty and then assings into it. You should change the copy constructor to use a member-initialiser-list:

Stack::Stack(const Stack &copyStack) : m_stack(copyStack.m_stack)
{}

This will call the copy constructor of LinkedList, and not the assignment operator.

Still, any class which manages resources (actually any C++ class) must follow the "Rule of Three" to work correctly. That rule states that if a class has a custom copy constructor, custom copy assignment operator or custom destructor, it should define all 3 of those to work correctly. LinkedList has a copy constructor and a destructor, which means you should also provide a copy assignment operator, e.g. like this:

LinkedList& operator= (const LinkedList &src);

I will leave its implementation as an excercise for the reader ;-) You can also look up the "copy and swap" idiom.

Once you do that, you should actually remove the copy constructor (and probably destructor too) from Stack, as the default-generated one will do just what you need - call the copy constructor on each member.

Answer 2

The compiler-generated copy constructor would work.

If you really want to implement it manually, then:

Stack(const Stack& copyStack) : m_stack(copyStack.m_stack) {}

Note that you should use the constructor initialization list. Then m_stack is created by using LinkedList's copy-constructor.

Of course, this relies on the fact that you must have implemented LinkedList(const LinkedList& obj); correctly!

Answer 3

What you are trying to implement is already part of the language:

#include <stack>
#include <list>

int main()
{
    std::stack<int, std::list<int>> my_stack;
}

Answer 4

You create a local variable called m_stack. This masks the member variable m_stack. You need to remove the LinkedList:

Stack::Stack(const Stack &copyStack){
    m_stack = copyStack.m_stack;
}

Further more you also need a copy assignment operator (operator=) that copies the members. You defined a copy constructor, so you need to think about the "Rule of Three" for c++