Deque 자료구조를 자바로 구현하기 /deque 메서드들 차이점 알아보기 : Programming Story

1. Java deque

우리가 흔히 접하는 자료구조에는 Stack과 Queue가 있다.

Stack은 Last In, First Out의 구조로 요소를 추가할 때는 뒷부분에 추가하고 요소를 뺄 때는 앞부분부터 제거되는 구조이다. 반면 Queue는 First In, First Out의 구조로 요소를 추가할 때 앞부분에 추가하고 뺄 때도 마찬가지로 앞부분부터 제거되는 구조이다.

반면, 우리가 코딩문제를 풀다 보면 상황에 따라 뒷부분과 앞부분에 모두 요소를 추가하고 싶을 때가 생길 수 있다. 그럴 때는 deque이라는 자료구조를 사용하면 되는데 deque은 특정 메서드를 사용하여 deque의 앞부분, 뒷부분에 모두 다 요소를 추가하고 제거할 수 있어서 매우 편리하다.

2. deque 메소드

그렇다면 Java에서 제공하는 deque관련 유용한 메서드를 살펴보고 각각이 어떤 식으로 다른지 살펴보자.

1) 요소를 넣고 싶을때

add() : deque의 끝부분에 요소를 추가, 성공시 true, 실패 시 Exception 일으킴
addLast(): 위의 add()와 마찬가지로 deque의 끝부분에 요소를 추가. return 값이 없으며 실패 시 Exception을 일으킴
addFirst(): deque의 첫 부분에 요소를 추가. return 값이 없으며 실패 시에만 Exception을 일으킴

<offer series> : 전반적으로 add 와 비슷한 기능을 제공하나 성공/실패에 따라서 true/false값을 return 한다는 점이 차이점이다.

offer(): deque의 끝부분에 요소를 추가. 성공시 true를 return, 실패 시 false를 return
offerLast(): 위의 offer()와 같음 (deque의 끝부분에 요소를 추가)성공시 true를 return, 실패 시 false를 return)
offerFirst(): deque의 처음부분에 요소를 추가. 성공시 true를 return, 실패시 false를 return함

2) 요소를 제거하고 싶을 때

<remove series>: 제거된 값을 반환하고, 실패 시에 Exception을 일으킴

remove(): deque의 첫 요소 삭제. 위의 add와 offer의 경우 Last와 First가 안붙으면 디폴트는 끝부분에 추가하는 것이었는데 remove의 경우에는 첫 요소를 삭제한다.
removeFirst(): deque의 첫 요소 삭제
removeLast(): deque의 마지막 요소 삭제

<poll series>: 기본적으로 제거된 값을 반환한다는 점에서 remove 와 비슷하지만, 실패 시에 null을 return한다는 점이 차이점이다.

poll(): deque 의 첫 요소 삭제
pollFirst(): deque의 첫 요소 삭제
pollLast(): deque의 마지막 요소 삭제

3) 해당 위치의 요소를 확인하고 싶을 때 : 제거는 하지 않음

<get series>: 해당 값을 return 하고 실패 시 Exception을 발생시킴

getFirst(): deque의 첫값을 return 함 ( element() 메서드도 똑같은 기능 제공)
getLast(): deque 의 마지막 값을 return 함

<peek series>: 기본적으로 해당 값을 반환한다는 점에서 get과 비슷하지만, 실패 시에 null을 return한다는 점이 차이점이다.

peek(): deque의 첫 값을 return 함
peekFirst(): deque의 첫 값을 return 함 (peek()과 같음)
peekLast(): deque의 마지막 값을 return 함

3. Java ArrayDeque 사용법

만약 Java로 정수로 구성된 deque을 구현하고 싶다면

ArrayDeque<Integer> d = new ArrayDeque<Integer>();

위처럼 ArrayDeque을 준비하고 앞에서 소개된 메서드들을 사용하여 필요한 기능을 구현해주면 된다.

4. ArrayDeque 구현 문제

ArrayDeque을 사용하여 구현한 문제를 소개하고 마치겠다.

https://www.programmingstory.com/2024/03/13549-3-bfs-arraydeque.html

deque이 실제 문제에서 어떻게 활용되는지 궁금하면 위의 링크로 들어가보면 된다.