2. 클래스 Queue에 큐의 크기와 원소 수를 반환하는 함수를 추가하라.
3. 클래스 Queue에 큐를 두 개의 큐로 분할하는 함수를 추가하라. 첫 번째 큐는 처음부터 시작해서 하나 건너 원소를 포함하고 두 번째 큐는 나머지 원소를 포함한다. 큐 원소의 상대적 순서는 변하지 않는다. 이 함수의 복잡도는 어떻게 되는가?
#include <iostream>
#include <algorithm>
using namespace std;
template <class T>
class Queue {
private:
T* queue;
T* division1;
T* division2;
int front, rear, 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];
//나머지 연산 하는 이유 : capacity가 8이라 가정하자.
//front 위치가 7이라면 단순히 1만 더하여 원소를 반환하게 되면 capacity의 범위(0~7)를 넘어서게 되는 오류 발생.
}
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) { //역시나 capacity의 범위를 벗어나지 않는 범위 내에서 rear+1이 front와 같으면 큐가 만원이라는 뜻.
T* newQueue = new T[2 * capacity]; //크기가 두 배 되는 새로운 배열 생성
int start = (front + 1) % capacity; //queue에서 front위치 앞의 첫 번째 원소 위치
if (start < 2) //front가 0, 첫번째 원소 위치가 1이므로 1부터 순서대로 배열이 채워져있음. front 기준으로 둘로 나눠서 복사할 필요 x
copy(queue + start, queue + start + capacity - 1, newQueue);
else {
copy(queue + start, queue + capacity, newQueue);
//두 번째 부분 queue[front+1]과 queue[capacity-1] 사이에 있는 원소들을 newQueue[0]에서 부터 복사
copy(queue, queue + rear + 1, newQueue + capacity - start);
//첫 번째 부분 queue[0] ~ queue[rear]사이에 있는 원소들을 newQueue[capacity-front-1]에서부터 복사
}
//queue를 newQueue로 전환
front = 2 * capacity - 1;
rear = capacity - 2;
capacity *= 2;
delete[] queue;
queue = newQueue;
}
rear = (rear + 1) % capacity; //rear위치 한 칸 뒤로 이동
queue[rear] = item;
}
void Pop() {
if (IsEmpty())
throw "Queue is empty. Cannot delete.";
front = (front + 1) % capacity; //front위치 앞으로 하나 땡김
queue[front].~T(); //T를 위한 파괴자
}
int Size() { //2번 큐의 크기 반환
if (IsEmpty())
return 0;
else if ((rear + 1) % capacity == front)
return capacity;
else
return rear - front + 1;
}
int Count() { //2번 큐의 원소 수 반환
if (IsEmpty())
return 0;
else if ((rear + 1) % capacity == front)
return capacity - 1;
else
return rear - front;
}
void Print() {
cout << "Queue의 원소 출력" << endl;
cout << "{ ";
for (int i = front + 1; i <= rear; i++)
cout << queue[i] << " ";
cout << "}" << endl;
}
void Division() { //3번
int size = 0;
if (rear >= front) {
cout << "현재 front : " << front << ", rear : " << rear << endl;
size = (rear - front) / 2;
division1 = new T[size];
division2 = new T[size];
cout << "<첫 번째 큐>" << endl << "{ ";
for (int i = size; i <= rear; i++) {
division1[i] = queue[i];
cout << division1[i] << " ";
}
cout << "}" << endl;
cout << "<두 번째 큐>" << endl << "{ ";
for (int i = 1; i < size; i++) {
division2[i] = queue[i];
cout << division2[i] << " ";
}
cout << "}" << endl;
}
else {
cout << "현재 front : " << front << ", rear : " << rear << endl;
size = ((capacity - (front + 1)) + rear + 1) / 2; //front가 더 크기 때문에 그냥 rear-front하면 음수가 됨
division1 = new T[size];
division2 = new T[size];
cout << "<첫 번째 큐>" << endl << "{ ";
for (int i = (front + 1) % capacity; i < size; i++) {
division1[i] = queue[i];
cout << division1[i] << " ";
}
cout << "}" << endl;
cout << "<두 번째 큐>" << endl << "{ ";
for (int i = size; i <= rear; i++) {
division2[i] = queue[i];
cout << division2[i] << " ";
}
cout << "}" << endl;
}
}
};
int main() {
Queue<int> intQueue;
int i;
int k;
cout << "큐에 Push할 원소의 개수 : ";
cin >> k;
cout << endl;
for (i = 0; i < k; i++) {
int n;
cout << "큐에 Push할 원소 입력 : ";
cin >> n;
intQueue.Push(n);
}
intQueue.Print();
cout << endl << "큐의 크기 : " << intQueue.Size() << ", 원소 수 : " << intQueue.Count() << endl;
cout << "front 원소 : " << intQueue.Front() << ", rear 원소 : " << intQueue.Rear() << endl;
intQueue.Division();
}
//출력
* 1번은 안 할 거임
* 4, 5, 6번은 2회독 때 =.=