스택/큐를 공부하고 있었는데, 강사님께서 스택/큐 이런 거 그냥 다 Deque로 구현하라고 말씀하셨다.
왜 그렇게 말씀하셨을까?
오늘은 강사님께서 왜 그렇게 말씀하셨는지, 그 이유를 알아보도록 하겠다.
Deque, 스택과 큐의 만능 해결사!
Deque는 "양쪽 끝에서 데이터를 넣고 뺄 수 있는 큐"라는 뜻입니다.
Deque의 장점
- 하나로 두 가지 기능: Deque는 스택(LIFO)처럼도, 큐(FIFO)처럼도 사용할 수 있습니다!
- 추출에서는 ArrayList랑 Deque 모두 매우 빠른 속도로 실행되고, 속도에서 큰 차이가 없습니다. 반면 삽입에서 속도 차이가 많이 발생하기 때문에 코딩테스트에서는 Deque를 사용하는 것이 더 바람직 해 보입니다.
Java Deque의 핵심 메서드 정리
Java의 Deque는 List처럼 인덱스로 중간 요소를 직접 건드릴 순 없고, 오직 양쪽 끝에서만 작업할 수 있습니다. 메서드 이름에 First와 Last가 붙어서 어디서 작업하는지 명확히 알 수 있습니다.
| 카테고리 | 메서드 | 설명 | 비고 (주의사항) |
|---|---|---|---|
| 추가 | offerFirst(E e) | Deque의 앞쪽(Head)에 요소를 추가합니다. | 용량 초과 시 false 반환 (안전하게 추가) |
offerLast(E e) | Deque의 뒤쪽(Tail)에 요소를 추가합니다. | 용량 초과 시 false 반환 (안전하게 추가) | |
| 제거 | pollFirst() | Deque의 앞쪽(Head) 요소를 제거하고 반환. | Deque 비어 있을 시 null 반환 (안전하게 제거) |
pollLast() | Deque의 뒤쪽(Tail) 요소를 제거하고 반환. | Deque 비어 있을 시 null 반환 (안전하게 제거) | |
| 확인 | peekFirst() | Deque의 앞쪽(Head) 요소를 제거 없이 확인. | Deque 비어 있을 시 null 반환 (안전하게 확인) |
peekLast() | Deque의 뒤쪽(Tail) 요소를 제거 없이 확인. | Deque 비어 있을 시 null 반환 (안전하게 확인) |
| 메서드 | 설명 | 예시 | 주의사항 |
|---|---|---|---|
isEmpty() | Deque가 비었는지 확인 (true/false) | while (!dq.isEmpty()) | 요소가 없을 때만 true |
size() | 현재 요소의 개수 반환 | dq.size() | 큰 Deque는 성능 이슈 가능 |
contains(o) | 특정 요소 존재 여부 확인 | dq.contains("A") | 내부 순회 필요 (느릴 수 있음) |
clear() | 모든 요소 제거 | dq.clear() | 이후 참조 주의 |
Deque<String> deque = new ArrayDeque<>();
deque.offerLast("A");
deque.offerLast("B");
deque.offerFirst("C");
System.out.println(deque); // [C, A, B]
System.out.println(deque.isEmpty()); // false
System.out.println(deque.size()); // 3
/*
* Q. contains의 작동 원리
* - Deque 내부 요소들을 처음부터 끝까지 하나씩 비교
* - equals() 메서드를 사용해서 비교
* - 같다고 판단되는 게 있으면 true, 아니면 false
*/
System.out.println(deque.contains("A")); // true
deque.clear(); // 모든 요소 삭제
System.out.println(deque); // []왜
offer/poll/peek을 추천하나요?
물론 add/remove/get도 있지만, add/remove/get는 Deque가 비어있거나 용량 제한이 있을 때 예외(Exception)를 발생시킵니다.
반면, offer/poll/peek 계열은 문제가 생겼을 때 false나 null을 반환하여 코드를 더 간결하고 안전하게 작성할 수 있게 해줍니다.
코딩테스트에서는 불필요한 예외 처리를 줄이는 것이 중요하므로, 이들을 사용하는 것이 일반적입니다.
사용
Deque<타입> 변수명 = new ArrayDeque<>();
스택(Stack)처럼 사용하고 싶을 때(LIFO):
자바에서 Deque로 스택을 구현할 때 보통 Last 보다는 First를 씁니다.
물론, Last든, First든 일관성 있게 쓰면 동작상 문제는 없지만,
자바 Deque의 스택 관련 메서드는 모두 앞쪽에 해당하며, 많은 자바 예시 코드도 이를 따르고 있습니다.
- 데이터 추가: offerFirst()
- 데이터 제거: pollFirst()
- 데이터 확인: peekFirst()
큐(Queue)처럼 사용하고 싶을 때(FIFO):
- 데이터 추가: offerLast()
- 데이터 제거: pollFirst()
- 데이터 확인: peekFirst()
할 수 있다!!!