[자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 덱(Deque)

✅ 자료구조 : 데이터를 저장하는 방식

✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조

랜덤 접근 불가능?

모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들

덱(Deque)

덱은 큐의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능하게 만든 큐이다.

간단하게 말해서 스택과 큐의 성질을 모두 가지는 자료구조이다.

double-ended queue의 줄임말이다.

이미지 출처

덱의 연산

양쪽 끝에서 데이터의 삽입과 삭제를 모두 할 수 있기 때문에 스택과 큐의 연산 모두 구현 가능

데이터 삽입

• addFirst() : 덱의 앞쪽에 데이터 추가. 용량 제한이 있는 덱의 경우 용량을 초과하면 예외가 발생한다.

• addLast() : 덱의 마지막에 데이터 추가. 용량 제한이 있는 덱의 경우 용량 초과 시 예외가 발생한다.

• offerFirst() : 덱의 앞쪽에 데이터 추가. 정상적으로 추가되면 true, 용량 제한에 걸리는 경우 false 리턴

• offerLast() : 덱의 마지막에 데이터 추가. 정상적으로 추가되면 true, 용량 제한에 걸리는 경우 false 리턴

• addAll(Collection <? extends E c) : 입력받은 Collection의 모든 데이터를 뒤쪽에 삽입

• add() == addLast()

• push() == addFirst()

데이터 삭제

• removeFirst() : 덱의 맨 앞에서 데이터를 뽑아 제거한 다음 해당 데이터를 리턴. 덱이 비어있으면 예외가 발생한다.

• removeLast() : 덱의 마지막에서 데이터를 뽑아 제거한 다음 해당 데이터를 리턴. 덱이 비어있으면 예외가 발생한다.

• pollFirst() : 덱의 맨 앞에서 데이터를 뽑아 제거한 다음 해당 데이터를 리턴. 덱이 비어있으면 null 리턴

• pollLast() : 덱의 마지막에서 데이터를 뽑아 제거한 다음 해당 데이터를 리턴. 덱이 비어있으면 null리턴

• removeFirstOccrrunce(Object o) : 덱의 앞에서부터 탐색하여 입력한 o와 동일한 첫 엘리먼트를 제거. o와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않음

• removeLastOccrrunce(Object o) : 덱의 뒤에서부터 탐색하여 입력한 o와 동일한 첫 엘리먼트를 제거. o와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않음

• remove() == removeFirst() == element() = pop()

• remove(Object o) == removeFirstOccrrunce(Object o)

• poll() == pollFirst()

데이터 조회

• getFirst() : 덱의 앞쪽 엘리먼트 하나를 리턴. 덱이 비어있으면 예외가 발생한다

• getLast() : 덱의 맨 뒤쪽 엘리먼트 하나를 리턴. 덱이 비어있으면 예외가 발생한다

• peekFirst() :덱의 앞쪽 엘리먼트 하나를 리턴. 덱이 비어있으면 null 반환

• peekLast() : 덱의 맨 뒤쪽 엘리먼트 하나를 리턴. 덱이 비어있으면 null 반환

• peek() == peekFirst()

그 외

• contain(Object o) : 덱에 o와 동일한 데이터가 포함되어 있는지 확인

• size() : 덱의 크기

• iterator() : 덱의 앞쪽부터 순차적으로 실행되는 이터레이터를 얻어옴

• descendingIterator() : 덱의 뒤쪽부터 순차적으로 실행되는 이터레이터를 언어 옴

이미지 출처

덱의 구현

아주 잘 정리해 두셨다.

•  자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기

•  [자료구조] 덱(Deque, Double-ended Queue) 설명 및 구현

자바에서 덱은 Deque 인터페이스로 구현되었다.

이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("Element1");

참고

• https://librewiki.net/wiki/%EC%8B%9C%EB%A6%AC%EC%A6%88:%EC%88%98%ED%95%99%EC%9D%B8%EB%93%AF_%EA%B3%BC%ED%95%99%EC%95%84%EB%8B%8C_%EA%B3%B5%ED%95%99%EA%B0%99%EC%9D%80_%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B3%BC%ED%95%99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88
• https://st-lab.tistory.com/185
• https://leejinseop.tistory.com/39
• https://soft.plusblog.co.kr/24