[자바/자료구조] 덱 개념 정리

바킹독 개념 정리

덱 정의

덱은 양쪽 끝에서 삽입과 삭제가 전부 가능하다

어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다.

덱의 성질

 

덱의 구현

덱은 배열로 구현하는게 쉽다.

head는 가장 앞에 있는 원소의 인덱스이고 tail을 가장 뒤에 있는 원소의 인덱스 + 1이다

 

덱은 양쪽에서 모두 삽입 가능하기 때문에 양쪽으로 확장해야한다. 시작지점을 0으로 잡으면 왼쪽으로 확장할 수 없게 된다. 시작 지점을 배열의 중간으로 둬야한다. 

그래서 배열의 크기는 2*MX+1이고 head와 tail의 초기값은 MX이다

 

여기까지가 배열로 덱을 구현하는 방법이었고 STL로 구현하는 방법을 알아보겠다.

 

JAVA의 덱

자바에서의 덱은 인터페이스로 구현되었다.
덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.

 

Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new ConcurrentLinkedDeque<>();
Deque<String> linkedList = new LinkedList<>();

 

Deque 인터페이스의 메소드

 

<삽입>

addFirst()

덱의 앞쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다

offerFirst()

덱의 앞쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다.

addLast()

덱의 마지막 쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량 초과시 예외가 발생한다

add()

addLast()와 동일

offerLast()

덱의 마지막 쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다.

 

<삭제>

removeFirst()

덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다.

pollFirst()

덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다.

removeLast()

덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다.

pollLast()

덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다.

remove()

removeFirst()와 동일

poll()

pollFirst()와 동일

 

<값 추출>

getFirst()

덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다

peekFirst()

덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 null이 리턴된다.

getLast()

덱의 마지막쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다.

peekLast()

덱의 마지막 엘리먼트 하나를 제거하지 않은 채 리턴한다. 덱이 비어있으면 null이 리턴된다.

peek()

peekFirst()와 동일

<그 외>

removeFirstOccurrence(Object o)

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

removeLastOccurrence(Object o)

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

element()

removeFirst()와 동일

push()

addFirst()와 동일. 덱을 스택으로 사용할 때 쓰임

pop()

removeFirst()와 동일. 덱을 스택으로 사용할 때 쓰임

remove(Object o)

removeFirstOccurrence(Object o)와 동일

contain(Object o)

덱에 Object o와 동일한 엘리먼트가 포함되어 있는지 확인

size()

Deque에 들어있는 엘리먼트의 개수