There is no reason for an array for deep-copying a stack. Since you have all the pointers to the nodes in your current stack chain, just walk that linked list. The unusual part of this algorithm involves forward-chaining the new nodes as they're entered, and thereby preserve the original stack order. There are a number of ways to do this, but I prefer using a single pointer-to-pointer that always holds the address of the pointer that will be populated on the next copy.
Stack(const Stack<T>& other)
: top(nullptr)
{
const Node* p = other.top;
Node **pp = ⊤
while (p)
{
*pp = new Node(*p);
p = p->next;
pp = &(*pp)->next;
}
*pp = nullptr;
}
When this is done, the stack will be deep-copy replicated and preserve the source objects order. And I strongly advise implementing a Node(const Node&)
copy-ctor that copies the data element only and hard-sets the next pointer to null.
How It Works
In the end, this is nothing more than a single-scan copy of a forward-linked list. The pointer pp
always holds the address of the next pointer that will be assigned a new node. It is important to remember the pointer it is addressing is part of the list, not some temporary pointer. Initially pp
is assigned the address of the top pointer, which is not-coincidentally already initialized to NULL. From there, the following is repeated until we run out of nodes:
- Assign a copy of the current source node to
*pp
. This means the pointer addressed bypp
will receive the new node address. - Advance
pp
to hold the address of thenext
member of the very node it was just assigned. This becomes the next target for the next insertion - Advance the source pointer to next source node.
This is repeated until we run out of nodes. At that time pp
holds the address of the last node's next
pointer, which should be assigned null for our list to properly terminate. That is the purpose of the closing *pp = nullptr;
. With that, the list is now terminated and the object now has a replica of the source object's linked list.
Some food for thought. What happens if the source list is initially empty? Would this work with a circular list (answer: no, don't even try it).