위키원
"큐"의 두 판 사이의 차이
잔글 (→같이 보기) |
|||
| 1번째 줄: | 1번째 줄: | ||
'''큐'''(queue)는 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이며, 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In First Out) 구조이다.<ref name='queue'>Mr.lee,〈[https://lee-mandu.tistory.com/462 자료 구조의 개념 정리]〉, 2019년 9월 10일</ref> | '''큐'''(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> | ||
| + | === 덱(Deque) === | ||
| + | * '''덱(Deque)''' : Double-ended queue의 약자로, 양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조이다. 큐는 push, pop을 할 수 있는 위치가 한 방향으로 고정되어 있지만, 덱은 앞에서도 push, pop, 뒤에서도 push, pop이 모두 가능하다.<ref name='deque'>ldgeao99,〈[https://ldgeao99.tistory.com/249 자료구조 덱]〉, 2019년 4월 23일 </ref> | ||
| + | ==== 입/출력 방식 ==== | ||
| + | [[파일:덱_입출력.png]]<ref name='deque'></ref><br> | ||
2020년 8월 12일 (수) 09:03 판
큐(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]
덱(Deque)
- 덱(Deque) : Double-ended queue의 약자로, 양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조이다. 큐는 push, pop을 할 수 있는 위치가 한 방향으로 고정되어 있지만, 덱은 앞에서도 push, pop, 뒤에서도 push, pop이 모두 가능하다.[5]
입/출력 방식
각주
- ↑ 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일
- ↑ 5.0 5.1 ldgeao99,〈자료구조 덱〉, 2019년 4월 23일
참고자료
같이 보기
