Ahn9807: 새 문서: 분류: 자료 구조 ==개요== '''큐'''는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO구조로 저장하는 형식을 말한다. 영어 단어는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는...

2023-02-25T11:09:43Z

새 문서: 분류: 자료 구조 ==개요== '''큐'''는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO구조로 저장하는 형식을 말한다. 영어 단어는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는...

새 문서

[[분류: 자료 구조]]

==개요==
'''큐'''는 [[컴퓨터]]의 기본적인 [[자료 구조]]의 한가지로, 먼저 집어 넣은 [[데이터]]가 먼저 나오는 [[FIFO]]구조로 저장하는 형식을 말한다. 영어 단어는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 [[스택]]과는 반대되는 개념이다.

[[프린터]]의 [[출력]] 처리나 [[윈도 시스템]]의 메시지 처리기, [[프로세스 관리]] 등 데이터가 [[입력]]된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

== 용어 ==
큐는 put(insert)와 get(delete)을 이용하여 구현된다. put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가리킨다! front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다.
또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 [[오버플로|오버플로우]](Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 [[언더플로|언더플로우]](Underflow)라고 한다.

== 종류 ==
큐에는 선형과 환형이 있다.
=== 선형 ===
막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.

다음은 선형 큐의 작동 방식이다.

DATA : A B C D E

<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="첫 번째 과정"
|+ ENQ(A)
|-
| 
|-
| 
|-
| 
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="두 번째 과정"
|+ENQ(B)
|-
| 
|-
| 
|-
|B
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="세 번째 과정"
|+ ENQ(C)
|-
| 
|-
|C
|-
|B
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="네 번째 과정"
|+ DEQ(A)
|-
| 
|-
|C
|-
|B
|-
| 
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="다섯 번째 과정"
|+ ENQ(D)
|-
|D
|-
|C
|-
|B
|-
| 
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="마지막 과정"
|+ DEQ(B)
|-
|D
|-
|C
|-
| 
|-
| 
|-
|}
</div>
<div style="clear:both;"></div>

=== 환형 큐 ===
선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.
<br>
원형 큐라고도 한다.<br>
DATA : A B C D E

<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="첫 번째 과정"
|+ ENQ(A)
|-
| 
|-
| 
|-
| 
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="두 번째 과정"
|+ ENQ(B)
|-
| 
|-
| 
|-
|B
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="세 번째 과정"
|+ ENQ(C)
|-
| 
|-
|C
|-
|B
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="네 번째 과정"
|+ ENQ(D)
|-
|D
|-
|C
|-
|B
|-
|A
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="다섯 번째 과정"
|+ DEQ(A)
|-
|D
|-
|C
|-
|B
|-
| 
|-
|}
</div>
<div style="float:left;">
{| class="wikitable" style="width:67px; text-align:center;" summary="마지막 과정"
|+ ENQ(E)
|-
|D
|-
|C
|-
|B
|-
|E
|-
|}
</div>
<div style="clear:both;"></div>

== 연결 리스트로 구현한 큐 (링크드 큐) ==
연결 리스트로 구현한 큐는 [[연결 리스트]]를 사용한 것으로써, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징이다. 필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.

== 관련 항목 ==
* [[스택]]

큐 - 편집 역사