[Exercises 1]
/*
Rewrite functions Push and Pop using the variable lastOp as discussed in this section
이번 섹션에서 언급한 lastOp 변수를 사용하도록 Push, Pop 함수를 수정한다.
The queue should now be ble to hold up to capacity elements.
이제 큐는 배열의 크기만큼 요소를 가지고 있을 수 있을 것이다.
*/
#include <iostream>
#include <cstring>
using namespace std;
template <class T>
class Queue
{
private:
T *queue;
int front;
int rear;
int capacity;
int lastOp;
public:
Queue(int queueCapacity = 10) :capacity(queueCapacity)
{
if (capacity < 1)
throw "Queue capacity must be >0";
queue = new T[capacity];
front = rear = 0;
lastOp = 0;
}
bool IsEmpty() const
{
return (front == rear && lastOp == 2);
}
T &Front() const
{
if (IsEmpty())
throw "Queue is empty. No front element";
return queue[(front + 1) % capacity];
}
T &Rear() const
{
if (IsEmpty())
throw "Queue is empty. No rear element";
return queue[rear];
}
void Push(const T &item)
{
if ((rear + 1) % capacity == front)
{
//크기를 두배로
T *newQueue = new T[2 * capacity];
int start = (front + 1) % capacity;
if (start < 2)
//한바퀴 안 돌았을 경우
copy(queue + start, queue + start + capacity - 1, newQueue);
else
{
//한바퀴 돌았을 경우
copy(queue + start, queue + capacity, newQueue);
copy(queue, queue + rear + 1, newQueue + capacity - start);
}
front = 2 * capacity - 1;
rear = capacity - 2;
capacity *= 2;
delete[]queue;
queue = newQueue;
}
rear = (rear + 1) % capacity;
queue[rear] = item;
lastOp = 1;
}
void Pop()
{
if (IsEmpty())
throw "Queue is empty. Can't delete";
lastOp = 2;
front = (front + 1) % capacity;
queue[front].~T(); //destructor for T
}
void LastOp()
{
if (lastOp == 1)
cout << "Push" << endl;
else if (lastOp == 2)
cout << "Pop" << endl;
}
};
int main(void)
{
Queue<int> intQueue;
cout << "Push" << endl;
for (int i = 0; i < 10; i++)
intQueue.Push(i + 1);
cout << "현재 front: " << intQueue.Front() << endl;
cout << "현재 rear: " << intQueue.Rear() << endl;
cout << "현재 lastOp: ";
intQueue.LastOp();
cout << endl << "Pop" << endl;
intQueue.Pop();
cout << "현재 front: " << intQueue.Front() << endl;
cout << "현재 rear: " << intQueue.Rear() << endl;
cout << "현재 lastOp: ";
intQueue.LastOp();
return 0;
}
[Exercises 2]
/*
To the class Queue, add functions to return the size and capacity of a queue
Queue 클래스에 배열의 크기와 현재 들어가있는 요소의 수를 반환하는 함수를 추가한다
*/
#include <iostream>
using namespace std;
template <class T>
class Queue
{
private:
T *queue;
int front;
int rear;
int capacity;
public:
Queue(int queueCapacity = 10) :capacity(queueCapacity)
{
if (capacity < 1)
throw "Queue capacity must be >0";
queue = new T[capacity];
front = rear = 0;
}
bool IsEmpty() const
{
return front == rear;
}
T &Front() const
{
if (IsEmpty())
throw "Queue is empty. No front element";
return queue[(front + 1) % capacity];
}
T &Rear() const
{
if (IsEmpty())
throw "Queue is empty. No rear element";
return queue[rear];
}
void Push(const T &item)
{
if ((rear + 1) % capacity == front)
{
//두배로
T *newQueue = new T[2 * capacity];
int start = (front + 1) % capacity;
if (start < 2)
//한바퀴 돌지 않았을 때
copy(queue + start, queue + start + capacity - 1, newQueue);
else
{
//한바퀴 돌았을 때
copy(queue + start, queue + capacity, newQueue);
copy(queue, queue + rear + 1, newQueue + capacity - start);
}
front = 2 * capacity - 1;
rear = capacity - 2;
capacity *= 2;
delete[]queue;
queue = newQueue;
}
rear = (rear + 1) % capacity;
queue[rear] = item;
}
void Pop()
{
if (IsEmpty())
throw "Queue is empty. Can't delete";
front = (front + 1) % capacity;
queue[front].~T();
}
void Size()
{
cout << "전체 배열의 크기: " << capacity << endl;
cout << "rear: " << rear << "\tfront: " << front << endl;
if (rear >= front)
cout << "현재 배열에 있는 요소의 수: " << rear - front << endl;
else
cout << "현재 배열에 있는 요소의 수: " << (capacity-(front+1))+rear + 1 << endl;
}
};
int main(void)
{
Queue<int> intQueue;
for (int i = 0; i < 10; i++)
intQueue.Push(i + 1);
intQueue.Size();
for (int i = 0; i < 5; i++)
intQueue.Pop();
intQueue.Size();
return 0;
}
[Exercises 3]
/*
To the class Queue, add a function to split a queue into two queues.
큐 클래스에, 큐를 두개의 큐로 나누는 함수를 추가한다.
The first queue is to contain every other element beginning with the first; the second queue contatins the remaining elements.
첫 번째 큐는 첫번째 큐로부터 시작하는 요소들로 채워지고, 두 번째 큐는 그 외의 요소들을 채운다
The relative order of queue elements is unchanged
이 때, 원래 순서가 바뀌지 않도록 한다
*/
#include <iostream>
using namespace std;
template <class T>
class Queue
{
private:
T *queue;
T *split1;
T *split2;
int front;
int rear;
int capacity;
public:
Queue(int queueCapacity = 10) :capacity(queueCapacity)
{
if (capacity < 1)
throw "Queue capacity must be >0";
queue = new T[capacity];
front = rear = 0;
}
~Queue()
{
delete[]queue;
delete[]split1;
delete[]split2;
}
void split()
{
int size = 0;
if (rear >= front)
{
size = (rear - front) / 2;
cout << "size: " << size << endl;
cout << "front: " << front << "\t" << "rear: " << rear << "\t" << "capacity: " << capacity << endl;
split1 = new T[rear-size+1];
split2 = new T[size];
cout << "첫번째 큐" << endl;
for (int i = size; i <= rear; i++)
{
split1[i] = queue[i];
cout << split1[i] << " ";
}
cout << endl << "두번째 큐" << endl;
for (int i = 1; i < size; i++)
{
split2[i] = queue[i];
cout << split2[i] << " ";
}
cout << endl;
}
else
{
size = ((capacity - (front + 1)) + rear + 1) / 2;
cout << "size: " << size << endl;
cout << "front: " << front << "\t" << "rear: " << rear << "\t" << "capacity: " << capacity << endl;
split1 = new T[capacity-size];
split2 = new T[rear + 1];
cout << "첫번째 큐" << endl;
for (int i = (front + 1)%capacity; i < size; i++)
{
split1[i] = queue[i];
cout << split1[i] << " ";
}
cout << endl << "두번째 큐" << endl;
for (int i = size; i <= rear; i++)
{
split2[i] = queue[i];
cout << split2[i] << " ";
}
cout << endl;
}
}
bool IsEmpty() const
{
return front == rear;
}
T &Front() const
{
if (IsEmpty())
throw "Queue is empty. No front element";
return queue[(front + 1) % capacity];
}
T &Rear() const
{
if (IsEmpty())
throw "Queue is empty. No rear element";
return queue[rear];
}
void Push(const T &item)
{
if ((rear + 1) % capacity == front)
{
//두배로
T *newQueue = new T[2 * capacity];
int start = (front + 1) % capacity;
if (start < 2)
//한바퀴 돌지 않았을 때
copy(queue + start, queue + start + capacity - 1, newQueue);
else
{
//한바퀴 돌았을 때
copy(queue + start, queue + capacity, newQueue);
copy(queue, queue + rear + 1, newQueue + capacity - start);
}
front = 2 * capacity - 1;
rear = capacity - 2;
capacity *= 2;
delete[]queue;
queue = newQueue;
}
rear = (rear + 1) % capacity;
queue[rear] = item;
}
void Pop()
{
if (IsEmpty())
throw "Queue is empty. Can't delete";
front = (front + 1) % capacity;
queue[front].~T();
}
void Size()
{
cout << "전체 배열의 크기: " << capacity << endl;
cout << "rear: " << rear << "\tfront: " << front << endl;
if (rear >= front)
cout << "현재 배열에 있는 요소의 수: " << rear - front << endl;
else
cout << "현재 배열에 있는 요소의 수: " << (capacity - (front + 1)) + rear + 1 << endl;
}
};
int main(void)
{
Queue<int> intQueue;
for (int i = 0; i < 10; i++)
intQueue.Push(i+1);
intQueue.split(); //나눈다
return 0;
}
[Exercises 4]
/*
To the class Queue, add a function to merge two queues into one by alternately taking elements from each queue.
큐 클래스에 두 개의 큐를 번갈아가면서 합치는 함수를 추가하라.
The relative oreder of queue elements is unchanged.
이 때 순서는 바뀌지 않는다.
*/
/*
To the class Queue, add a function to split a queue into two queues.
큐 클래스에, 큐를 두개의 큐로 나누는 함수를 추가한다.
The first queue is to contain every other element beginning with the first; the second queue contatins the remaining elements.
첫 번째 큐는 첫번째 큐로부터 시작하는 요소들로 채워지고, 두 번째 큐는 그 외의 요소들을 채운다
The relative order of queue elements is unchanged
이 때, 원래 순서가 바뀌지 않도록 한다
*/
#include <iostream>
using namespace std;
template <class T>
class Queue
{
private:
T *queue;
int front;
int rear;
int capacity;
public:
Queue(int queueCapacity = 10) :capacity(queueCapacity)
{
if (capacity < 1)
throw "Queue capacity must be >0";
queue = new T[capacity];
for (int i = 0; i < capacity; i++)
queue[i] = -1; //초기화를 이런식으로 해서 합칠 때 편하게
front = rear = 0;
}
~Queue()
{
delete[]queue;
}
bool IsEmpty() const
{
return front == rear;
}
T &Front() const
{
if (IsEmpty())
throw "Queue is empty. No front element";
return queue[(front + 1) % capacity];
}
T &Rear() const
{
if (IsEmpty())
throw "Queue is empty. No rear element";
return queue[rear];
}
void Push(const T &item)
{
if ((rear + 1) % capacity == front)
{
//두배로
T *newQueue = new T[2 * capacity];
int start = (front + 1) % capacity;
if (start < 2)
//한바퀴 돌지 않았을 때
copy(queue + start, queue + start + capacity - 1, newQueue);
else
{
//한바퀴 돌았을 때
copy(queue + start, queue + capacity, newQueue);
copy(queue, queue + rear + 1, newQueue + capacity - start);
}
front = 2 * capacity - 1;
rear = capacity - 2;
capacity *= 2;
delete[]queue;
queue = newQueue;
}
rear = (rear + 1) % capacity;
queue[rear] = item;
}
void Pop()
{
if (IsEmpty())
throw "Queue is empty. Can't delete";
front = (front + 1) % capacity;
queue[front].~T();
}
template <typename T>
friend void Merge(Queue<T> &q1, Queue<T> &q2, Queue<T> &merge);
};
template <typename T>
void Merge(Queue<T> &q1, Queue<T> &q2, Queue<T> &merge)
{
int idx = 0;
int index = 0;
while (idx < merge.capacity)
{
if (q1.queue[index] != -1)
merge.queue[idx++] = q1.queue[index];
if (q2.queue[index] != -1)
merge.queue[idx++] = q2.queue[index];
index++;
}
cout << "합친 결과" << endl;
for (int i = 0; i < idx; i++)
cout << merge.queue[i] << " ";
cout << endl;
}
int main(void)
{
Queue<int> intQueue1;
Queue<int> intQueue2;
Queue<int> merge(20);
for (int i = 0; i < 10; i++)
{
intQueue1.Push(i + 1);
intQueue2.Push(i * 2);
}
Merge(intQueue1, intQueue2, merge);
return 0;
}
[Exercises 5]
/*
A double-ended queue(deque) is a linear list in which additions and deletions may be made at either end
덱은 Push와 Pop이 양쪽 끝에서 모두 허용되는 리스트이다
Obtain a data representation mapping a deque into a one-dimensional array
덱을 나타내는 일차원배열을 만들어본다.
Write a C++ template functions to add and delete elements from either end of the deque and also to return an element from either end
덱의 양 끝에서 추가하거나 삭제하는 함수를 작성하고 양 끝의 요소를 반환하는 함수도 작성한다
*/
#include <iostream>
using namespace std;
template <class T>
class Deque
{
private:
T *deque;
int size; //안에 있는 요소
int capacity;
int front;
int rear;
public:
Deque(int dequeCapacity = 10) :capacity(dequeCapacity), size(0)
{
if (capacity < 1)
throw "Deque의 크기는 0보다 커야한다";
deque = new T[capacity];
front = rear = 0;
}
bool IsEmpty() const
{
return front == rear;
}
T &Front() const
{
if (IsEmpty())
throw "deque는 비어있습니다";
return deque[front];
}
T &Rear() const
{
if (IsEmpty())
throw "deque는 비어있습니다";
return deque[rear];
}
void PushFront(const T &item) //앞에 Push
{
if (size == 0)
{
deque[front] = item;
}
else
{
deque[front - 1] = item;
front--;
size++;
}
}
void PushRear(const T &item) //뒤에 Push
{
if (size == 0)
{
deque[rear] = item;
size++;
}
else
{
deque[rear + 1] = item;
rear++;
size++;
}
}
void PopFront()
{
if (IsEmpty())
throw "deque는 비어있습니다";
deque[front].~T();
front++;
size--;
}
void PopRear()
{
if (IsEmpty())
throw "deque는 비어있습니다";
deque[rear].~T();
rear--;
size--;
}
template <typename T>
friend ostream &operator<<(ostream &os, Deque<T> &dq);
};
template <typename T>
ostream &operator<<(ostream &os, Deque<T> &dq)
{
if (dq.front < dq.rear)
{
for (int i = dq.front; i <= dq.rear; i++)
{
if (dq.size == 0)
break;
os << dq.deque[i] << " ";
}
}
else
{
for (int i = dq.rear; i <= dq.front; i++)
{
if (dq.size == 0)
break;
os << dq.deque[i] << " ";
}
}
return os;
}
int main(void)
{
Deque<int> intDeque;
for (int i = 0; i < 5; i++)
intDeque.PushRear((i + 2) * 4);
for (int i = 0; i < 5; i++)
intDeque.PushFront((i + 1)*3);
cout << endl << "덱 출력" << endl;
cout << intDeque << endl;
cout << "현재 front: " << intDeque.Front();
cout << "\t현재 rear: " << intDeque.Rear() << endl;
cout << endl << "Front Pop" << endl;
intDeque.PopFront();
cout << "현재 front: " << intDeque.Front();
cout << "\t현재 rear: " << intDeque.Rear() << endl;
cout << endl << "Rear Pop" << endl;
intDeque.PopRear();
cout << "현재 front: " << intDeque.Front();
cout << "\t현재 rear: " << intDeque.Rear() << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*6번 문제는 링크드리스트로 넘어가면 질리도록 풀 문제 중 하나기 때문에 생략했습니다.
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 미로 예제 (4) | 2017.08.13 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.4 연습문제 (2) | 2017.08.13 |
| 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 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 1~4 (0) | 2017.08.03 |