개념
정의
FIFO(First in First Out)의 자료구조
- Front: 가장 처음에 들어온 원소의 인덱스 - 1
- Rear: 가장 마지막에 들어온 원소를 가리키는 인덱스
- capacity: 큐가 최대로 담을 수 있는 원소의 개수(배열의 크기 - 1)
- size: 현재 큐에 담겨져 있는 원소의 개수(size = rear - front)
- enqueue: 큐에 데이터를 넣는 연산(rear = (rear + 1) % capacity)
- dequeue: 큐에서 데이터를 빼는 연산(front = (front + 1) % capacity)
Front 와 Rear
- front, rear 두 개의 인덱스를 사용해서 전체 배열의 시작과 끝을 추적한다.
- front와 rear의 값이 동일할 경우, 해당 큐는 비어있다.
- front는 가장 먼저 추가 된 아이템으 인덱스보다 값이 1 작은 값이고 rear는 가장 마지막에 추가 된 아이템의 인덱스다.
- front, rear 모두 업데이트를 할 때 나머지 연산을 사용한다.
- 큐가 가득 차 있는 상태의 경우 즉, front의 나머지 연산 결과가 rear과 동일한 경우에 메모리를 증가시킨 후에 내용물을 모두 복사한다.
구현
성능을 최대로 발휘하기 위해 원형큐로 큐를 구현한다.
enqueue
void Enqueue(const T &item) // 맨 뒤에 추가, Push()
{
if (IsFull())
Resize();
// REVIEW: 인덱스 변화를 수정한 다음에 엔큐하기
rear_ = (rear_ + 1) % capacity_;
queue_[rear_] = item;
}
dequeue
void Dequeue() // 큐의 첫 요소 삭제, Pop()
{
assert(!IsEmpty());
// REVIEW:
front_ = (front_ + 1) % capacity_;
}
resize(반복문 ver)
void Resize() // 2배씩 증가
{
T *temp = new T[capacity_ * 2];
int count = 1;
/* NOTE: 초기식과 증감식을 활용해서 인덱스 조절 가능 + 조건식을 통해 종료조건 지정 가능 */
for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i = (i + 1) % capacity_) {
temp[++count] = queue_[i];
}
front_ = 0;
rear_ = capacity_ - 1;
capacity_ *= 2;
delete[] queue_; // NOTE: 객체를 교체할 때 반드시 메모리를 해제해줄 것!
queue_ = temp;
}
resize(memcpy ver)
void Resize() // 2배씩 증가
{
int start = (front_ + 1) % capacity_;
if (start < 2) {
memcpy(temp, queue_ + start, sizeof(T) * (capacity_ - 1)); // 포인터연산을 통해 주소 지정
} else {
memcpy(temp, queue_ + start, sizeof(T) * (capacity_ - start));
memcpy(temp + capacity_ - start, queue_, sizeof(T) * (rear_ + 1));
}
front_ = 2 * capacity_ - 1; // 빈공간을 없애는 방식일 때 front의 위치
rear_ = capacity_ - 2; // memcpy로 구현했을 때 rear_의 인덱스값
capacity_ *= 2; // 새로 갱신 된 배열의 크기 추적
delete[] queue_;
queue_ = temp;
}
전체코드
#pragma once
#include <cassert>
#include <iomanip>
#include <iostream>
using namespace std;
template <typename T> // 템플릿 선언 -> 제네릭 프로그래밍 목적
class Queue // Circular Queue
{
public:
/* 큐 생성자 */
Queue(int capacity = 2) {
assert(capacity > 0);
capacity_ = capacity;
queue_ = new T[capacity_];
front_ = rear_ = 0;
}
/* 큐 소멸자 */
~Queue() {
if (queue_)
delete[] queue_;
}
/* 큐가 비어있는 지 여부 */
bool IsEmpty() const { return front_ == rear_; }
/* 큐가 차 있는지 여부 */
bool IsFull() const {
// 원형 큐에서 꽉 찼다의 기준
return (rear_ + 1) % capacity_ == front_;
}
/* 큐의 맨 앞 인덱스 */
T &Front() const {
assert(!IsEmpty());
return queue_[(front_ + 1) % capacity_]; // 주의 + 1
}
/* 큐의 끝 인덱스 */
T &Rear() const {
assert(!IsEmpty());
return queue_[rear_];
}
/* TODO: 큐의 크기 */
int Size() const {
// 하나하나 세는 방법 보다는 경우를 따져서 바로 계산하는 것이 빠릅니다.
// if-else-if-else로 구현하는 경우
// if (...)
// return ...;
// else if (...)
// return ...;
// else
// return 0;
// 또는 if-else 하나로도 구현 가능합니다.
// if (...)
// return ...;
// else
// return ...;
if (IsEmpty()) {
return 0;
} else if (rear_ > front_) {
return rear_ - front_;
} else {
return rear_ + capacity_ - front_;
}
}
/* 크기 재조정 */
// NOTE: 원형큐에서 구현하기 가장 까다로운 부분
void Resize() // 2배씩 증가
{
// 조언
// - 새로운 개념이 항상 그렇듯 원형 큐도 처음에는 어렵고 나중에는 당연해집니다.
// - 처음 공부하실 때 답을 맞추려고 하지 마시고 "어떻게 디버깅을 잘 할까?"를 찾으세요.
// - 부지런히 여러가지 출력해보고 "출력하는 도구(예: 배열 출력)"도 만들어서 사용해보고
// - 머리도 쓰고 고민도 하다 보면 인생을 지탱해줄 능력을 갖추게 됩니다.
// - 힘들면 디스코드에서 조금씩 도움 받으시는 것도 좋아요.
// REVIEW: 하나하나 복사하는 방식은 쉽게 구현할 수 있습니다.
// (도전) 경우를 나눠서 memcpy()로 블럭 단위로 복사하면 더 효율적입니다.
T *temp = new T[capacity_ * 2];
// int count = 1;
// /* NOTE: 초기식과 증감식을 활용해서 인덱스 조절 가능 + 조건식을 통해 종료조건 지정 가능 */
// for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i = (i + 1) % capacity_) {
// temp[++count] = queue_[i];
// }
// front_ = 0;
// rear_ = capacity_ - 1;
// capacity_ *= 2;
// delete[] queue_; // NOTE: 객체를 교체할 때 반드시 메모리를 해제해줄 것!
// queue_ = temp;
int start = (front_ + 1) % capacity_; //
if (start < 2) {
memcpy(temp, queue_ + start, sizeof(T) * (capacity_ - 1)); // 포인터연산을 통해 주소 지정
} else {
memcpy(temp, queue_ + start, sizeof(T) * (capacity_ - start));
memcpy(temp + capacity_ - start, queue_, sizeof(T) * (rear_ + 1));
}
front_ = 2 * capacity_ - 1; // 빈공간을 없애는 방식일 때 front의 위치
rear_ = capacity_ - 2; // memcpy로 구현했을 때 rear_의 인덱스값
capacity_ *= 2; // 새로 갱신 된 배열의 크기 추적
delete[] queue_;
queue_ = temp;
}
void Enqueue(const T &item) // 맨 뒤에 추가, Push()
{
if (IsFull())
Resize();
// REVIEW: 인덱스 변화를 수정한 다음에 엔큐하기
rear_ = (rear_ + 1) % capacity_;
queue_[rear_] = item;
}
void Dequeue() // 큐의 첫 요소 삭제, Pop()
{
assert(!IsEmpty());
// REVIEW:
front_ = (front_ + 1) % capacity_;
}
void Print() {
using namespace std;
for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i = (i + 1) % capacity_)
cout << queue_[i] << " ";
cout << endl;
if (print_debug_)
PrintDebug();
}
void PrintDebug() {
using namespace std;
cout << "Cap = " << capacity_ << ", Size = " << Size();
cout << endl;
// front와 rear 위치 표시
for (int i = 0; i < capacity_; i++) {
if (i == front_)
cout << " F ";
else if (i == rear_)
cout << " R ";
else
cout << " ";
}
cout << endl;
// 0 based index
for (int i = 0; i < capacity_; i++)
cout << setw(2) << i << " ";
cout << endl;
if (front_ < rear_) {
// front 앞 사용하지 않은 공간
for (int i = 0; i < front_ + 1; i++)
cout << " - ";
// 저장된 내용물
for (int i = front_ + 1; i <= rear_; i++)
cout << setw(2) << queue_[i] << " ";
// rear 뒤 사용하지 않은 공간
for (int i = rear_ + 1; i < capacity_; i++)
cout << " * ";
cout << endl << endl;
} else if (front_ > rear_) {
// rear 이전에 저장된 내용물
for (int i = 0; i <= rear_; i++)
cout << setw(2) << queue_[i] << " ";
// rear와 front 사이 사용하지 않은 공간
for (int i = rear_ + 1; i <= front_; i++)
cout << " * ";
// front 뒤 내용물
for (int i = front_ + 1; i < capacity_; i++)
cout << setw(2) << queue_[i] << " ";
cout << endl << endl;
} else // 비었을 경우
{
for (int i = 0; i < capacity_; i++)
cout << " - ";
cout << endl << endl;
}
}
void SetDebugFlag(bool flag) { print_debug_ = flag; }
protected: // 뒤에서 상속해서 사용
T *queue_; // array for queue elements
int front_ = 0; // 시작 인덱스보다 하나 작은 값
int rear_ = 0; // 마지막 인덱스 (첫 값은 1에 추가)
int capacity_; // 빈 칸을 하나 둬야 하기 때문에 필요 메모리는 최대 저장량 + 1
bool print_debug_ = false;
};