Stack, Queue, Deque

Stack

• LIFO(Last In First Out): 후입 선출

성능이 좋지 않아 사용하지 않습니다. 대신 Deque를 사용하면 됩니다.

Queue

• FIFO(First In First Out): 선입 선출

Deque

• Stack, Queue의 기능을 모두 사용할 수 있는 자료구조

• offerFirst(), push(): 앞에 추가
• offerLast(), offer(): 뒤에 추가
• pollFirst(), pop(), poll(): 앞에서 꺼냄
• pollLast(): 뒤에서 꺼냄

상속 구조

ArrayDeque vs LinkedList

• ArrayDeque는 특별한 원형 큐 자료를 사용
• 둘 다 앞 뒤 입력 모두 O(1)의 성능을 제공
• 이론적으로는 LinkedList가 삽입, 삭제가 자주 발생할 때 더 효율적일 수 있으나, 실제론 배열을 사용하는 ArrayDeque가 더 나은 성능을 보임

ArrayDeque가 LinkedList보다 거의 모든 면에서 성능이 좋기 때문에 ArrayDeque를 사용하면 됩니다.

참고

• https://www.inflearn.com/course/김영한의-실전-자바-중급-2