Queue에 대해서

Queue의 구조는 한쪽에서는 삽입만 일어나고 한쪽에서는 삭제만 하는 자료구조 입니다. 즉, 먼저 들어간 것이 먼저 나오는 FIFO 구조입니다.

Queue 인터페이스를 구현하는 대표적인 두 가지 클래스는 LinkedList와 ArrayDeque입니다.

 

큐를 배열이 아닌 LinkedList로 구현한 이유

 요소의 추가 및 제거 시 기존 배열을 재구성할 필요 없이 노드의 연결만 변경하면 됩니다. 이로 인해 요소의 추가 및 제거(특히, 앞/뒤)가 상수 시간(O(1))에 이루어집니다.

이유가 뭔가하면 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고있고, 요소가 배열에 들어있는 양에 따라 용적(배열 크기)을 줄이거나 늘려주어야 하고, 큐를 선형적인 큐로 구현했을 경우 요소들이 뒤로 쏠리기 때문에 이러한 문제를 효율적으로 극복하고자 원형 형태로 구현하는데 이 구현이 고려해야 할 점도 많고 조금 복잡하다.

하지만 배열 대신 연결리스트로 구현하게 될 경우 위와같은 단점들이 해결된다. 각 데이터들을 노드(node) 객체에 담고 노드 간 서로 연결해주기 때문에 배열처럼 요소 개수에 따라 늘려주거나 줄여줄 필요도 없고 삽입, 삭제 때는 연결 된 링크만 끊어주거나 이어주면 되기 때문에 관리면에서도 편하다. 

LinkedList의 차이점  LinkedList와 ArrayDeque

• ArrayDeque는 null 요소를 허용하지 않는 반면, LinkedList는 null 요소의 삽입이 가능합니다
•  ArrayDeque 클래스는 중간에 요소를 삽입하는 메소드가 없다. 따라서 중간에 요소를 삽입하는 기능이 필요한 경우는 LinkedList를 이용하는 것이 좋다.

 

 

결론

-- 큐의 앞과 뒤에서 빠르게 요소를 추가하고 삭제하는 경우 linkedlist보다 성능이 좋다
-- 중간에 요소를 삽입하거나 삭제하는 메소드 제공하지 않음
-- 큐와 스택의 기능을 모두 제공하면서도 내부 구현이 배열로 이루어져 있어서 빠른 접근 속도를 제공
-- 실제로 문서에서도 linkedlist보다 빠름을 언급