자료구조 : 큐

참고 문헌 :

parkdream.tistory.com/102

[C] 큐(Queue)

 

chanhuiseok.github.io/posts/algo-26/

알고리즘 - 큐(Queue) : 선형 큐와 원형 큐

 

ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)#%EC%84%A0%ED%98%95

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

velog.io/@holicme7/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Prioirity-Queue-mbk48cz764

우선순위 큐(Prioirity Queue) (1) - 최대 힙 이용

---

1. 큐 (Queue)

1.1 정의 : 기본 자료구조 중 하나로, 먼저 넣은 데이터가 먼저 나오는 FIFO(First In Fist Out) 구조를 가집니다. 

 

1.2 종류 : 선형 큐, 순환 큐, 우선순위 큐

 

1.3 용어 : 

- enqueue : 큐에서 데이터를 저장

- dequeue : 큐에서 데이터를 제거

- front : dequeue 할 데이터의 index를 저장합니다.

- rear : enqueue 할 데이터의 index를 저장합니다.

 

enqueue(1) -> enqueue(2) -> dequeue() 했을 때 front과 rear의 값 변경은 다음과 같습니다.

< front 과 rear의 값 변경 >

---

2. 선형 큐 (Linear Queue)

- 기본적인 Queue 형태로 막대 모양입니다. 주로 배열을 사용하여 구현합니다.

- dequeue 하여 생겨난 공간을 사용하기 위해서는 큐에 저장된 데이터를 재 정렬하는 과정을 거쳐야 하는 단점이 존재합니다.

- 위와 같은 단점을 극복하기 위하여 배열이 아닌 링크드 리스트로 구현하거나 원형 큐를 사용합니다.

- rear 값이 큐의 크기이면 큐가 꽉 찼다고 판단하게 됩니다.

- front과 rear가 같은 값이면 스택이 비어있다고 판단하게 됩니다.

 

Ex) 큐의 크기가 5일 때 

enqueue(a) -> dequeue() -> enqueue(a) -> enqueue(b) -> enqueue(c) -> enqueue(d) 수행 후  큐 상태

< 현재 큐 상태 >

현재 상황에서 index = 0은 비어있습니다. 이때 enqueue(e)를 수행하기 위해서 다음과 같이 데이터를 재 정렬을 수행 후에 데이터를 큐에 넣어야 합니다.

< 정렬 후 모습 >

< 데이터 추가 >

선형 큐 구현하기 (C99)

#include<stdio.h>

#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = 0, rear = 0;

int isFull()
{
	return rear == MAX_SIZE ? 1 : 0;
}

int isEmpty()
{
	return front == rear ? 1 : 0;
}

void sortQueue() //데이터 재정렬 
{
	int i = -1;
	for(i = 0; i < rear - front; i++)
		queue[i] = queue[front + i];
		
	front = 0;
	rear = i;
}

void enqueue(int data)
{
	sortQueue();
	if(!isFull())
		queue[rear++] = data;
}

int dequeue()
{
	if(!isEmpty())
		return queue[front++];
}

 

front, 데이터 재정렬 이런 키워드를 강조하기 위하여 작성한 코드입니다.

---

3. 원형 큐 (Circular Queue)

- front가 0이 아닌 상황에서 rear가 n 인 상황에서 enqueue가 진행되면 선형 큐처럼 데이터를 재 정렬하는 것이 아니라 rear = 0으로 하여 index가 0인 곳에 데이터를 추가하는 큐입니다.

- 큐의 시작 index가 0 끝 index가 큐의 크기(n) - 1이 아니라 상황마다 다르게 합니다.

 

Ex) 큐의 크기가 5일 때 

enqueue(a) -> dequeue() -> enqueue(a) -> enqueue(b) -> enqueue(c) -> enqueue(d) 수행 후  큐 상태에서 enqueue(e)를 수행한 모습입니다.

< 순환 큐의 데이터 모습 >

 

- 큐에서 비었는지 확인은 front과 rear가 같은 값이면 큐가 비어있다고 판단하지만 순환 큐에서 표를 보면 enqueue(e)를 큐가 가득 차있어도 front과 rear의 값이 같은 것을 확인할 수 있습니다. 따라서 순환 큐에서는 하나의 빈 공간을 추가하여 front과 rear가 같을 때 비어 있음을 의미하고 rear + 1 = front이면 큐가 가득 참 있다는 것을 의미하게 됩니다.

 

Ex) 큐의 크기가 6일 때 (실제 사용 가능한 크기 5)

enqueue(a) -> dequeue() -> enqueue(a) -> enqueue(b) -> enqueue(c) -> enqueue(d) 수행 후  큐 상태에서 enqueue(e)를 수행한 모습입니다.

< rear과 front 사이에 빈공간 추가 모습 >

이렇게 사용함으로써 큐가 비어있는지 가득 차있는지 판별할 수 있습니다.

 

원형 큐 구현하기 (C99)

#include<stdio.h>
#include<Windows.h>
#define MAX_SIZE 5

int c_queue[MAX_SIZE];
int front = 0, rear = 0;

int isFull()
{
	return (rear + 1) % MAX_SIZE == front ? 1 : 0;
}

int isEmpty()
{
	return front == rear ? 1 : 0;
}

void enqueue(int data)
{
	if(!isFull())
		c_queue[rear++] = data;
	else{
		printf("queue is full!\n");
        exit(1);
	}
	rear %= MAX_SIZE;
}

int dequeue()
{
	if(!isEmpty())
		front = (front + 1) % MAX_SIZE;
	else{
    	printf("queueu is empty!\n");
        exit(1);
	}
	
	return c_queue[front];
}

---

4. 우선순위 큐 (Priority Queue)

- 데이터에 우선순위가 주어져 큐에 들어간 순서에 관계없이 우선순위가 높은 데이터가 나오게 됩니다.

- 우선순위 큐를 구현하는 방법은 배열, 링크드 리스트, 힙이 있습니다. 이 3가지 중 가장 효율 적인 방법은 힙을 사용하여 구현합니다.

- 힙은 완전 이진트리 구조로 빠르게 최댓값, 최솟값 찾도록 만들어진 자료구조입니다.