Stack, Queue, Deque

Stack

LIFO 후입선출이다

스택에 값을 넣는건 push 빼는건 pop

Stack은 내부에서 Vector라는 자료 구조를 사용한다 옛날에 개발된건데 하위호환을 위해 놔둔거다 지금은 Deque를 사용하면 된다.

 

Queue

FIFO 선입선출이다

큐에 값을 넣는건 offer 빼는건 poll

Queue인터페이스는 Collection의 자식이다

Queue의 대표 구현체는 ArrayDeque, LinkedList가 있다

 

Deque

Double Ended Queue의 약자다 양 끝에서 요소를 추가하거나 제거할 수 있다. 큐와 스택으로 둘 다 활용이 가능하다

offerFirst() : 앞에 추가

offerLast() : 뒤에 추가

pollFirst() : 앞에서 꺼냄

pollLast() : 뒤에서 꺼냄

Deque의 대표적 구현체는 ArrayDeque, LinkedList가 있음

ArrayDeque가 링크드리스트보다 모든면에서 빠름

100만 건 입력 어레이덱 110ms 링크드리스트 480ms

100만 건 조회 어레이덱 9ms 링크드리스트 20ms

둘의 차이는 어레이리스트 링크드리스트의 차이와 비슷하다

어레이덱은 배열을 링크드리스트는 동적 노드 링크를 사용함

어레이덱은 특별한 원형 큐 자료구조를 사용하는데 앞,뒤 입력 모두 O(1)의 성능을 제공한다

링크드리스트도 앞,뒤 입력 모두 O(1)이다

이론적으로 링크드리스트가 삽입 삭제가 자주 발생할때 저 좋읈수도 있지만 메모리 접근 패턴, cpu 캐시 최적화등을 고려할 때 어레이덱이 실제로 더 나은 성능을 보여주는 경우가 많음

데크를 스택으로 사용할 때 push를 호출하면 앞에서 입력하고 pop을 호출하면 앞에서 꺼낸다

데크를 큐로 사용할 때 offer() 호출하면 뒤에서 입력한다 poll()을 호출하면 앞에서 꺼낸다

데크는 큐 인터페이스의 자식이기 때문에 단순히 큐의 기능만 필요하면 큐 인터페이스를 사용하고 더 많은 기능이 필요하면 데크 인퍼페이스를 사용하면 됨 구현체로는 성능 빠른 어레이 데크 ㄱㄱ