요즘 알고리즘에 감이 돌아와서, 파이썬만으로 구현하지 않고 자바도 함께 구현 연습을 하고 있다.
물론 아직 파이썬 퍼스트이긴 하다. 자바는 아직 더 연습이 필요한 상태이기 때문에...
여하간 자바로 알고리즘 풀이를 하면서 유용하게 쓰이는 collections framework의 클래스들이 있기도 하고, 학습을 하며 하나씩 정리를 하고 싶은 자료구조(예를 들어 TreeSet...!)들이 쌓이고 있어서 하나씩 정리를 해나가 보려고 한다.

Java Collections Framework

Deque (double-ended queue)

자바의 데크 인터페이스는 큐 인터페이스를 상속한다. 양방향 큐의 기능을 제공하므로, FIFO 큐와 LIFO 스택 두가지 모두로 활용할 수 있다.
자바 독스를 확인해보면 레거시 스택에 비해 스택의 구현 자료구조로 권장되고 있다.

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Deque.html

주요 메소드는 아래와 같다.

Summary of Deque methods

익셉션을 던지는 경우와 null 혹은 특정한 값을 리턴하는 메소드로 구분할 수 있다.

Operation	Throws Exception (Head)	Special Value (Head)	Throws Exception (Tail)	Special Value (Tail)
Insert	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Remove	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Examine	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

Comparison of Queue and Deque methods

FIFO (First-In-First-Out) 동작을 수행한다.
요소들은 데큐의 끝에 추가되고, 처음에서 제거된다.
큐 인터페이스로부터 상속된 메서드들은 아래 테이블에 나타난 데큐 메소드와 정확히 동일하다.
- 두 가지 메소드 중 하나를 사용하면 된다. 구현체인 ArrayDeque 를 확인해보면 다른 하나의 메소드(예를 들어 remove())가 동일 기능의 메소드(removeFirst())를 그대로 호출하는 것을 볼 수 있다.

Queue Method	Equivalent Deque Method
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

LIFO (Last-In-First-Out) 스택 동작도 수행한다.
요소들은 데큐의 시작으로 삽입되고, 팝(제거) 된다.
스택의 메서드들은 아래 테이블에 작성된 데큐 메소드와 동일하다.

Comparison of Stack and Deque methods

Stack Method	Equivalent Deque Method
push(e)	addFirst(e)
pop()	removeFirst()
peek()	getFirst()

ArrayDeque

데크와 큐 구현체이다.
오라클에서 제공하는 자바 독스를 확인해보면, 해당 구현체가 스택일 때는 Stack 클래스보다 빠르고, 큐일 때는 링크드 리스트 보다 빠를 것이라고 나온다.

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/ArrayDeque.html

성능 및 특징

ArrayDeque는 내부적으로 기본 array 배열을 활용하게 되므로, 포인터와 노드로 구현되는 링크드 리스트에 비해서 지역성이 높을 것이며, 메모리 측면에서도 효율성을 가질 것이다.
- cache locality 가 높다.
- 다만 ArrayDeque는 사이즈 제한이 없고 이를 위해 현재 크기와 가용 크기에 따라 동적으로 배열을 재할당 받는 동작을 수행하기도 한다. 처음 ArrayDeque 객체를 생성할 때 적정한 크기로 잘 설정하는 것도 효율을 높이는 방법이 될 것이다.
쓰레드 세이프 하지 않다.
- 데크를 멀티 쓰레드 환경에서 활용해야 한다면 concurrent 패키지에 있는 ConcurrentLinkedDeque 또는 LinkedBlockingDeque를 활용할 수 있다.
인덱스 접근을 지원하지는 않는다.
- 내부적으로 배열을 활용하는데 인덱스 접근이 지원되지 않는 이유
  - 배열로 구현했으나, 순환(circular) 형태의 배열로 구현되어 있다. 즉, 배열의 시작과 끝을 원형으로 연결해 동작하도록 만들어졌다.
  - 원형 큐로 구현함으로써, 큐의 끝에 도달해도 앞이 비었다면 문제 없이 다음 요소를 이어서 삽입할 수 있도록 해 공간 효율성을 높였다.
    - 단순 삽입/삭제시 요소 재배열이 필요하지 않다.
  - 이러한 구현 방식 때문에 index를 직접적으로 접근하는 것은 불가능하다. 대신, 큐의 양 끝에서 요소를 추가/제거하거나, Iterator를 사용하여 요소에 접근할 수 있습니다.

Stack

사용이 지양되고 있는 스택 자료구조 구현 클래스이다.

Vector 클래스를 상속받는다.
- 그런데 Vector 클래스의 모든 메소드는 synchronized 키워드가 붙어 있다.
- 일견 스레드 세이프 하겠다고 볼 수 있지만, 모든 메소드에, 메소드 레벨에 동기화 키워드가 붙어있는 것은 잘못된 설계였다고 볼 수 있다.
Stack에서 제공하는 메서드 역시 synchronized를 사용해서 동기화 처리하는데, 내부적으로 Vector가 제공하는 메서드를 사용함으로써 이중으로 동기화 처리된다.
심지어 메서드 실행에 한해서는 쓰레드 세이프하지만 객체 자체에 대해서는 동기화 처리가 되어있지 않기 때문에 여전히 쓰레드 세이프를 보장받지 못 하는 점이 있다.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

클래스의 독스를 확인하면 위와 같이 더 완전하고 일관성 있는 스택 구현을 제공하는 데크 구현체를 활용할 것을 권장하고 있다.

참고자료

저작자표시 (새창열림)

'Java' 카테고리의 다른 글

JDBC 란? (0)	2021.07.04
Maven이란? (0)	2021.07.04
자바 환경변수 (0)	2021.05.08

stepbystep

[Java Collections]ArrayDeque 알아보기

Java Collections Framework