덱(deque)

deque의 정의

• 덱은 double ended queue의 줄임말로 queue 인터페이스를 확장한 것이다.
• 자료의 입출력(추가, 삭제)을 양 끝에서 할 수 있다는 특징을 가지고 있다.
• 인덱스로 요소에 액세스, 삽입, 제거를 허용하지 않는다!
• 필요한 모든 스택 작업을 제공하기 때문에 편리하다.

+

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque.

공식 문서에 있는 내용으로, deque가 LIFO인 stack으로 사용이 가능하니 레거시에 존재하는 stack 클래스보다 우선적으로 사용할 것을 권장하고 있다! == Deque의 구현체인 ArrayDeque를 사용하라는 뜻

stack보다는 deque인 이유?

1. stack은 vector를 상속받았다
2. vector는 특정상황(단일 스레드 실행, 단순 Iterator 탐색...)에서 효율적이지 않다!
   1. 모든 작업에 Lock이 사용되기 때문에 단일 스레드 실행 성능이 저하된다

deque의 시간 복잡도

삽입/삭제(원소를 앞/뒤에 삽입 또는 삭제하는 경우): O(1)

조회: O(n)

java에서의 deque

어떻게 저장이 되는걸까?

• deque의 element가 저장되는 배열.
• element가 없는 셀은 항상 null이다.
• 배열에는 하나 이상의 null(꼬리 부분)이 있다.

• array 안에서 circular하게 데이터를 저장한다.
• 배열이 다 찼다면, grow()를 통하여 배열의 크기를 늘린다.
• 이 과정에서 head와 tail이 로직에 맞게 변경된다.

단순한데 구현 참 잘했다..!