[자료구조] 덱(Deque)

 

덱(Deque)이란? 

양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다. 

선입선출(FIFO), 후입선출(LIFO) 개념이 모두 적용이 되는 자료구조이다. 

Java에서 Deque은 java.util.Deque 인터페이스를 이용해 구현할 수 있다. 

 

 

 

 

 

장점

데이터의 삽입 & 삭제가 빠름

크기가 가변적임

데이터를 앞뒤에서 삽입 & 삭제할 수 있음

index로 임의 원소 접근이 가능함

 

 

 

 

단점

deque의 중간에서의 삽입과 삭제가 어렵다. 

 

 

 

 

 

 

 

 

 

사용법 

Deque 객체 생성 

//import java.util.Deque;
//import java.util.LinkedList;

Deque<Integer> deque = new LinkedList<>();

 

 

 

앞 부분에 값 추가하기 

deque.addFirst(1);
deque.offerFirst(2);

// [2, 1]

 

 

 

뒷 부분에 값 추가하기 

deque.addLast(1);
deque.add(2);
deque.offerLast(3);
deque.offer(4);

[1, 2, 3, 4]

 

 

add와 offer 메소드의 차이 

add : illegalStateException을 발생시킨다.

offer : 큐가 가득차서 더 이상 추가할 수 없는 경우 false를 반환하고, 요소가 추가되면 true를 반환하며 특정 예외를 throw하지 않는다. 

 

 

 

 

 

앞 부분 값 삭제하기 

for(int i=1;i<=5;i++) {
	deque.offer(i);
}

// [1, 2, 3, 4, 5]

deque.remove();
deque.removeFirst();
deque.pollFirst();
deque.poll();
// [5]

 

 

 

뒷 부분 값 삭제하기

for(int i=1;i<=5;i++) {
	deque.offer(i);
}

// [1, 2, 3, 4, 5]

deque.removeLast();
deque.pollLast();
// [1, 2, 3]

 

 

remove와 poll 메소드의 차이

remove : 비어있을 때 삭제하면 예외 발생

poll : 비어있을 때 삭제하면 null 반환

 

 

 

 

앞 부분 값 가져오기 (읽기)

for (int i = 1; i <= 5; i++) {
	deque.offer(i);
} 
// [1, 2, 3, 4, 5]

int num1 = deque.getFirst();	// 1
int num2 = deque.peekFirst();	// 1
int num3 = deque.peek();	// 1

 

 

 

뒷 부분 값 가져오기 (읽기) 

for (int i = 1; i <= 5; i++) {
	deque.offer(i);
} 
// [1, 2, 3, 4, 5]

int num1 = deque.getLast();	// 5
int num2 = deque.peekLast();	// 5

 

 

get과 peek 메소드의 차이 

get : 해당 값을 return하고 실패 시 Exception을 발생

peek : 해당값을 return하고 실패시 null을 return한다. 

 

 

 

 

 

 

 

 

 

 

참조 

https://velog.io/@esun1903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Deque

[자료구조] Deque(덱,데크)

https://adjh54.tistory.com/135#4)%20%EB%8D%B1(deque)-1

[Java/자료구조론] 선형구조 이해하기 -1 : 큐(Queue), 스택(Stack), 덱(Deque)