해시넷
"큐"의 두 판 사이의 차이
잔글 |
|||
| (사용자 2명의 중간 판 4개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
| − | '''큐'''(queue)는 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 | + | '''큐'''(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) == |
* '''선형 큐(Linear Queue)''' : 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공한다.<ref name='enqueue_1'>Lkt_Programmer,〈[https://lktprogrammer.tistory.com/47?category=676210 선형 큐(Linear Queue) 자료 구조]〉, 2017년 9월 29일 </ref> | * '''선형 큐(Linear Queue)''' : 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공한다.<ref name='enqueue_1'>Lkt_Programmer,〈[https://lktprogrammer.tistory.com/47?category=676210 선형 큐(Linear Queue) 자료 구조]〉, 2017년 9월 29일 </ref> | ||
=== 입력(Enqueue) === | === 입력(Enqueue) === | ||
| 7번째 줄: | 7번째 줄: | ||
=== 출력(Dequeue) === | === 출력(Dequeue) === | ||
[[파일:선형큐_dequeue.png]]<ref name='enqueue_1'></ref> | [[파일:선형큐_dequeue.png]]<ref name='enqueue_1'></ref> | ||
| + | |||
== 원형 큐(Circular Queue) == | == 원형 큐(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> | * '''원형 큐(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> | ||
| 14번째 줄: | 15번째 줄: | ||
=== 출력(Dequeue) === | === 출력(Dequeue) === | ||
front의 포인터를 1 증가시면서 데이터를 제거한다.<ref name='circular_queue2'></ref> | front의 포인터를 1 증가시면서 데이터를 제거한다.<ref name='circular_queue2'></ref> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{각주}} | {{각주}} | ||
== 참고자료 == | == 참고자료 == | ||
| + | * Lkt_Programmer, 〈[https://lktprogrammer.tistory.com/47?category=676210 선형 큐(Linear Queue) 자료 구조]〉, 2017-09-29 | ||
| + | * Lkt_Programmer, 〈[https://lktprogrammer.tistory.com/59?category=676210 원형 큐 (Circular Queue) 자료 구조]〉, 2017-10-13 | ||
| + | * syunyun, 〈[https://syundev.tistory.com/36 원형 큐]〉, 2019-12-20 | ||
== 같이 보기 == | == 같이 보기 == | ||
| + | * [[덱]] | ||
| + | * [[스택]] | ||
* [[자료구조]] | * [[자료구조]] | ||
{{데이터|검토 필요}} | {{데이터|검토 필요}} | ||
2020년 8월 12일 (수) 10:07 기준 최신판
큐(queue)는 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이다. 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In First Out) 구조이다.[1]
목차
선형 큐(Linear Queue)[편집]
- 선형 큐(Linear Queue) : 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공한다.[2]
입력(Enqueue)[편집]
출력(Dequeue)[편집]
원형 큐(Circular Queue)[편집]
- 원형 큐(Circular Queue) : 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조이다. 선형큐의 문제점은 rear이 가리키는 포인터가 배열의 마지막 인덱스를 가리키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없는데, 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다.[3]
입력(Enqueue)[편집]
rear값을 1 증가시키면서 해당 인덱스에 데이터를 삽입시킨다. 이때, (rear+1) % array.length 조건을 통해서 원형큐가 꽉찬 상태인지 확인한다. 예를들어, 큐의 사이즈는 4이고 enqueue(1),enqueue(2),enqueue(3)을 수행하고 euqueue(4)를 수행하면 (3+1) % 4 == front 이므로 enqueue를 수행할 수 없다.[4]
출력(Dequeue)[편집]
front의 포인터를 1 증가시면서 데이터를 제거한다.[4]
각주[편집]
- ↑ Mr.lee,〈자료 구조의 개념 정리〉, 2019년 9월 10일
- ↑ 2.0 2.1 2.2 Lkt_Programmer,〈선형 큐(Linear Queue) 자료 구조〉, 2017년 9월 29일
- ↑ Lkt_Programmer,〈원형 큐 (Circular Queue) 자료 구조〉, 2017년 10월 13일
- ↑ 4.0 4.1 syunyun,〈원형 큐〉, 2019년 12월 20일
참고자료[편집]
- Lkt_Programmer, 〈선형 큐(Linear Queue) 자료 구조〉, 2017-09-29
- Lkt_Programmer, 〈원형 큐 (Circular Queue) 자료 구조〉, 2017-10-13
- syunyun, 〈원형 큐〉, 2019-12-20
같이 보기[편집]
