위키원
"큐"의 두 판 사이의 차이
(→선형 큐(Linear Queue) =) |
|||
| 18번째 줄: | 18번째 줄: | ||
== 참고자료 == | == 참고자료 == | ||
| − | + | * 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일 | ||
== 같이 보기 == | == 같이 보기 == | ||
* [[자료구조]] | * [[자료구조]] | ||
{{데이터|검토 필요}} | {{데이터|검토 필요}} | ||
2020년 8월 12일 (수) 09:05 판
큐(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년 9월 29일
- Lkt_Programmer,〈원형 큐 (Circular Queue) 자료 구조〉, 2017년 10월 13일
- syunyun,〈원형 큐〉, 2019년 12월 20일
같이 보기
