2018年02月07日
《その279》 問題演習 p.357演習9-11
新版明解C++中級編 p.357 演習9-11
次のキュー抽象クラステンプレート Queue<> から派生した、
配列仕様・線形リスト仕様・vector<>仕様の 各クラステンプレートを作成し、それらを利用するプログラムを作成せよ。
なお、キューの実装方法（配列・線形リスト・vector<>）は、プログラム実行時に、ユーザが選択できる形式にすること。
// Queue.h
#ifndef ___ClassQueue
#define ___ClassQueue
// 抽象クラステンプレート Queue<>
template <class Type> class Queue {
public:
class Overflow { }; // Overflow例外
class Empty { }; // Empty例外
// 純粋仮想デストラクタ
virtual ~Queue() = 0;
// 純粋仮想関数 push
virtual void enqueue(const Type&) = 0;
// 純粋仮想関数 pop
virtual Type dequeue() = 0;
};
template <class Type>
Queue<Type>::~Queue() { }
#endif
// 解答
// 以下のプログラムでは、
// 配列仕様のクラステンプレートは、《276》で作成した ArrayQueue<>
// 線形リスト仕様のクラステンプレートは、《277》で作成した ListQueue<>
// vector<>仕様のクラステンプレートは、《278》で作成した VectorQueue<>
// を使用しています。
// Queue.h
#ifndef ___ClassQueue
#define ___ClassQueue
// 抽象クラステンプレート Queue<>
template <class Type> class Queue {
public:
class Overflow { }; // Overflow例外
class Empty { }; // Empty例外
// 純粋仮想デストラクタ
virtual ~Queue() = 0;
// 純粋仮想関数 push
virtual void enqueue(const Type&) = 0;
// 純粋仮想関数 pop
virtual Type dequeue() = 0;
};
template <class Type>
Queue<Type>::~Queue() { }
#endif
// ArrayQueue.h
#ifndef ___ClassArrayQueue
#define ___ClassArrayQueue
#include "Queue.h"
// 配列仕様のキュー ArrayQueue<>
template <class Type> class ArrayQueue
: public Queue<Type> {
// データ収納用配列の要素数
static const int size = 10;
int ptr; // キューポインタ
Type que[size]; // キューの本体
public:
ArrayQueue() : ptr(0) { }
~ArrayQueue() { }
void enqueue(const Type& x) {
if (ptr >= size)
throw Queue<Type>::Overflow();
que[ptr++] = x;
}
Type dequeue() {
if (ptr <= 0)
throw Queue<Type>::Empty();
Type temp = que[0];
--ptr;
for (int i = 0; i < ptr; i++)
que[i] = que[i + 1];
return temp;
}
};
#endif
// ListQueue.h
#ifndef ___ClassListQueue
#define ___ClassListQueue
#include "Queue.h"
// 線形リスト仕様のキュー ListQueue<>
template <class Type> class ListQueue
: public Queue<Type> {
// ノード Node<Type>
template <class Type> class Node {
friend class ListQueue<Type> ;
Type* data;
Node* next;
public:
Node(Type* d, Node* n)
: data(d), next(n) { }
};
Node<Type>* top;
Node<Type>* last;
public:
// コンストラクタ
ListQueue() {
top = NULL;
}
// デストラクタ
~ListQueue() {
while (top != NULL) {
if (top->next != NULL) {
Node<Type>* temp = top->next;
delete top->data;
delete top;
top = temp;
}
else {
delete top->data;
delete top;
top = NULL;
}
}
}
// enqueue
void enqueue(const Type& x) {
if (top == NULL)
top = last = new Node<Type>(new Type(x), NULL);
else {
Node<Type>* temp = last;
try {
last = new Node<Type>(new Type(x), NULL);
}
catch (const std::bad_alloc&) {
throw Queue<Type>::Overflow();
}
temp->next = last;
}
}
// dequeue
Type dequeue() {
if (top == NULL) {
throw Queue<Type>::Empty();
}
else if (top->next == NULL) {
Type temp = *(top->data);
delete top->data;
delete top;
top = NULL;
return temp;
}
else {
Node<Type>* temp = top->next;
Type tmp = *(top->data);
delete top->data;
delete top;
top = temp;
return tmp;
}
}
};
#endif
// VectorQueue.h
#ifndef ___ClassVectorQueue
#define ___ClassVectorQueue
#include "Queue.h"
#include <vector>
// テンプレートライブラリ vector<>
// によるキュー VectorQueue<>
template <class Type> class VectorQueue
: public Queue<Type> {
// データメンバとしての
// べクトルオブジェクト que の宣言
std::vector<Type> que;
public:
// コンストラクタ
VectorQueue() { }
// デストラクタ
~VectorQueue() { }
// enque
void enqueue(const Type& x) {
try {
// 末尾へ要素追加（push_back関数）
que.push_back(x);
}
catch (...) {
throw Queue<Type>::Overflow();
}
}
// dequeue
Type dequeue() {
// 要素が空かどうかの判定（empty関数）
if (que.empty())
throw Queue<Type>::Empty();
// 先頭要素を取得（front関数）
Type x = que.front();
// 先頭要素の削除
que.erase(que.begin());
return x;
}
};
#endif
// p357_9-11.cpp
#include <iostream>
#include "Queue.h"
#include "ArrayQueue.h"
#include "ListQueue.h"
#include "VectorQueue.h"
using namespace std;
template <class Type>
Queue<Type>* generate_Queue(int sw) {
switch (sw) {
case 1 : return new ArrayQueue<Type>();
case 2 : return new ListQueue<Type>();
default : return new VectorQueue<Type>();
}
}
// 全データの dequeue & 表示
template <class Type>
void dequeue_all(Queue<Type>& s) {
cout << " ";
int f = 0;
try {
while (1) {
cout << s.dequeue() << ' ';
f++;
}
}
catch (const Queue<Type>::Empty&) {
if (f)
;
else
cout << "Empty!!";
}
}
int main() {
int sw;
do {
cout << "キューの種類（ 1.配列 "
"2.線形リスト 3.vector ) : ";
cin >> sw;
} while (sw < 1 || sw > 3);
cout << '\n';
// キューを生成
Queue<int>* s = generate_Queue<int>(sw);
while (1) {
int menu;
cout << "◆ 1.enqueue 2.dequeue "
"3.全要素のdequeue 0.終了 : ";
cin >> menu;
if (menu == 0) break;
int x;
if (menu == 1) {
cout << "データ : "; cin >> x;
try {
s->enqueue(x);
}
catch (const Queue<int>::Overflow&) {
cout << " Overflow!!\n";
}
}
else if (menu == 2) {
try {
x = s->dequeue();
cout << " " << x << '\n';
}
catch (const Queue<int>::Empty&) {
cout << " Empty!!\n";
}
}
else if (menu == 3) {
dequeue_all(*s);
cout << '\n';
}
}
delete s;
}
この記事へのコメント
コメントを書く
この記事へのトラックバックURL
https://fanblogs.jp/tb/7287508
※ブログオーナーが承認したトラックバックのみ表示されます。
この記事へのトラックバック
