Linked List issue

[andersonwq]

I have this code and it is suppose to add the number to the end of the linked list but it is adding in an extra 0 at the end. How do I fix this?

template<class type>
void stack<type> :: push (type item)
{
        node<type> *t=new node<type>;
        node<type> *trail = new node<type>;
        node<type> *tmp = new node<type>;

        if(head == NULL)
        {
                t->data = item;
                t->next = head;
                head = t;
        }
        t = head;
        while(t != NULL)
        {
                trail = t;
                t = t->next;
        }
                trail->data = item;
                trail->next = tmp;
                tmp->next = t;
}

This is the function.

[coder777]

using a singly linked list for a stack is not a bad idea. It makes things simple:

template<class type>
void stack<type> :: push (type item)
{
        node<type> *t=new node<type>;

        t->data = item;
        t->next = head;
        head = t;
}

template<class type>
type stack<type> :: pop()
{
        type result = type();

        if(head)
        {
                result = head->data
                node<type> *t=head;
                head = head->next;
                delete t;
        }

        return result;
}

I don't know what you mean by 'extra 0'. But that code above should do the job. (not tested though)

[D80DSL3A]

@coder777 What is type() on line 14 where you declare a local instance of type?
It looks like an explicit constructor call but that doesn't make sense.
Hope you don't mind the butt-in!

[coder777]

It looks like an explicit constructor call but that doesn't make sense.

Yes it is an explicit constructor call. And yes it makes sense.

Not all knows that the so calles POD (int and alike) do have constructors which you can only call explicitly. You can write int x = int(); which resolves (for all PODs alike even pointer) to int x = 0;

For a comlex types the requirement is (if you want do use my stack) that the type provides such a constructor. std::vector<int> x = std::vector<int>(); resolves to std::vector<int> x;

It's simply the guarantee that you get an initialized return value.

There's only one problem with it: Since you get always useful data from 'pop' you might end in an endless loop (if you don't check whether the stack is empty())

[D80DSL3A]

Thanks coder777.
It took a couple of days for me to get the time to try it out, but it appears to work (except for missing ; line 18).
I am new to using class templates so this stack example provided a nice problem to experiment with.

This code provides a basis for your function definitions (I substituted T for type as it fits better with my textbooks examples).

template<class T>
class stack
{
private:
	template<class T> struct node
	{
		T data;
		node* next;
	};
	node<T> * head;
public:
	stack(void){ head = NULL; }
	void push(T item);
	T pop();
};

Trying it out on nodes with a simple integer data type:

int main(void)
{
	stack<int> iStack;

	iStack.push(1);
	iStack.push(2);
	iStack.push(3);

	cout << iStack.pop() << " ";// 3
	cout << iStack.pop() << " ";// 2
	cout << iStack.pop() << " ";// 1
	cout << iStack.pop() << " ";// 0 - verifies operation of type() constructor ?
			
	cout << endl;
	return 0;	
}

Two problems:
1) How to distinguish the 0 returned by the 4th call to pop() from a valid data value?

2) If not all nodes are popped then the program would exit with un-deleted nodes (memory leak). A destructor for the stack class could be used to pop() the remaining nodes. Does that seem appropriate?

EDIT: I have verified this simple destructor does the job just fine:

template<class T>
stack<T>::~stack()
{
	while(head)
	{
		pop();
		cout << "Node deleted" << endl;// so I can see what's going on
	}
}

[coder777]

fun2code wrote:

1) How to distinguish the 0 returned by the 4th call to pop() from a valid data value?

Write a functen bool empty() const { return (NULL == head); } that tells if the value of 'pop' is valid or not.

(except for missing ; line 18)

Oops.

A destructor for the stack class could be used to pop() the remaining nodes. Does that seem appropriate?

Yes