큐 편집하기

'''큐'''(queue)는 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 [[자료구조]]이다. 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In First Out) 구조이다.<ref name='queue'>Mr.lee,〈[https://lee-mandu.tistory.com/462 자료 구조의 개념 정리]〉, 2019년 9월 10일</ref>

== 선형 큐(Linear Queue) ==
* '''선형 큐(Linear Queue)''' : 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공한다.<ref name='enqueue_1'>Lkt_Programmer,〈[https://lktprogrammer.tistory.com/47?category=676210 선형 큐(Linear Queue) 자료 구조]〉, 2017년 9월 29일 </ref>
=== 입력(Enqueue) ===
[[파일:선형_큐.PNG]]<ref name='enqueue_1'></ref>
=== 출력(Dequeue) ===
[[파일:선형큐_dequeue.png]]<ref name='enqueue_1'></ref>

== 원형 큐(Circular Queue) ==
* '''원형 큐(Circular Queue)''' : 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조이다. 선형큐의 문제점은 rear이 가리키는 포인터가 배열의 마지막 인덱스를 가리키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없는데, 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다.<ref name='circular_queue'>Lkt_Programmer,〈[https://lktprogrammer.tistory.com/59?category=676210 원형 큐 (Circular Queue) 자료 구조]〉, 2017년 10월 13일 </ref>
=== 입력(Enqueue) ===
rear값을 1 증가시키면서 해당 인덱스에 데이터를 삽입시킨다. 이때, (rear+1) % array.length 조건을 통해서 원형큐가 꽉찬 상태인지 확인한다. 예를들어, 큐의 사이즈는 4이고 enqueue(1),enqueue(2),enqueue(3)을 수행하고 euqueue(4)를 수행하면 (3+1) % 4 == front 이므로 enqueue를 수행할 수 없다.<ref name='circular_queue2'>syunyun,〈[https://syundev.tistory.com/36 원형 큐]〉, 2019년 12월 20일 </ref>

=== 출력(Dequeue) ===
front의 포인터를 1 증가시면서 데이터를 제거한다.<ref name='circular_queue2'></ref>

{{각주}}

== 참고자료 ==
* Lkt_Programmer,〈[https://lktprogrammer.tistory.com/47?category=676210 선형 큐(Linear Queue) 자료 구조]〉, 2017년 9월 29일
* Lkt_Programmer,〈[https://lktprogrammer.tistory.com/59?category=676210 원형 큐 (Circular Queue) 자료 구조]〉, 2017년 10월 13일 
* syunyun,〈[https://syundev.tistory.com/36 원형 큐]〉, 2019년 12월 20일 
== 같이 보기 ==
* [[덱]]
* [[스택]]
* [[자료구조]]

{{데이터|검토 필요}}