1.3.2 動的確保のスタック・キューへの適用

//dynamic_stack
#include <iostream>

template <class T> class stack{
	class set_of_datum{
	private:
		T value;
		set_of_datum *next;
	public:
		set_of_datum(T value){
			this->value = value;
			next = NULL;
		}
		void set_next(set_of_datum *next){
			this->next = next;
		}
		set_of_datum *get_next(){return next;}
		T get_value(){return value;}
	};
private:
	set_of_datum *data; //スタックの本体
public:
	stack(); //コンストラクタ
	~stack(); //デストラクタ
	void clear(); //スタックの中身を空にする
	void push(T obj); //スタックにobjを追加する
	T pop(); //スタックからobjを取り出す
	void show(); //スタックの中身を見せる
	int get_data_num(); //スタックデータの数を返す
};

template <class T> stack<T>::stack(){
	data = NULL;
}

template <class T> stack<T>::~stack(){
	clear();
}

template <class T> void stack<T>::clear(){
	while(data != NULL){
		set_of_datum *target = data; //delete対象
		data = (*data).get_next();
		delete target;
	}
}

template <class T> void stack<T>::push(T obj){
	set_of_datum *new_datum = new set_of_datum(obj);
	(*new_datum).set_next(data);
	data = new_datum;
}

template <class T> T stack<T>::pop(){
	T dummy; //error発生時に返すダミーデータ
	if(data != NULL){
		T value = (*data).get_value();
		set_of_datum *target = data; //delete対象
		data = (*data).get_next();
		delete target;
		return value;
	}
	else{
		std::cout << "error: this stack is EMPTY! -- in stack<T>::pop()" << std::endl;
		return dummy;
	}
}

template <class T> void stack<T>::show(){
	set_of_datum *ptr = data; //表示するデータ
	for(int i=0; ptr!=NULL; i++){
		std::cout << i << ":" << (*ptr).get_value() << std::endl;
		ptr = (*ptr).get_next();
	}
}

template <class T> int stack<T>::get_data_num(){
	int value = 0;
	set_of_datum *ptr = data;
	while(ptr != NULL){
		value ++;
		ptr = (*ptr).get_next();
	}
	return value;
}

まぁ、こんなものだろう。
同様に、キューも。

//dynamic_queue
#include <iostream>

template <class T> class queue{
	class set_of_datum{
	private:
		T value;
		set_of_datum *before;
		set_of_datum *next;
	public:
		set_of_datum(T value){
			this->value = value;
			before = NULL;
			next = NULL;
		}
		void set_before(set_of_datum *before){
			this->before = before;
		}
		void set_next(set_of_datum *next){
			this->next = next;
		}
		set_of_datum *get_before(){return before;}
		set_of_datum *get_next(){return next;}
		T get_value(){return value;}
	};
private:
	set_of_datum *data; //キューの本体(先頭)
	set_of_datum *pop_target; //キューの本体(末尾)
public:
	queue(); //コンストラクタ
	~queue(); //デストラクタ
	void clear(); //キューの中身を空にする
	void enqueue(T obj); //キューにobjを追加する
	T dequeue(); //キューからobjを取り出す
	void show(); //キューの中身を見せる
	int get_data_num(); //キューのサイズを返す
};

template <class T> queue<T>::queue(){
	data = NULL;
	pop_target = NULL;
}

template <class T> queue<T>::~queue(){
	clear();
}

template <class T> void queue<T>::clear(){
	while(data != NULL){
		set_of_datum *target = data; //delete対象
		data = (*data).get_next();
		delete target;
	}
}

template <class T> void queue<T>::enqueue(T obj){
	set_of_datum *new_datum = new set_of_datum(obj);
	if(get_data_num() == 0)	pop_target = new_datum;
	else{
		(*new_datum).set_next(data);
		(*data).set_before(new_datum);
	}
	data = new_datum;
}

template <class T> T queue<T>::dequeue(){
	T dummy; //error発生時に返すダミーデータ
	if(data != NULL){
		T value = (*pop_target).get_value();
		set_of_datum *target = pop_target; //delete対象
		if(data == target)	data = NULL;
		else	(*(*target).get_before()).set_next(NULL);
		pop_target = (*target).get_before();
		delete target;
		return value;
	}
	else{
		std::cout << "This queue is EMPTY! -- error in queue<T>::pop()" << std::endl;
		return dummy;
	}
}

template <class T> void queue<T>::show(){
	set_of_datum *ptr = data;
	for(int i=0; ptr!=NULL; i++){
		std::cout << i << ":" << (*ptr).get_value() << std::endl;
		ptr = (*ptr).get_next();
	}
}

template <class T> int queue<T>::get_data_num(){
	int value = 0;
	set_of_datum *ptr = data;
	while(ptr != NULL){
		value++;
		ptr = (*ptr).get_next();
	}
	return value;
}

queue< T >::dequeue()のif文の中身が若干汚いけど、他に書き方はあるのだろうか。