[자료구조] 덱(Deque) - JAVA(자바)

덱(Deque)

 

• Double-Ended Queue의 줄임말이다.
• front에서 삽입, last에서 삭제하는 큐와 달리 front와 last 모두 삽입, 삭제가 가능하다.
  • 덱을 front에서만 삽입,삭제를 하게 하면 스택처럼 사용할 수 있다.
• 삽입, 삭제 연산의 시간복잡도  O(1)이고, index를 통해 요소에 접근할 수 있기 때문에 탐색시에도 O(1)의 시간복잡도를 가진다.
• 삽입, 삭제가 빠른 편이다.
• 크기가 가변적이다.
• 한쪽으로만 입력이 가능한 덱 - 스크롤(Scroll), 한쪽으로만 삭제가 가능한 덱 - 셸프(shelf)
• 덱의 중간 원소의 삽입, 삭제가 어렵다.
• 자바에서 덱은 인터페이스로만 작성되어 있다.

 

 

Deque 생성 (LinkedList로 구현예시)

- 자바에서 Deque은 인터페이스로만 작성되어 있어 Deque 클래스 인스턴스를 생성하기 위해 new Deque()이 아닌 new LinkedList(), new ArrayDeque() 등으로 생성해야 한다.

Deque<Integer> deque = new LinkedList<>();

 

Deque 삽입

• front에 삽입
  • addFirst(): 맨 앞에 데이터를 추가한다. -  용량 초과시  illegalStateException 발생
  • offerFirst(): 맨 앞에 데이터를 추가한다. - 용량 초과시 false, 삽입했다면 true 리턴
  • push(): addFirst()와 동일 - 덱을 스택으로 사용할 때 사용
• last에 삽입
  • addLast(): 맨 뒤에 데이터를 추가한다. - 용량 초과시 illegalStateException 발생
  • add(): addList()와 동일
  • offerLast(): 맨 뒤에 데이터를 추가한다. - 용량 초과시 false, 삽입했다면 true 리턴
  • offer(): offerLast()와 동일

 

Deque 삭제

• front를 삭제
  
  • removeFirst(): 맨 앞의 데이터를 제거한다. - 비어있는데, 삭제한다면 예외 발생
  • remove(): removeFirst()와 동일
  • pollFirst(): 맨 앞의 데이터를 제거한다. - 비어있는데, 삭제한다면 null 리턴
  • poll(): pollFirst()와 동일
  • pop(): removeFirst()와 동일 - 덱을 스택으로 사용할 때 사용
• last를 삭제
  • removeLast(): 맨 뒤의 데이터를 제거한다. - 비어있는데, 삭제한다면 예외 발생
  • pollLast(): 맨 의 데이터를 제거한다. - 비어있는데, 삭제한다면 null 리턴

 

Deque 값 확인 (제거하지 않고 값만 가져오는 메소드)

• front를 확인
  • getFirst(): 맨 앞의 데이터를 가져온다. - 비어있다면 예외 발생
  • peekFirst(): 맨 앞의 데이터를 가져온다. - 비어있다면 null 리턴
  • peek(): peekFirst()와 동일
• last를 확인
  • getLast(): 맨 뒤의 데이터를 가져온다. - 비어있다면 예외 발생
  • peekLast(): 맨 뒤의 데이터를 가져온다. - 비어있다면 null 리턴

 

Deque 값 확인(제거하는 메소드)

• removeFirstOccurrence(Object o): 맨 앞부터 탐색해서 o와 동일한 첫번째 데이터를 삭제한다
• remove(Object o): removeFirstOccurrence()와 동일
• removeLastOccurrence(Object o): 맨 부터 탐색해서 o와 동일한 첫번째 데이터를 삭제한다

 

Deque 특정 데이터 존재 여부

• contain(Object o): o가 있다면 true, 없다면 false 리턴

 

Deque 크기

• size(): 덱의 크기를 리턴