1

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?

7
  • When N is in the array size it is not a good idea to allocate it on stack. The first while loop should be enough to initialize the nodes on the object being constructed.
    – bobah
    Feb 12, 2014 at 7:49
  • You're making it waaaay more complicated here than you should... It could all be done in one while loop, like bobah says. Feb 12, 2014 at 7:52
  • @bobah I put a counter there so that I know what the size of my stack is os that I can use it in my for loops
    – beckinho
    Feb 12, 2014 at 7:53
  • @beckinho - sorry I meant function call stack, not your Stack class. When you allocate a large local array T arr[num] there is a possibility to have call stack overflow.
    – bobah
    Feb 12, 2014 at 7:55
  • 1
    You have no need to count the elements nor copy them to a temporary array... just for (Node* p = other.top; p; p = p->next) push(*p); Feb 12, 2014 at 7:58

1 Answer 1

1

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).

2
  • Thanx for your help. But Im getting errors like: cannot convert stack<int>::Node** to stack<int>::Node* in initialization Node pp = &top..... Invalid user-defined conversion from stack<int>Node to const Stack<int>::Node& *pp=new Node(*p)....and others
    – beckinho
    Feb 12, 2014 at 8:02
  • @beckinho Check the code again. I was missing a * on pp in the initial post.
    – WhozCraig
    Feb 12, 2014 at 8:06

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.