Queue

큐 기초

FIFO(First - In - First - Out)

먼저 들어온 데이터가 먼저 나가는 구조

 

간단한 예로는 매표소에서 표를 사기 위해 늘어선 줄을 예로 들어 설명할 수 있음

줄에 있는 사람들 중 가장 앞에 있는 사람(즉 가장 먼저 온 사람)이 가장 먼저 표를 살 수 있음, 반면 나중에 온 사람들은 줄의 맨 뒤에 서야 함

 

Queue에서 데이터 추가와 삭제는 뒤에서 새로운 데이터가 추가되고 앞에서는 데이터가 하나씩 삭제되는 구조를 가지고 있음

 

Queue를 설명하면서 Stack을 빼놓을 수 없기 때문에, 다른 점을 이야기 하면 Stack의 경우 삽입과 삭제가 같은 쪽에서 일어나지만 Queue에서는 삽입과 삭제가 다른 쪽에서 발생.

Queue에서 삽입이 일어나는 곳을 Rear, 삭제가 일어나는 곳을 Front라고 한다.

 

enqueue, dequeue를 사용한 간단한 예

Enqueue(3)	큐에 3 추가
Enqueue(5)	큐에 5 추가
Enqueue(7)	큐에 7 추가
Dequeue()	큐 맨 앞 부분 삭제(3)
Dequeue()	큐 맨 앞 부분 삭제(5)

 

선형 큐

Queue도 Stack과 마찬가지로 구현 방법은 다양하지만 가장 간단한 1차원 배열을 쓰는 방법을 설명

front는 Queue의 첫 번째 요소를 가리키고, rear는 Queue의 마지막 요소를 가리킴

front와 rear의 초기값은 -1

 

데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장

삭제할 때도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제

위와 같은 큐를 Linear Queue라고 한다.

 

* Linaer Queue의 문제점

front와 rear의 값이 계속 증가만 하기 때문에 언젠가 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지 못한다는 점

 

원형 큐

앞서 말한 Linear Queue의 문제점인 배열의 앞부분이 비어 있더라도 사용하지 못한다는 점을 해결하는 방법으로 소개

주기적으로 모든 요소들을 왼쪽으로 이동

 

* Linear Queue에서 오른쪽에 몰려 있을 때, 왼쪽으로 옮기려면 시간이 많이 듦

 

이럴 때, 배열을 Linear로 생각하지 말고 원형으로 생각해서 해결

= front와 rear의 값이 배열의 끝인 Max_queue_size-1에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것

= 배열이 원형으로 처음과 끝이 연결되어 있다고 생각하는 것

= 여기서 실제 배열이 원형으로 변화되는 것은 아님, 그냥 개념상으로 원형으로 배열의 인덱스를 변화시켜주는 것

 

원형 큐에서는 front와 rear의 개념이 약간 변형됨

1) 먼저 초기값은 -1이 아닌 0

2) front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킴

3) 삽입 시에는 rear가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입

4) 삭제 시에도 front가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제

 

front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타냄

원형 큐에서 하나의 자리는 항상 비워둠 ----> 포화 상태와 공백 상태를 구별하기 위해서

 

원형 큐에서 만약 front==rear이면 공백 상태가 되고 만약 front와 rear보다 하나 앞에 있으면 포화상태