큐(Queue)란 무엇인가?

출처 : https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg

SW Expert Academy

---

Queue는 선입선출(FIFO) 구조이다.

서비스 대기열(버퍼)같은 경우에 사용하게 된다.

선입선출 구조이기 때문에 앞쪽을 나타내는 Front와 뒤쪽을 나타내는 Rear가 있다.

 

버퍼 : 일시적으로 그 데이터를 보관하는 메모리 영역

 

Queue에서 필요한 주요 동작은 아래와 같다.

enQueue() : 큐에 데이터를 넣는 과정, Rear가 커진다. Push로 만들수도 있지만 스택과 혼돈이 생길수도 있으므로 지양한다. deQueue() : 큐에서 데이터를 빼는 과정, Front가 커진다. Pop으로 만들수도 있지만 위아 마찬가지로 지양한다. isEmpty() :  큐가 비어있는지 확인한다. isFull() : 큐가 꽉 차있는지 확인한다. peek() : 앞에 있는 원소를 삭제하지 않고 반환한다.

 

큐의 종류는 아래와 같다.

선형큐 : 1차원 배열을 이용한 큐 (큐의 크기가 배열의 크기가 되는 구조이다.) front와 rear를 이용하여 공백과 포화상태를 판단할 수 있다. front = rear인 경우 공백상태이다. rear = n - 1 (n은 배열크기이다.)   선형큐의 문제점 enQueue와 Dequeue가 반복되면 앞부분에 비어있는 공간이 있음에도 front와 rear가 뒤로가 포화상태 혹은 삽입불가 상태가 된다. 고정된 크기를 가지게 되므로 메모리 낭비가 될 수 있다.

 

원형큐 : 메모리 공간을 아끼기 위해 이론적으로 원형적인 큐(배열의 처음과 끝이 연결되어 있다고 가정)를 만들어 사용   공백과 포화상태 구분을 위해 front가 있는 자리는 사용하지 않고 빈자리로 둔다. 따라서 front가 잇는 자리는 데이터가 비어있다고 생각한다. rear가 마지막 부분에 있다면 mod 연산을 이용하여 앞으로 보낸다.(Index의 순환) front 와 rear가 같다면 공백상태이다. rear 의 다음칸이 front라면 full 상태이다.   선형큐와 마찬가지로 비어있는 공간이 있게되므로 메모리 낭비가 된다.

 

연결 리스트(Linked List)를 이용한 큐 : 연결리스트를 이용하여 큐처럼 이용한다. front는 첫번째 노드를 가리킨다. rear는 마지막 노드를 가리킨다. 각각의 노드는 큐의 원소이다. 초기 혹은 공백상태는 front와 rear가 null이다. front와 rear는 주소값을 가지고 있다.(포인터) 빈 공간이 생기지 않으므로 메모리를 아낄 수 있다. 대신 메모리를 잡는 시간이라던가, 구현 난이도가 있다.

 

우선순위 큐(Priority Queue): 우선순위를 이용하여 우선순위가 높은 순서대로 나가게 된다.(FIFO가 아님) 우선순위는 큰 수로 표현하거나 작은 수로 표현할 수 있다. 시뮬레이션 시스템, 네트워크 트래픽제어, 운영체제의 테스크 스케줄링 예시 : 병원에 접수하고 대기중인데 교통사고가 나서 응급환자가 왔다. 이때 응급환자를 먼저 보게된다.   배열을 이용한 구현 : 가장 앞에 높은 우선순위의 원소가 있다. 삽입시 우선순위를 비교하여 적절한 위치에 삽입하게 된다. 삽입, 삭제시 원소의 재배치가 발생하므로 소요되는 시간이나 메모리 낭비가 크다. => 따라서 라이브러리를 사용하거나 Heap 자료구조를 이용하여 구현한다.