자료구조

BootCamp

[Java] 원형 큐(Queue) 구현하기

안녕하세요 이번에는 선형 큐를 원처럼 이은 원형 큐(Queue)에 대해 알아보겠습니다. 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 선형 큐의 문제점은배열의 가장 앞에 있는 데이터를 꺼내오기 때문에 그 다음 인덱스의 데이터들을 한 칸씩 밀어야 하는 단점이 있습니다. 이 과정은 자료 하나를 꺼낼 때마다 반복문으로 수행되며, O(n)만큼의 시간 복잡도를 요구하므로 상당히 비효율적입니다. 1. 원형 Queue 분석 원형 Queue도 선형 Queue와 마찬가지로 1차원 배열을 사용하여 구현합니다. 하지만 선형 Queue와는 다르게 Shift를 해서 앞으로 밀지 않습니다. 배열을 선형으로 사용하여 삽입을 계속해야 하는 선형 Queue의 데이터를 넣을 때마다 번거로움이 있다는 단점을 해결합니다. 또..

기록하는 개발
'자료구조' 태그의 글 목록