자료구조 - 큐
[큐 (Queue)]
큐는 FIFO(First In, First Out) 방식으로 작동하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 큐는 두 개의 포인터(front와 rear)를 사용하여 데이터의 삽입과 삭제를 관리합니다.
front 는 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킵니다.
큐는 순서가 중요한 작업들을 처리할 때 유용합니다. 주로 프로세스 관리, 네트워크 패킷 처리, 넓이 우선 탐색(BFS) 알고리즘 등에 사용됩니다.
[큐의 추상 자료형(ADT)]
큐는 다음과 같은 연산들로 추상화할 수 있습니다.
<is_empty> : 큐가 비어있으면 TRUE, 아니면 FALSE 를 반환합니다.
is_empty(q) ::=
if(size == 0) return TRUE;
else return FALSE;
<is_full> : 큐가 가득 차있으면 TRUE, 아니면 FALSE 를 반환합니다.
is_full(q) ::=
if(size == max_size) return TRUE;
else return FALSE;
<enqueue> : 큐에 요소를 삽인하는 연산입니다.
enquque(q, e) ::=
if( is_full(q) ) queue_full 오류;
else q의 끝에 e를 추가합니다.
<dequeue> : 큐의 맨 앞 요소를 삭제하는 연산입니다.
dequeue(q) ::=
if( is_empty(q) ) queue_empty 오류;
else q의 맨 앞에 있는 요소를 제거하여 반환합니다.
[큐의 장점과 단점]
장점
- FIFO 방식으로 순서가 보장됩니다.
- 삽입과 삭제가 O(1) 시간 복잡도를 가집니다.
단점
- 크기가 고정되어 있으면 공간 낭비가 발생할 수 있습니다.
- 동적 배열로 구현하지 않으면 크기 변경이 어렵습니다.
[큐의 연산]
큐의 삽입 연산은 rear 값을 증가시키고 자료를 삽입하고, 삭제 연산은 front 를 증가시키고 자료를 삭제합니다.
rear와 front 는 plus 연산만 가능합니다.
① createQueue(4);
② addQueue(queue, 'A');
③ addQueue(queue, 'B');
④ addQueue(queue, 'C');
⑤ deleteQueue(queue);
⑥ deleteQueue(queue);
⑦ deleteQueue(queue);
⑧ addQueue(queue, 'D');
큐의 예제 코드
#include <iostream>
#include <queue>
int main()
{
std::queue<int> q; // 큐 생성
q.push(1); // 큐에 1 삽입
q.push(2); // 큐에 2 삽입
q.push(3); // 큐에 3 삽입
// 큐가 비어있지 않은 동안 반복
while (!q.empty())
{
std::cout << q.front() << " "; // 큐의 front 요소 출력
q.pop(); // 큐에서 front 요소 제거
}
return 0;
}
[원형 큐(Circular Queue)]
원형 큐는 일반 큐와 달리, 끝(front)과 끝(rear)이 연결되어 있는 구조입니다. 큐의 끝에 도달하면 처음으로 돌아가서 사용할 수 있습니다.
기존의 선형 큐는 front와 rear의 값이 증가만 하기 때문에 언젠가 배열의 끝에 도달하게 되고 배열의 앞부분이 비어있어도 사용하지 못한다는 점에서 약점이 있었습니다.
원형 큐는 그러한 큐의 단점을 보완하고 공간을 효율적으로 사용하기 위해 고안되었습니다.
주로 고정된 크기의 버퍼를 사용해야하거나 네트워크 트래픽 관리, 멀티태스킹 시스템에서 테스크 관리 시 사용합니다.
[원형 큐의 삽입, 삭제 알고리즘]
기존의 큐는 front와 rear를 증가하기만 하면 됐고, 배열의 크기가 정해지지 않았습니다.
하지만 원형 큐는 배열의 크기가 정해져있고 front 와 rear의 값이 증가는 하지만 배열의 끝에 도달하면 값이 변해야 합니다.
나머지 연산자(%)를 사용하여 쉽게 구현이 가능합니다.
enqueue 알고리즘
enqueue(Q,x) :
rear<-(rear+1) % MAX_QUEUE_SIZE;
Q[rear]<-x;
dequeue 알고리즘
dequeue(Q):
front<-(front+1) % MAX_QUEUE_SIZE;
return Q[front];
[원형 큐의 장점과 단점]
장점
- 고정된 크기 내에서 메모리를 효율적으로 사용합니다.
- 원형 배열 구조로 인해, 공간 낭비가 없습니다.
단점
- 구현이 다소 복잡할 수 있습니다.
- 큐가 가득 찬 상태와 비어 있는 상태를 구분하기 위해 하나의 공간을 비워두어야 합니다.
원형 큐의 예제 코드
#include <iostream>
#define MAX_SIZE 5 // 원형 큐의 최대 크기 정의
class CircularQueue
{
private:
int front; // 큐의 front 포인터
int rear; // 큐의 rear 포인터
int arr[MAX_SIZE]; // 원형 큐 배열
public:
CircularQueue() : front(-1), rear(-1) {} // 초기 생성자
// 큐가 가득 찼는지 확인
bool isFull()
{
return (front == (rear + 1) % MAX_SIZE);
}
// 큐가 비어있는지 확인
bool isEmpty()
{
return (front == -1);
}
// 큐에 요소를 추가
void enqueue(int value)
{
if (isFull())
{
std::cout << "Queue is Full\n";
return;
}
rear = (rear + 1) % MAX_SIZE; // rear 포인터 이동
arr [rear] = value; // 새로운 값 삽입
if (front == -1) front = 0; // 첫 요소 삽입 시 front 초기화
}
// 큐에서 요소 제거
void dequeue()
{
if (isEmpty())
{
std::cout << "Queue is Empty\n";
return;
}
if (front == rear)
{
front = rear = -1; // 마지막 요소 제거 시 포인터 초기화
}
else
{
front = (front + 1) % MAX_SIZE; // front 포인터 이동
}
}
// 큐의 front 요소를 반환
int Front()
{
if (isEmpty())
{
std::cout << "Queue is Empty\n";
return -1;
}
return arr[front];
}
};
int main()
{
CircularQueue cq; // 원형 큐 생성
cq.enqueue(1); // 원형 큐에 1 삽입
cq.enqueue(2); // 원형 큐에 2 삽입
cq.enqueue(3); // 원형 큐에 3 삽입
cq.enqueue(4); // 원형 큐에 4 삽입
std::cout << "Front element: " << cq.Front() << "\n"; // 원형 큐의 front 요소 출력
cq.dequeue(); // 원형 큐에서 요소 제거
cq.enqueue(5); // 원형 큐에 5 삽입
// 큐가 비어있지 않은 동안 반복
while (!cq.isEmpty())
{
std::cout << cq.Front() << " "; // 큐의 front 요소 출력
cq.dequeue(); // 큐에서 front 요소 제거
}
return 0;
}