テンプレートクラスのカプセル化(2)——順序スタックと連鎖スタック

C++ 言語、連結スタックの実装

実験内容：

プログラミングでスタックの以下の機能を実装する：
（1）長さ n の順序スタックを作成し、要素の型は自由に定義し、スタック内の各要素の値を出力する。
（2）データ要素 e をスタックに入れ、スタックに入れた後の順序スタック内の各要素の値を出力する。
（3）順序スタックのスタックトップ要素をスタックから取り出し、取り出した要素の値と取り出した後の順序スタック内の各要素の値を出力する。

プログラミングでキューの以下の機能を実装する：
（1）長さ n の循環キューを作成し、要素の型は自由に定義し、キュー内の各要素の値を出力する。
（2）データ要素 e をキューに入れ、キューに入れた後のキュー内の各要素の値を出力する。
（3）循環キューのキュー先頭要素を取り出し、取り出した要素の値と取り出した後のキュー内の各要素の値を出力する。

プログラミングで連結スタックの以下の機能を実装する
長さ n の連結スタックを作成し、要素の型は自由に定義し、スタックの初期化、プッシュ、ポップなどの典型的な操作を実装する。

全体として、まずは順序スタックと連結スタックの基本操作を実装する：プッシュ操作（Push）、ポップ操作（Pop）、スタックトップ要素の取得（Top）、スタックが空かどうかの判断（IsEmpty）、スタックが満杯かどうかの判断（IsFull）、スタック内の要素数の取得（Size）、スタック内のすべての要素の表示（PrintStack）、スタック内のすべての要素をクリアする（Clear）。次に、キューの基本操作を実装する：エンキュー操作（Push）、デキュー操作（Pop）、キュー先頭要素の取得（Front）、キューが空かどうかの判断（IsEmpty）、キューが満杯かどうかの判断（IsFull）、キュー内の要素数の取得（Size）、キュー内のすべての要素の表示（PrintQueue）、キュー内のすべての要素をクリアする（Clear）。引き続きテンプレートクラスをカプセル化する。初期化と破棄操作はコンストラクタとデストラクタで実装する。
@TOC

順序スタック#

順序スタック操作クラス定義#

//順序スタック定義
template <class T> class myStack1 {
private:
	int MaxSize;  //スタック容量
	T* Data;	  //データ
	int top;  //スタックトップ要素を記録、スタックトップ要素のインデックスの次のインデックス、空の時はtopは0
public:
	myStack1(int maxsize = 100);  //コンストラクタ スペースを割り当てる
	~myStack1();				   //デストラクタ スペースを回収する
	void PrintStack();		   //順序スタック内のすべての要素を表示する
	void Push(T data);	//プッシュ操作、top値を1増やし、要素itemをスタックトップに保存する
	T Pop();			//ポップ操作、要素を取り出して返す、Top値を1減らす
	T Top();			//スタックトップ要素を取得する、取り出さない
	int Size();			//スタック内の要素数を取得する
	bool IsEmpty();		//スタックが空かどうかを判断する
	bool IsFull();		//スタックが満杯かどうかを判断する
};

主要操作#

(1) コンストラクタとデストラクタ#

template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
	Data = new T[maxsize];
};
template <class T> myStack1<T>::~myStack1() {
	if (Data)
		delete[] Data;
}

(2) スタックが空か満杯かの判断#

//スタックが空かどうかを判断する
template <class T> bool myStack1<T>::IsEmpty() {
	return top == 0;
}
//スタックが満杯かどうかを判断する
template <class T> bool myStack1<T>::IsFull() {
	return top == MaxSize;
}

(3) プッシュ操作#

要素 data をスタックトップに保存し、Top 値を 1 増やす

template <class T> void myStack1<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:プッシュに失敗しました、スタックは満杯です！" << endl;
	} else {
		Data[top++] = data;
	}
}

(4) スタックトップ要素の取得#

スタックトップ要素を取得し、取り出さない

template <class T> T myStack1<T>::Top() {
	if (IsEmpty()) {
		cout << "error:トップは存在しません、スタックは空です！" << endl;
		return error;  // ERRORはT型の特別な値
	} else {
		return Data[top - 1];
	}
}

(5) スタック内の要素数の取得#

template <class T> int myStack1<T>::Size() {
	return top;
}

(6) ポップ操作#

スタックトップ要素を取り出し、Top 値を 1 減らす

template <class T> T myStack1<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:ポップに失敗しました、スタックは空です！" << endl;
		return error;  // ERRORはT型の特別な値
	} else {
		T temp = Data[--top];
		return temp;
	}
}

(7) 順序スタック内のすべての要素を表示する#

template <class T> void myStack1<T>::PrintStack() {
	if (IsEmpty())
		cout << "このスタックは空です！" << endl;
	for (int i = 0; i < top; ++i) {
		cout << "第 " << i + 1 << " データは:";
		cout << Data[i] << endl;
	}
	cout << "スタックには合計で " << top << " 要素があります。" << endl;
}

完全なコード#

//順序スタック
#include <bits/stdc++.h>
#define error -1
using namespace std;
//順序スタック定義
template <class T> class myStack1 {
private:
	int MaxSize;  //スタック容量
	T* Data;	  //データ
	int top;  //スタックトップ要素を記録、スタックトップ要素のインデックスの次のインデックス、空の時はtopは0
public:
	myStack1(int maxsize = 100);  //コンストラクタ スペースを割り当てる
	~myStack1();				   //デストラクタ スペースを回収する
	void PrintStack();		   //順序スタック内のすべての要素を表示する
	void Push(T data);	//プッシュ操作、top値を1増やし、要素itemをスタックトップに保存する
	T Pop();			//ポップ操作、要素を取り出して返す、Top値を1減らす
	T Top();			//スタックトップ要素を取得する、取り出さない
	int Size();			//スタック内の要素数を取得する
	bool IsEmpty();		//スタックが空かどうかを判断する
	bool IsFull();		//スタックが満杯かどうかを判断する
};

//順序スタック操作クラス実装
//コンストラクタ スペースを割り当てる
template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
	Data = new T[maxsize];
};
//デストラクタ スペースを解放する
template <class T> myStack1<T>::~myStack1() {
	if (Data)
		delete[] Data;
}
//(1) スタックが空かどうかを判断する
template <class T> bool myStack1<T>::IsEmpty() {
	return top == 0;
}
//(2) スタックが満杯かどうかを判断する
template <class T> bool myStack1<T>::IsFull() {
	return top == MaxSize;
}
//(3) プッシュ操作
// 要素dataをスタックトップに保存し、Top値を1増やす
template <class T> void myStack1<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:プッシュに失敗しました、スタックは満杯です！" << endl;
	}
	else {
		Data[top++] = data;
	}
}
//(4) スタックトップ要素を取得する、取り出さない
template <class T> T myStack1<T>::Top() {
	if (IsEmpty()) {
		cout << "error:トップは存在しません、スタックは空です！" << endl;
		return error;  // ERRORはT型の特別な値
	}
	else {
		return Data[top - 1];
	}
}
//(5) スタック内の要素数を取得する
template <class T> int myStack1<T>::Size() {
	return top;
}
//(6) ポップ操作
// スタックトップ要素を取り出し、Top値を1減らす
template <class T> T myStack1<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:ポップに失敗しました、スタックは空です！" << endl;
		return error;  // ERRORはT型の特別な値
	}
	else {
		T temp = Data[--top];
		return temp;
	}
}
//(7) 順序スタック内のすべての要素を表示する
template <class T> void myStack1<T>::PrintStack() {
	if (IsEmpty())
		cout << "このスタックは空です！" << endl;
	for (int i = 0; i < top; ++i) {
		cout << "第 " << i + 1 << " データは:";
		cout << Data[i] << endl;
	}
	cout << "スタックには合計で " << top << " 要素があります。" << endl;
}
//メイン関数で呼び出される関数 (テスト用)
template <class T> void Stack_Push(myStack1<T>& S) {
	T data;
	cout << "スタックに入れる要素を入力してください:";
	cin >> data;
	S.Push(data);
	cout << "------------- プッシュ後、スタック S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Pop(myStack1<T>& S) {
	T data = S.Pop();
	if (data != error) {
		cout << "取り出した要素は:";
		cout << data << endl;
	}
	cout << "------------- ポップ後、スタック S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Top(myStack1<T>& S) {
	T data = S.Top();
	if (data != error) {
		cout << "スタックトップ要素は:";
		cout << data << endl;
	}
}
template <class T> void Stack_Size(myStack1<T>& S) {
	cout << "このスタック内の要素数は:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(myStack1<T>& S) {
	cout << "---------------------- スタック S --------------------" << endl;
	S.PrintStack();
}
int main() {
	int n;
	cout << "nを入力し、長さnの順序スタックを作成します:";
	cin >> n;
	myStack1<int> S(n);
	cout << "n個の要素を入力してください:" << endl;
	for (int i = 0; i < n; ++i) {
		int data;
		cin >> data;
		S.Push(data);
	}
	cout << "1 プッシュ操作" << endl;
	cout << "2 ポップ操作" << endl;
	cout << "3 スタックトップ要素の取得" << endl;
	cout << "4 スタック内の要素数の取得" << endl;
	cout << "5 順序スタック内のすべての要素を出力" << endl;
	cout << "6 終了" << endl;
	while (1) {
		int choice;
		cout << "メニュー選択:";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: Stack_Push(S); break;
			case 2: Stack_Pop(S); break;
			case 3: Stack_Top(S); break;
			case 4: Stack_Size(S); break;
			case 5: Stack_PrintStack(S); break;
			case 6: break;
			default: cout << "入力エラー、再入力してください";
		}
		if (choice == 6)
			exit(0);
		cout << "Enterキーを押して続行…" << endl;
		getchar();
	};
	return 0;
}

連結スタック#

連結スタックノード定義#

template <class T> class SNode {
private:
	SNode* next;  //ポインタ
	T Data;		  //データ
public:
	friend class Stack<T>;
	SNode() { next = nullptr; }	 //空ノード
	SNode(T data) {				 //データを持つノード
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }  //このノードのデータを表示する
};

連結スタック操作クラス定義#

template <class T> class Stack {
private:
	int maxsize;  //スタック容量
	SNode<T>* head;	 //ヘッダポインタ 空のヘッダノードを持つため、スタックトップ要素は常にhead->next
public:
	Stack(int size = 100);	//コンストラクタ スペースを割り当てる、空のヘッダノード
	~Stack();				//デストラクタ スペースを回収する
	void PrintStack();		//スタック内のすべての要素を表示する
	void Clear();			//スタック内のすべての要素をクリアする
	void Push(T data);		//プッシュ操作 要素dataをスタックトップに保存する
	T Pop();		 //ポップ操作 スタックトップ要素を取り出し、スタックから削除する
	T Top();		 //スタックトップ要素を取得する、取り出さない
	int Size();		 //スタック内の要素数を取得する
	bool IsEmpty();	 //スタックが空かどうかを判断する
	bool IsFull();	 //スタックが満杯かどうかを判断する
};

主要操作#

(1) コンストラクタとデストラクタ#

//コンストラクタ スペースを割り当てる、空のヘッダノード
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
	head = new SNode<T>;
	head->next = nullptr;
};

//デストラクタ スペースを解放する
template <class T> Stack<T>::~Stack() {
	while (head->next) {
		Pop();
	}
	if (head)
		delete head;
}

(2) スタックが空か満杯かの判断#

template <class T> bool Stack<T>::IsEmpty() {
	if (head->next) return false;
	else return true;
}
template <class T> bool Stack<T>::IsFull() {
	if (Size() < maxsize) return false;
	else return true;
}

(3) プッシュ操作#

要素 data をスタックトップに保存する

template <class T> void Stack<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:プッシュに失敗しました、スタックは満杯です！" << endl;
	} else {
		SNode<T>* p = new SNode<T>;
		p->Data = data;
		p->next = head->next;
		head->next = p;
	}
}

(4) スタックトップ要素の取得#

template <class T> T Stack<T>::Top() {
	if (IsEmpty()) {
		cout << "error:トップは存在しません、スタックは空です！" << endl;
		return error;
	} else {
		T temp = head->next->Data;
		return temp;
	}
}

(5) スタック内の要素数の取得#

template <class T> int Stack<T>::Size() {
	int cnt = 0;
	SNode<T>* p = head;
	while (p->next) {
		cnt++;
		p = p->next;
	}
	return cnt;
}

(6) ポップ操作#

スタックトップ要素を取り出し、スタックから削除する

template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:ポップに失敗しました、スタックは空です！" << endl;
		return error;
	} else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}

(7) スタック内のすべての要素を表示する#

スタックトップ要素を取り出し、スタックから削除する

template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:ポップに失敗しました、スタックは空です！" << endl;
		return error;
	} else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}

(8) スタック内のすべての要素をクリアする#

//(8) スタック内のすべての要素をクリアする
template <class T> void Stack<T>::Clear() {
	while (head->next) {
		Pop();
	}
}

完全なコード#

//連結スタック
#include <bits/stdc++.h>
#define error -1
using namespace std;
template <class T> class Stack;
//連結スタックノード定義
template <class T> class SNode {
private:
	SNode* next;  //ポインタ
	T Data;		  //データ
public:
	friend class Stack<T>;
	SNode() { next = nullptr; }	 //空ノード
	SNode(T data) {				 //データを持つノード
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }  //このノードのデータを表示する
};
//連結スタック操作クラス定義
template <class T> class Stack {
private:
	int maxsize;  //スタック容量
	SNode<T>* head;	 //ヘッダポインタ 空のヘッダノードを持つため、スタックトップ要素は常にhead->next
public:
	Stack(int size = 100);	//コンストラクタ スペースを割り当てる、空のヘッダノード
	~Stack();				//デストラクタ スペースを回収する
	void PrintStack();		//スタック内のすべての要素を表示する
	void Clear();			//スタック内のすべての要素をクリアする
	void Push(T data);		//プッシュ操作 要素dataをスタックトップに保存する
	T Pop();		 //ポップ操作 スタックトップ要素を取り出し、スタックから削除する
	T Top();		 //スタックトップ要素を取得する、取り出さない
	int Size();		 //スタック内の要素数を取得する
	bool IsEmpty();	 //スタックが空かどうかを判断する
	bool IsFull();	 //スタックが満杯かどうかを判断する
};

//連結スタック操作クラス実装
//コンストラクタ スペースを割り当てる、空のヘッダノード
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
	head = new SNode<T>;
	head->next = nullptr;
};

//デストラクタ スペースを解放する
template <class T> Stack<T>::~Stack() {
	while (head->next) {
		Pop();
	}
	if (head)
		delete head;
}
//(1) スタックが空かどうかを判断する
template <class T> bool Stack<T>::IsEmpty() {
	if (head->next)
		return false;
	else
		return true;
}
//(2) スタックが満杯かどうかを判断する
template <class T> bool Stack<T>::IsFull() {
	if (Size() < maxsize)
		return false;
	else
		return true;
}
//(3) プッシュ操作
// 要素dataをスタックトップに保存する
template <class T> void Stack<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:プッシュに失敗しました、スタックは満杯です！" << endl;
	}
	else {
		SNode<T>* p = new SNode<T>;
		p->Data = data;
		p->next = head->next;
		head->next = p;
	}
}
//(4) スタックトップ要素を取得する、取り出さない
template <class T> T Stack<T>::Top() {
	if (IsEmpty()) {
		cout << "error:トップは存在しません、スタックは空です！" << endl;
		return error;
	}
	else {
		T temp = head->next->Data;
		return temp;
	}
}
//(5) スタック内の要素数を取得する
template <class T> int Stack<T>::Size() {
	int cnt = 0;
	SNode<T>* p = head;
	while (p->next) {
		cnt++;
		p = p->next;
	}
	return cnt;
}
//(6) ポップ操作
// スタックトップ要素を取り出し、スタックから削除する
template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:ポップに失敗しました、スタックは空です！" << endl;
		return error;
	}
	else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}
//(7) スタック内のすべての要素を表示する
template <class T> void Stack<T>::PrintStack() {
	if (IsEmpty())
		cout << "このスタックは空です！" << endl;
	SNode<T>* p = head;
	int cnt = 0;
	while (p->next) {
		++cnt;
		p = p->next;
		cout << "第 " << cnt << " データは:";
		cout << p->Data << endl;
	}
	cout << "スタックには合計で " << Size() << " 要素があります。" << endl;
}
//(8) スタック内のすべての要素をクリアする
template <class T> void Stack<T>::Clear() {
	while (head->next) {
		Pop();
	}
}
//メイン関数で呼び出される関数 (テスト用)
template <class T> void Stack_Push(Stack<T>& S) {
	T data;
	cout << "スタックに入れる要素を入力してください:";
	cin >> data;
	getchar();
	S.Push(data);
	cout << "------------- プッシュ後、スタック S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Pop(Stack<T>& S) {
	T data = S.Pop();
	if (data != error) {
		cout << "取り出した要素は:";
		cout << data << endl;
	}
	cout << "------------- ポップ後、スタック S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Top(Stack<T>& S) {
	T data = S.Top();
	if (data != error) {
		cout << "スタックトップ要素は:";
		cout << data << endl;
	}
}
template <class T> void Stack_Size(Stack<T>& S) {
	cout << "このスタック内の要素数は:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(Stack<T>& S) {
	cout << "---------------------- スタック S --------------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_ClearStack(Stack<T>& S) {
	S.Clear();
	cout << "成功裏にクリアしました！" << endl;
}
int main() {
	int n;
	cout << "nを入力し、長さnの連結スタックを作成します:";
	cin >> n;
	Stack<int> S(n);
	cout << "n個の要素を入力してください:" << endl;
	for (int i = 0; i < n; ++i) {
		int data;
		cin >> data;
		S.Push(data);
	}
	cout << "1 プッシュ操作" << endl;
	cout << "2 ポップ操作" << endl;
	cout << "3 スタックトップ要素の取得" << endl;
	cout << "4 スタック内の要素数の取得" << endl;
	cout << "5 スタック内のすべての要素を出力" << endl;
	cout << "6 スタック内のすべての要素をクリア" << endl;
	cout << "7 終了" << endl;
	while (1) {
		int choice;
		cout << "メニュー選択:";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: Stack_Push(S); break;
			case 2: Stack_Pop(S); break;
			case 3: Stack_Top(S); break;
			case 4: Stack_Size(S); break;
			case 5: Stack_PrintStack(S); break;
			case 6: Stack_ClearStack(S); break;
			case 7: break;
			default: cout << "入力エラー、再入力してください";
		}
		if (choice == 7)
			exit(0);
		cout << "Enterキーを押して続行…" << endl;
		getchar();
	};
	return 0;
}