Dumping singly linked list into 2 stacks.

Hello. I need to figure out how to dump the contents of my singly linked list into 2 stacks (one for men, one for women). I have my singly-linked list, arranged from highest contribution to the lowest, but they need to be placed into 2 separate stacks. Any hints would be appreciated.

main.cpp

Code:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <stack>
using namespace std;

#include "sllist.h"
#include "contributornode.h"
#include "contributor.h"

int main()
{
	double Con,ID=0;
	short Sex,tmp = 0;
	SLLIST GuestList;
	
	Contributor c,x;
				
	stack <Contributor> Men;
	stack <Contributor> Women;
	stack <Contributor> Left;
	stack <Contributor> Right;
		
	srand(time(0));
	for(int j=0; j < 10; j++)
	{
		Con = rand() % 1000 + 1;
		Sex = rand() % 10 + 1;
		if (Sex > 4)
			GuestList.insert(Contributor("Gentleman Contrib",male,Con,ID));
		else
			GuestList.insert(Contributor("Lady Contrib",female,Con,ID));
	}
	
	// debug
	//cout << GuestList << endl;
	// dump items in 2 stacks
	
	while (tmp < GuestList.getSizeOfList()) // traverse through list
	{	
		if (GuestList.DumpIntoStack(tmp) == 0)
		{
			Men.push(c); // **** WHAT DO I PUT HERE? ****
			tmp++;
			continue;
		}
		if (GuestList.DumpIntoStack(tmp) == 1)
		{
			Women.push(c); // **** AND HERE - WHAT DO I PUT HERE? ****
			tmp++;
			continue;
		}
		if (GuestList.DumpIntoStack(tmp) < 0 || GuestList.DumpIntoStack(tmp) > 1)
		{
			cerr << "Program terminated - Abnormal number." << endl;
			exit(1);
		}
	}
	
	// Pop the contributors off the stack and display them.
	while (!Men.empty())
	{
		c = Men.top();
		Men.pop();
		cout << c << endl;
	}
	return 0;
}

Contributor.cpp:

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
using namespace std;

#include "Contributor.h"

Contributor::Contributor()
{
	Contribution = 0.00;
	Name = "Blank";
	Gender = unknown;
	IDKey = 0;
}
Contributor::Contributor(string name,Gender_type g,double contribution,int idkey)
{
	Contribution = contribution;
	Gender = g;
	IDKey = idkey;
	Name = name;
}
Contributor::Contributor(const Contributor &c)
{
	Contribution = c.Contribution;
	Gender = c.Gender;
	IDKey = c.IDKey;
	Name = c.Name;
}

Contributor::~Contributor () 
{}

ostream & operator<< (ostream &out, const Contributor &c)
{
	string temp;
	if (c.Gender == male)
		temp = "male";
	if (c.Gender == female)
		temp = "female";
	if (c.Gender == unknown)
		temp = "unknown";
	out << "Name = " << c.Name << " | Gender = " << temp << " | Contribution = $" << c.Contribution << ".00" << " | IDKey = " << c.IDKey;
	//out << "-------------------------------------------------------------------------" ;
	return out;
}

istream & operator>> (istream &in, Contributor &r)
{
	string temp;
	cout << "Enter a name (no spaces): ";
	in >> r.Name;
	cout << "Enter gender (male, female, unknown): ";
	in >> temp;
	if (temp == "male")
		r.Gender = male;
	if (temp == "female")
		r.Gender = female;
	if (temp == "unknown")
		r.Gender = unknown;
	if (temp != "unknown" && temp != "male" && temp != "female")
		r.Gender = unknown;
	cout << "Enter a contribution: ";
	in >> r.Contribution;
	cout << "Enter an ID Key: ";
	in >> r.IDKey;
	return in;
}

const Contributor & Contributor::operator= (const Contributor &rhs)
{
	if (this != &rhs)
	{
		Contribution = rhs.Contribution;
		Name = rhs.Name;
		Gender = rhs.Gender;
		IDKey = rhs.IDKey;
	}
	return *this;
}

bool Contributor::operator< (const Contributor &rhs) const
{
	return (Contribution < rhs.Contribution);
}
bool Contributor::operator> (const Contributor &rhs) const
{
	return (Contribution > rhs.Contribution);
}
bool Contributor::operator>= (const Contributor &rhs) const
{
	return (Contribution >= rhs.Contribution);
}
bool Contributor::operator== (const Contributor &rhs) const
{
	return (Name == rhs.Name);
}
bool Contributor::operator!= (const Contributor &rhs) const
{
	return (Name != rhs.Name);
}

Contributor.h:

Code:

#ifndef CONTRIBUTOR_H
#define CONTRIBUTOR_H

enum Gender_type {male,female,unknown};

class Contributor
{
public:
	Contributor();
	Contributor(string,Gender_type,double,int);
	Contributor(const Contributor &);
	~Contributor ();

	friend ostream & operator<< (ostream &, const Contributor &);
	friend istream & operator>> (istream &, Contributor &);

	const Contributor & operator= (const Contributor &);
	
	//accessor functions
	string getName(){return Name;}
	double getContribution(){return Contribution;}
	int getIDKey(){return IDKey;}
	Gender_type getGender(){return Gender;}

	bool operator< (const Contributor &) const;
	bool operator> (const Contributor &) const;
	bool operator>= (const Contributor &) const;
	bool operator== (const Contributor &) const;
	bool operator!= (const Contributor &) const;

private:
	string Name;
	double Contribution;
	int IDKey;
	Gender_type Gender;
};

#endif

SLLIST.cpp:

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;

#include "SLList.h"
#include "contributornode.h"
#include "contributor.h"

SLLIST::SLLIST(const SLLIST &rhs)
{
	head = rhs.head;
}

const SLLIST & SLLIST::operator= (const SLLIST &rhs)
{
	if (this != &rhs)
		head = rhs.head;
	return *this;
}

ostream & operator<< (ostream &o, const SLLIST &rhs)
{
	ContributorNode *p;
	p = rhs.head;
    while (p != 0)
	{
		o << p->contributor << endl; 
		p = p->next;
	}
	return o;
}

void SLLIST::FreeList() 
{
	ContributorNode *p;
	while (head != 0)
	{
		p = head;
		head = head->next;
		delete p;
	}
}

void SLLIST::insert(const Contributor &cont)
{
	ContributorNode *p,*tmp;
	if (head == 0)
	{
		head = new ContributorNode(cont,0);
		return;
	}
		p = head;
		tmp = head;
		while (p != 0)
		{
			if (p->contributor > cont)
			{
				tmp = p;
				p = p->next;
			}
			else
			{
				if (p == head)
					head = new ContributorNode(cont,head); // beginning
				else
					tmp->next = new ContributorNode(cont,p); // middle
				return;
			}
		}
		tmp->next = new ContributorNode(cont,0); // end
}

void SLLIST::remove(const Contributor &cont)
{
	ContributorNode *p,*tmp;
	p = head;
	tmp = head;
	if (head == 0)
	{
		cerr << "ERROR: No items to remove in list." << endl;
		return;
	}
	while (p != 0) 
	{
		if (p->contributor == cont) 
		{
			if (p == head)
			{
				head = p ->next;
				delete p;
				return;
			}
			else
			{
				tmp->next = p->next;
				delete p;
				return;
			}
		}
	tmp = p;
	p = p->next;
	}
	return;
}

int SLLIST::DumpIntoStack(short tmp)
{
	if (tmp > getSizeOfList() || tmp < 0)
		return -1;
	ContributorNode *p;
	p = head;
	short a = 0;
	while (a < tmp)
	{
		p = p->next;
		a++;
	}
	if (p->contributor.getGender() == male)
		return 0;
	if (p->contributor.getGender() == female)
		return 1;
	if (p->contributor.getGender() == unknown)
		return -1;
	return 2;
}

short SLLIST::getSizeOfList() const
{
	short a = 0;
	ContributorNode *p;
	p = head;
	while (p != 0) 
	{
		p = p->next;
		a++;
	}
	return a;
}

SLLIST.h:

Code:

#ifndef SLLIST_H
#define SLLIST_H
#include "ContributorNode.h"

class SLLIST 
{
public:
	SLLIST(){head = 0;} 
	SLLIST(const SLLIST &); 
	~SLLIST(){FreeList();} 

	const SLLIST & operator= (const SLLIST &);
	friend ostream & operator<< (ostream &o, const SLLIST &);
	void FreeList();
	void insert(const Contributor &cont);
	void remove(const Contributor &cont);
	int DumpIntoStack(short);
	short getSizeOfList() const;

private:
	ContributorNode *head;
};

#endif

ContributorNode.h:

Code:

#ifndef CNODE_H
#define CNODE_H
#include "contributor.h"

class ContributorNode
{
public:
	Contributor contributor;
	ContributorNode *next;
	ContributorNode(const Contributor &cont,ContributorNode *ptr=0){contributor = cont;next = ptr;}
};

#endif

Your DumpIntoStack function doesn't really seem to do what its name indicates... I don't really see a use for that function at all. That aside, you need a function that returns the Contributor object stored at a given location/index within the list (call it GetContributor or something). Store this into your c or x variables and have a GetSex member function for your Contributor objects so you can do something like:

Code:

while (tmp < GuestList.getSizeOfList()) // traverse through list
{
    c = GuestList.GetContributor(tmp++);
    if (c.GetSex() == 0) Men.push(c);
    else if (c.GetSex() == 1) Women.push(c);
    else
    {
        cerr << "Program terminated - Abnormal number." << endl;
        exit(1);
    }
}

Thanks for your reply. I am not sure if I'm having an off day or if my brain isn't full comprehending what you're saying, but I am having some difficulty with taking your suggestions and running with it. Could you please provide some more hints or code examples?

It would be greatly appreciated.

strotee76

I don't see what's so complicated. Maybe looking at the rest of the code is scrambling your brains? j/k Well, basically you loop through each node in the list; and if the node belongs to a man, then push it onto the Men stack; and if it belongs to a woman, then push it onto the Women stack...

What is the whole purpose of having a separate list container and then two stacks? Is it simply so that you can sort them in the list (highest to lowest) and then have the information that ends up in your stacks be in lowest (top) to highest order? Is that sorting the only reason you even have the list? Do you really need to use stacks? If all you need to do is display contributors in lowest to highest order based on contribution, you might be able to just simply use a couple of multiset containers to store all of this information in lowest to highest order by contribution, then you don't need any of the list related code at all:

Code:

#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

#include "contributor.h"

int main()
{
    double Con,ID=0;
    short Sex;
	
    multiset <Contributor> Men;
    multiset <Contributor> Women;

    srand(time(0));
    for(int j=0; j < 10; j++)
    {
        Con = rand() % 1000 + 1;
        Sex = rand() % 10 + 1;

        // Insert into proper Men/Women multiset based on Sex value.
        // Objects in multiset will automatically be sorted from lowest
        // to highest contribution value because of less than operator
        // you have already defined for Contributor objects

        if (Sex > 4)
            Men.insert(Contributor("Gentleman Contrib",male,Con,ID));
        else
            Women.insert(Contributor("Lady Contrib",female,Con,ID));
    }

    // Output men contributors in lowest to highest order.

    copy(Men.begin(),Men.end(),ostream_iterator<Contributor>(cout,"\n"));

    // Do same thing for women?

    copy(Women.begin(),Women.end(),ostream_iterator<Contributor>(cout,"\n"));


    return 0;

}

That should be all the code you need... just your main.cpp and your contributor.h and contributor.cpp. Some sample output from one of my runs...

Code:

Name = Gentleman Contrib | Gender = male | Contribution = $142.00 | IDKey = 0
Name = Gentleman Contrib | Gender = male | Contribution = $308.00 | IDKey = 0
Name = Gentleman Contrib | Gender = male | Contribution = $461.00 | IDKey = 0
Name = Gentleman Contrib | Gender = male | Contribution = $584.00 | IDKey = 0
Name = Gentleman Contrib | Gender = male | Contribution = $632.00 | IDKey = 0
Name = Gentleman Contrib | Gender = male | Contribution = $745.00 | IDKey = 0
Name = Lady Contrib | Gender = female | Contribution = $275.00 | IDKey = 0
Name = Lady Contrib | Gender = female | Contribution = $388.00 | IDKey = 0
Name = Lady Contrib | Gender = female | Contribution = $646.00 | IDKey = 0
Name = Lady Contrib | Gender = female | Contribution = $897.00 | IDKey = 0

Thanks.

I resolved the issue with a little sleep and a clear head. Your original suggestions did make sense. I looked at this thread again for the first time since last Wed-Thur.


Thanks again,
strotee76