Question

I have a class stack which is defined like this:

#ifndef STACK_H
#define STACK_H
#include "MyException.h"
#include <iostream>

using namespace std;

template<class T>
class Stack;

template<class T>
ostream& operator<<(ostream&,Stack<T>&);

template<class T>
class Stack
{
public:

    friend ostream& operator<< <T>(ostream&,Stack<T>&);

    /*The constructor for the Stack class*/
    Stack();

    /*The copy constructor*/
    Stack(const Stack<T>& other);

    Stack<T>& operator=(const Stack<T>& other);

    /*The destructor for the stack class*/
    ~Stack();

    void push(const T& el);

    T pop();

    bool isEmpty();

private:
    /*The node class.*/
    class Node
    {
        public:
            Node(const T& data, Node* n = 0)
            {
                element = data;
                next = n;
            }

            T element;
            Node* next;
    };

    /*The top of the stack*/
    Node* top;
};
#include "Stack.C"
#endif

And I have to perform a deep copy in my copy constructor. But what I did was create an temporary array and copy all the elements in the object received by the parameter into the array and then node into the array then push all of them to into the node defined in the Stack class. This is how I did it:

template<class T>
    Stack<T>::Stack(const Stack<T>& other)
    {

        top = NULL;

        if(other.top == NULL)
        {
            this->top=NULL;
        }

        else
        {

            Node* count;
            count= other.top;

            int num=1;

            while(count->next != NULL)
            {
                num++;
                count = count->next;
            }
            cout<<"test"<<endl;



            T arr[num];
            arr[0] = other.top->element;



            Node* count2;
            count2= other.top;

            for(int i = 1 ; i<num; i++)
            {
                arr[i] = count2->next->element;

                count2 = count2->next;
            }

            T temp;
            for(int i =0, j=num-1; i<num/2 ; i++, j--)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }


            for(int i =0; i<num; i++)
            {
                push(arr[i]);
                cout<<arr[i]<<endl;
            }
        }
    }

You can assume that my push(const T& el) and pop() works fine. Can anyone help me perform a deep copy?

Was it helpful?

Solution

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 = &top;
    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:

  1. Assign a copy of the current source node to *pp. This means the pointer addressed by pp will receive the new node address.
  2. Advance pp to hold the address of the next member of the very node it was just assigned. This becomes the next target for the next insertion
  3. 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).

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top