[Exercises 1]
/*
Implement Stack as a publicly derived class of Bag using templates
템플릿을 이용하여 Bag 클래스를 상속하는 Stack 클래스를 구현한다
*/
#include <iostream>
using namespace std;
template <typename T>
class Bag
{
protected:
T *array;
int capacity;
int top;
public:
Bag(int bagCapacity = 10) :capacity(bagCapacity)
{
array = new T[capacity];
top = -1;
}
virtual ~Bag()
{
delete[]array;
}
virtual void Push(const T &item)
{
if (IsFull())
{
cout << "꽉 차서 더 이상 Push 불가능" << endl;
}
array[++top] = item;
}
virtual T Pop() = 0; //가상함수 즉, Bag에서는 딱히 쓸모가 없지만 Stack에서 쓸모가 있기 때문에
virtual void Del() //top을 지운다(Stack의 Pop과는 다르기 때문에 새로 정의)
{
if (IsEmpty())
{
cout << "스택은 비었다" << endl;
}
for (int i = (top / 2); i < top; i++)
{
array[i] = array[i + 1]; //한칸씩 땡긴다
}
top--;
}
virtual bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
virtual bool IsFull()
{
if (top >= capacity)
return true;
return false;
}
template <typename T>
friend ostream &operator<<(ostream &os, Bag<T> &b);
};
template <typename T>
ostream &operator<<(ostream &os, Bag<T> &b)
{
for (int i = 0; i <= b.top; i++)
os << b.array[i] << " ";
os << endl;
return os;
}
template <typename T>
class Stack :public Bag<T>
{
public:
Stack(int stackCapacity = 10) :Bag<T>(stackCapacity)
{
}
~Stack()
{
//자동으로 ~Bag()
}
T Pop()
{
if (IsEmpty())
cout << "스택은 비어있다" << endl;
T del=array[top--];
return del;
}
};
int main(void)
{
Stack<int> intStack;
for (int i = 0; i < 10; i++)
{
intStack.Push(i + 1);
}
cout << "현재 스택 출력" << endl;
cout << intStack << endl;
for (int i = 0; i < 5; i++)
{
cout << i + 1 << "번째 Pop: " << intStack.Pop() << endl;
}
cout << endl << "5번 Pop 후 스택 출력" << endl;
cout << intStack << endl;
return 0;
}
[Exercises 2]
/*
Implement Queue as a publicly derived class of Bag using templates
앞선 문제와 마찬가지로 템플릿을 이용하여 Bag 클래스를 상속한 큐를 구현한다
*/
#include <iostream>
using namespace std;
template <typename T>
class Bag
{
protected:
T *array;
int capacity;
int top;
public:
Bag(int bagCapacity = 10) :capacity(bagCapacity)
{
array = new T[capacity];
top = -1;
}
virtual ~Bag()
{
delete[]array;
}
virtual void Push(const T &item)
{
if (IsFull())
{
cout << "꽉 차서 더 이상 Push 불가능" << endl;
}
array[++top] = item;
}
virtual void Del() //top을 지운다(Stack의 Pop과는 다르기 때문에 새로 정의)
{
if (IsEmpty())
{
cout << "스택은 비었다" << endl;
}
for (int i = (top / 2); i < top; i++)
{
array[i] = array[i + 1]; //한칸씩 땡긴다
}
top--;
}
virtual bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
virtual bool IsFull()
{
if (top >= capacity)
return true;
return false;
}
template <typename T>
friend ostream &operator<<(ostream &os, Bag<T> &b);
};
template <typename T>
ostream &operator<<(ostream &os, Bag<T> &b)
{
for (int i = 0; i <= b.top; i++)
os << b.array[i] << " ";
os << endl;
return os;
}
template <typename T>
class Queue :public Bag<T>
{
protected:
int front;
//원래는 rear까지 정의해야하지만 Bag 클래스의 top이 rear 역할
public:
Queue(int queueCapacity = 10) :Bag<T>(queueCapacity), front(0)
{
}
~Queue()
{
//~Bag() 자동 호출
}
//Bag 클래스의 Push 함수가 Queue Enqueue 역할
T Dequeue()
{
if (IsEmpty())
{
cout << "Queue는 비어있다" << endl;
return 0;
}
T del = array[front++];
return del;
}
int &Front() const
{
if (IsEmpty())
cout << "Queue는 비어있다" << endl;
return array[front + 1];
}
int &Rear() const
{
if (IsEmpty())
cout << "Queue는 비어있다" << endl;
return array[top];
}
bool IsEmpty() const
{
return top == front;
}
template <typename T>
friend ostream &operator<<(ostream &os, Queue<T> &q);
};
template <typename T>
ostream &operator<<(ostream &os, Queue<T> &q)
{
for (int i = q.front; i <= q.top; i++)
cout << q.array[i] << " ";
cout << endl;
return os;
}
int main(void)
{
Queue<int> intQueue;
for (int i = 0; i < 10; i++)
{
intQueue.Push(i + 1);
}
cout << "현재 큐 출력" << endl;
cout << intQueue << endl;
for (int i = 0; i < 5; i++)
{
cout << i + 1 << "번째 Dequeue: " << intQueue.Dequeue() << endl;
}
cout << "5번 Dequeue 후 큐 출력" << endl;
cout << intQueue << endl;
return 0;
}
[Exercises 3]
/*
A double-ended queue(deque) is a linear list in which additions and deletions may be made at either end
덱은 양쪽 끝에서 Enqueue와 Dequeue가 가능한 선형 리스트이다.
Implement the class Deque as a publicly derived class of Queue
큐 클래스를 상속받는 덱 클래스를 구현하라.
The class Deque must have public function to add and delete elements from either end of the deque and also to return an element from either end
덱 클래스에는 양 쪽 끝에서 Enqueue와 Dequeue를 수행하는 함수가 있어야 하고 양 쪽 끝의 요소를 반환하는 함수도 있어야한다.
*/
#include <iostream>
using namespace std;
template <typename T>
class Bag
{
protected:
T *array;
int capacity;
int top;
public:
Bag(int bagCapacity = 100) :capacity(bagCapacity)
{
array = new T[capacity];
top = 50;
}
virtual ~Bag()
{
delete[]array;
}
virtual void Push(const T &item)
{
if (IsFull())
{
cout << "꽉 차서 더 이상 Push 불가능" << endl;
}
array[++top] = item;
}
virtual T Del() //top을 지운다(Stack의 Pop과는 다르기 때문에 새로 정의)
{
if (IsEmpty())
{
cout << "스택은 비었다" << endl;
}
for (int i = (top / 2); i < top; i++)
{
array[i] = array[i + 1]; //한칸씩 땡긴다
}
T del=array[top--];
return del;
}
virtual bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
virtual bool IsFull()
{
if (top >= capacity)
return true;
return false;
}
template <typename T>
friend ostream &operator<<(ostream &os, Bag<T> &b);
};
template <typename T>
ostream &operator<<(ostream &os, Bag<T> &b)
{
for (int i = 0; i <= b.top; i++)
os << b.array[i] << " ";
os << endl;
return os;
}
template <typename T>
class Queue :public Bag<T>
{
protected:
int front;
//원래는 rear까지 정의해야하지만 Bag 클래스의 top이 rear 역할
public:
Queue(int queueCapacity = 100) :Bag<T>(queueCapacity), front(50)
{
}
virtual ~Queue()
{
//~Bag() 자동 호출
}
//Bag 클래스의 Push 함수가 Queue Enqueue 역할
virtual T Dequeue()
{
if (IsEmpty())
{
cout << "Queue는 비어있다" << endl;
return 0;
}
T del = array[++front];
return del;
}
virtual int &Front() const
{
if (IsEmpty())
cout << "Queue는 비어있다" << endl;
return array[front + 1];
}
virtual int &Rear() const
{
if (IsEmpty())
cout << "Queue는 비어있다" << endl;
return array[top];
}
virtual bool IsEmpty() const
{
return top == front;
}
template <typename T>
friend ostream &operator<<(ostream &os, Queue<T> &q);
};
template <typename T>
ostream &operator<<(ostream &os, Queue<T> &q)
{
for (int i = q.front; i <= q.top; i++)
cout << q.array[i] << " ";
cout << endl;
return os;
}
template <typename T>
class Deque :public Queue<T>
{
public:
Deque(int dequeCapacity = 100) :Queue<T>(dequeCapacity)
{
}
~Deque()
{
//~Bag()와 ~Queue() 자동 수행
}
T DequeueFront()
{
T del=Dequeue(); //그대로 쓰인다
return del;
}
T DequeueRear() //끝을 삭제시키는 함수
{
if (IsEmpty())
{
cout << "덱은 비어있다" << endl;
return 0;
}
T del = array[top--];
return del;
}
void PushFront(const T &item)
{
if (IsFull())
{
cout << "꽉 차서 더 이상 Push 불가능" << endl;
}
array[front--] = item; //배열은 -1번째 요소라는 개념이 없기 때문에 배열의 크기를 키우고 50에서 시작시켰습니다
}
void PushRear(const T &item)
{
Push(item); //Bag의 Push 함수 사용
}
//Front와 Rear 반환은 Queue 클래스에서 그대로 사용하면 된다
template <typename T>
friend ostream &operator<<(ostream &os, Deque<T> &dq);
};
template <typename T>
ostream &operator<<(ostream &os, Deque<T> &dq)
{
for (int i = dq.front+1; i <= dq.top; i++) //마지막 PushFront 때 front-- 가 진행되기 때문에
cout << dq.array[i] << " ";
cout << endl;
return os;
}
int main(void)
{
Deque<int> intDeque;
for (int i = 0; i < 5; i++)
{
intDeque.PushFront(i + 1);
}
for (int i = 0; i < 5; i++)
{
intDeque.PushRear((i + 1) * 2);
}
cout << "현재 덱 출력" << endl;
cout << intDeque << endl;
for (int i = 0; i < 3; i++)
{
cout << i + 1 << "번째 DequeueRear: " << intDeque.DequeueRear() << endl;
}
cout << "현재 덱 출력" << endl;
cout << intDeque << endl;
for (int i = 0; i < 3; i++)
{
cout << i + 1 << "번째 DequeueFront: " << intDeque.DequeueFront() << endl;
}
cout << "현재 덱 출력" << endl;
cout << intDeque << endl;
return 0;
}
[Exercises 4]
/*
For each of the following pairs state wheter they are linked by the IS-A relationship.
주어진 쌍들이 IS-A 관계인지 파악해라
*/
(a) Rectangle and Trapezium
(a) 직사각형, 대능형골
->서로 연관이 없기 때문에 IS-A 관계가 아니다
(b) Rectangle and Circle
(b) 직사각형, 원
->서로 연관이 없기 때문에 IS-A 관계가 아니다
(c) Lion and Tiger
(c) 사자, 호랑이
->둘다 고양이과이긴 하지만 IS-A 관계는 아니다
(d) Stack and OrderedList
(d) 스택, 정렬된 리스트
->스택은 정렬된 리스트일 수도 있기 때문에 IS-A 관계
(e) Queue and OrderedList
(e) 큐, 정렬된 리스트
->큐도 정렬된 리스트일 수도 있기 때문에 IS-A 관계
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 후위표기법 예제 (2) | 2017.08.15 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 미로 예제 (4) | 2017.08.13 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.3 연습문제 (0) | 2017.08.11 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.2 연습문제 (0) | 2017.08.11 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 5~9 (0) | 2017.08.04 |