help! stack and queue using singly linked list.(linux)

Question

crossbow25 0 Newbie Poster

14 Years Ago

SinglyList.h

#ifndef SINGLYLIST_H
#define SINGLYLIST_H
#include <iostream>
#include <string>
using namespace std;

class Exception
{
private:
	string errMsg;
public:
	Exception(const string& err)
	{ errMsg = err; }
};

class InvalidPositionException : public Exception 
{
public:
	InvalidPositionException(const string& err) : Exception(err){}
};
class EmptyException : public Exception
{
public:
	EmptyException(const string& err) : Exception(err){}
};

template <typename Object> 

class SinglyList
{

protected:
	struct Node
	{
		Object element; 
		Node *next; 
		Node(const Object &e=Object(), Node *n = NULL):element(e),next(n)
		{}
	};
	typedef Node* NodePtr;

public:
	class Position
	{
	private:
		NodePtr node;
	public:
		Position(NodePtr n=NULL)
		{node = n;}
		Object &element() const throw(InvalidPositionException)
		{
			if(node==NULL) throw InvalidPositionException("Null position");
			return node->element;
		}
		bool isNull()const
		{return node==NULL;}
		friend class SinglyList<Object>;
	};
	
protected:
	NodePtr nodePtr(const Position &p) const throw(InvalidPositionException)
	{
		if(p.node==NULL) throw InvalidPositionException("Attempt to use null position");
		else return p.node;
	}

private:
	NodePtr head; 
	NodePtr tail; 
	int sz; 

public:
	SinglyList()
	{head = tail = NULL; sz = 0;}
	int size() const
	{return sz;}
	bool isEmpty() const 
	{return sz==0;}
	Position insertLast(const Object &e)
	{
		NodePtr v=new Node(e,NULL);
		tail->next = v; tail = v; 
		if(head==NULL) 
			head = tail; 
		sz++;
		return Position(tail);
	}
	Position insertFirst(const Object &e)
	{
		NodePtr v= new Node(e,head);
		head = v; 
		if(tail==NULL)
			tail = head; 
		sz++;
		return Position(head);
	}
	void remove(const Position &p) throw(InvalidPositionException) 
	{
		NodePtr v=nodePtr(p),t=head;
		if(!v) throw InvalidPositionException("NULL position");
		if(v == head)
		{
			head = v->next; 
			if(tail == v)
				tail = v->next; 
			sz--;
		}
		else
		{
		while(t&&t->next)
		{
			if(t->next==v)
			{
				t->next = v->next; 
				sz--;
				if(t->next == NULL)
				{	tail = t;} 
				break;
			}
			t = t->next;
		}
		}
		delete v;
		return;
	}
	void print_list()// 출력함수
	{
		NodePtr printNode = head;
		while(printNode != NULL)
		{
			cout << printNode->element << "    ";
			printNode = printNode->next; 
		}
	}
	Position before(const Position& p) const throw(InvalidPositionException) 
	{
		NodePtr v = nodePtr(p), t=head;
		if(v==t)
			throw InvalidPositionException("Advance past beginning of list");
		while(v!=t->next)
		{
			t = t->next;
		}
		return Position(t);
	}
	Position after(const Position& p) const throw(InvalidPositionException)
	{
		NodePtr v = nodePtr(p), next = v->next;
		if(next==tail)
			throw InvalidPositionException("Advance past ending of list");
		return Position(next);
	}
	void replaceElement(const Position& p, const Object& e) throw(InvalidPositionException)
	{
		NodePtr v = nodePtr(p); 
		v->element = e; 
	}
	void swapElements(const Position& p,const Position& q) throw(InvalidPositionException)
	{
		NodePtr v=nodePtr(p);
		NodePtr t=nodePtr(q);
		Object temp;
		temp= t->element;
		t->element = v->element;
		v->element = temp;//swap
	}
	Position insertBefore(const Position& p, const Object &e) throw(InvalidPositionException)
	{
		NodePtr v = nodePtr(p), t=head;
		sz++;
		if(v != t) 
		{
		while(v != t->next)
		{
			t = t->next;
		}
		
		
		NodePtr newNode = new Node(e,v);
		t->next = newNode;
		return Position(newNode);
		}
		sz--;
		insertFirst(e);
	}
	Position insertAfter(const Position& p, const Object &e) throw(InvalidPositionException)
	{
		NodePtr v = nodePtr(p), next = v->next; 
		sz++;
		NodePtr newNode = new Node(e,next);
		v->next = newNode;
		return Position(newNode); 

	Position first() const throw(EmptyException)
	{
		if(isEmpty()) throw EmptyException("Empty list!");
		return Position(head);
	}
	Position last() const throw(EmptyException)
	{
		if(isEmpty()) throw EmptyException("Empty list");
		return Position(tail);
	}

};

#endif

Tstack.h

#include"SinglyList.h" 

template <typename Object>

class Tstack
{
private:

	SinglyList<Object> S; 

public:
	
	void push(const Object e)
	{
		S.insertFirst(e); 
	}

	Object pop() 
	{
		SinglyList<Object>::Position v = S.first(); 
		Object t; 
		t = v.element(); 
		S.remove(v); 
		return t; 
	}

	Object top() 
	{
		SinglyList<Object>::Position v = S.first(); 
		return v.element(); 
	}

	int stack_size()
	{
		return S.size(); 
	}
};

Tqueue.h

#include"SinglyList.h"  

template <typename Object>

class Tqueue
{
private:

	SinglyList<Object> S;

public:
	
	void Enqueue(const Object e) 
	{
		S.insertFirst(e); 
	}

	Object Dequeue() 
	{
		SinglyList<Object>::Position v = S.last();
		Object t;
		t = v.element(); 
		S.remove(v);
		return t;
	}

	Object Front() 
	{
		SinglyList<Object>::Position v = S.last();
		return v.element();
	}

	int queue_size()
	{
		return S.size(); 
	}
};

main.cpp

#include <iomanip>
#include "SinglyList.h" 
#include "Tstack.h"		
#include "Tqueue.h"		

int select_type();		
void type_int();		
void type_double();		
void type_char();		

void main()
{
	int sw;
	sw = select_type();
	switch (sw)
	{
	case 1:
		type_int();
		break;
	
	case 2:
		type_double();
     	break;

	case 3:
		type_char();
		break;

	default:
		break;
	}
}

//function body

//type select
int select_type()
{
	int x;
	cout << "select struct type (1: int, 2: double, 3: char - )";
	cin >> x;
	return x;
}

//integer
void type_int()
{
	// template class
	Tstack<int> test;
	int i, n, x;
	cout << "\n---- stack ----" << endl;
	cout << "input the number of value : ";
	cin >> n;
	for (i = 0; i < n; i++ )
	{
		cout << "input the integer type value : ";
		cin >> x;
		test.push(x); 
	}
	
	cout << "\nsize of stack : " << test.stack_size() << endl; 

	cout << "Top of stack : " << test.top() << endl;	

	cout << "\npop the element from stack" << endl;
	for (i = 0; i < n; i++ )
	{
		cout << setw(4) << test.pop();	
	}
	cout << endl;
	
	
	Tqueue<int> temp;
	cout << "\n---- queue ----" << endl;
	for(i = 0; i < n; i++ )
	{	
		cout << "input the integer type value : ";
		cin >> x;
		temp.Enqueue(x);		
	}
	
	cout << "\nsize of queue : " << temp.queue_size() << endl;	

	cout << "front of queue : " << temp.Front() << endl;	
	cout << "\ndequeue the element from queue" << endl;		
	for(i = 0; i < n; i++ )
	{
		cout << setw(4) << temp.Dequeue();
	}
	cout << endl;
}

//double
void type_double()
{
	Tstack<double> test;
	int i;
	
	double x;
	cout << "\n---- stack ----" << endl;
	for (i = 1; i < 10; i++ )
	{
		cout << "input the double type value : ";
		cin >> x;
		test.push(x);
	}
	cout << "\npop the element from stack" << endl;
	for (i = 1; i < 10; i++ )
	{
		cout << setw(8) << test.pop();
	}
	
	cout << "\n---- queue ----" << endl;	
	Tqueue<double> temp;
	for(i = 1; i < 10; i++ )
	{
		cout << "input the double type value : ";
		cin >> x;
		temp.Enqueue(x);
	}
	
	cout << "\ndequeue the element from queue" << endl;
	for(i = 1; i < 10; i++ )
	{
		cout << setw(8) << temp.Dequeue();
	}
	cout << endl;
}

//char
void type_char()
{
	Tstack<char> test;
	int i;
	
	char x;
	cout << "\n---- stack ----" << endl;
	for (i = 1; i < 10; i++ )
	{
		cout << "input the char type value : ";
		cin >> x;
		test.push(x);
	}
	cout << "\npop the element from stack" << endl;
	for (i = 1; i < 10; i++ )
	{
		cout << setw(4) << test.pop();
	}
	
	cout << "\n---- queue ----" << endl;	
	Tqueue<char> temp;
	for(i = 1; i < 10; i++ )
	{
		cout << "input the char type value : ";
		cin >> x;
		temp.Enqueue(x);
	}
	
	cout << "\ndequeue the element from queue" << endl;
	for(i = 1; i < 10; i++ )
	{
		cout << setw(4) << temp.Dequeue();
	}
	cout << endl;
}

Tstack.h: In member function ‘Object Tstack<Object>::pop()’:
Tstack.h:20: error: expected ‘;’ before ‘v’
Tstack.h:22: error: ‘v’ was not declared in this scope
Tstack.h: In member function ‘Object Tstack<Object>::top()’:
Tstack.h:29: error: expected ‘;’ before ‘v’
Tstack.h:30: error: ‘v’ was not declared in this scope
Tqueue.h: In member function ‘Object Tqueue<Object>::Dequeue()’:
Tqueue.h:20: error: expected ‘;’ before ‘v’
Tqueue.h:22: error: ‘v’ was not declared in this scope
Tqueue.h: In member function ‘Object Tqueue<Object>::Front()’:
Tqueue.h:29: error: expected ‘;’ before ‘v’
Tqueue.h:30: error: ‘v’ was not declared in this scope
In file included from main.cpp:3:
Tstack.h: In member function ‘Object Tstack<Object>::pop()’:
Tstack.h:20: error: expected ‘;’ before ‘v’
In file included from main.cpp:3:
Tstack.h:22: error: ‘v’ was not declared in this scope
Tstack.h: In member function ‘Object Tstack<Object>::top()’:
Tstack.h:29: error: expected ‘;’ before ‘v’
Tstack.h:30: error: ‘v’ was not declared in this scope
In file included from main.cpp:4:
Tqueue.h: In member function ‘Object Tqueue<Object>::Dequeue()’:
Tqueue.h:20: error: expected ‘;’ before ‘v’
In file included from main.cpp:4:
Tqueue.h:22: error: ‘v’ was not declared in this scope
Tqueue.h: In member function ‘Object Tqueue<Object>::Front()’:
Tqueue.h:29: error: expected ‘;’ before ‘v’
Tqueue.h:30: error: ‘v’ was not declared in this scope
In file included from main.cpp:3:
Tstack.h: In member function ‘Object Tstack<Object>::top() [with Object = int]’:
main.cpp:64:   instantiated from here
Tstack.h:29: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tstack.h:29: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:3:
Tstack.h: In member function ‘Object Tstack<Object>::pop() [with Object = int]’:
main.cpp:69:   instantiated from here
Tstack.h:20: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tstack.h:20: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:4:
Tqueue.h: In member function ‘Object Tqueue<Object>::Front() [with Object = int]’:
main.cpp:85:   instantiated from here
Tqueue.h:29: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tqueue.h:29: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:4:
Tqueue.h: In member function ‘Object Tqueue<Object>::Dequeue() [with Object = int]’:
main.cpp:90:   instantiated from here
Tqueue.h:20: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tqueue.h:20: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:3:
Tstack.h: In member function ‘Object Tstack<Object>::pop() [with Object = double]’:
main.cpp:112:   instantiated from here
Tstack.h:20: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tstack.h:20: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:4:
Tqueue.h: In member function ‘Object Tqueue<Object>::Dequeue() [with Object = double]’:
main.cpp:127:   instantiated from here
Tqueue.h:20: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tqueue.h:20: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:3:
Tstack.h: In member function ‘Object Tstack<Object>::pop() [with Object = char]’:
main.cpp:149:   instantiated from here
Tstack.h:20: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tstack.h:20: note: say ‘typename SinglyList::Position’ if a type is meant
In file included from main.cpp:4:
Tqueue.h: In member function ‘Object Tqueue<Object>::Dequeue() [with Object = char]’:
main.cpp:164:   instantiated from here
Tqueue.h:20: error: dependent-name ‘SinglyList::Position’ is parsed as a non-type, but instantiation yields a type
Tqueue.h:20: note: say ‘typename SinglyList::Position’ if a type is meant

This code is Stack and Queue using SinglyList class
it works well in visual c++
but does not work in linux(Ubunto)
i entered "g++ -o main SinglyList.h Tstack.h Tqueue.h main.cpp
I have tried to find error point.
but I don't know.
linux is difficult to me.
what can i do for sucessfull program?
tell me. T^T
thanks.

c++ queue

Edited 14 Years Ago by crossbow25 because: n/a

2 Contributors
2 Replies
258 Views
10 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by crossbow25

StuXYZ 731 Practically a Master Poster

14 Years Ago

Ok, first off, I REALLY hope this doesn't compile on VC++ because if it does then VC++ is adding a bracket
In addition to not compiling to the standard.

So what did you do wrong:

You missed a } at the end of insertAfter in SinglyList.h.

[The clue is that all the errors are in the same object, regardless of the fact that they should be in different ones]

Second: You are required to change to this

typename SinglyList<Object>::Position v = S.first();

The standard say that this causes the name to be treated as a type, and it also says that without the typename, it is treated as a non-type EVEN if this leads to a syntax error.

Thus add the typename directive. [You have about 4 places to do that, I think]

Edited 14 Years Ago by StuXYZ because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

crossbow25 0 Newbie Poster · Answer 1 · 2010-10-09T15:22:00+00:00

thanks! thank you, StuXYZ!
you're genius and good programer.
it works well.
thank you for your advices!