1. Deque 란?
Deque란 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미한다.
덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다. 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다.
2. Deque의 시간복잡도
| 연산 | 시간 복잡도 |
|---|---|
| 삽입(Insertion) | O(1) |
| 삭제(Deletion) | pop : O(1) remove : O(n) |
| 검색(Search) | O(n) |
3. Deque는 언제 사용해야 할까?
deque는 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다.
시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다.
즉, 대부분의 경우에 deque는 list보다 월등한 옵션이다.
데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.
4. ArrayDeque와 LinkedList
후에 설명하겠지만 Deque를 선언할 때는 new Deque()와 같은 형식으로는 선언이 되지 않는다.
new ArrayDeque<>() 또는 new LinkedList<>()와 같이 선언을 해야한다.
1. ArrayDeque와 LinkedList
ArrayDeque는 Queue의 서브인터페이스인 Deque의 구현체이고, LinkedList는 List와 Queue의 구현체이다. 따라서 LinkedList는 List의 특징을 가지고 있고, ArrayDeque은 배열의 특성을 가지고 있다고 할 수 있다.
2. 연산성능
ArrayDeque을 배열의 측면에서 바라봤을 때, deque의 양끝에서 삽입/삭제 연산이 일어날 경우 시간 복잡도가 O(1)이므로 삽입/삭제 성능이 우수하다. 또한 Random access가 가능하기에 원소 조회 시에도 속도가 빠르다. LinkedList도 삽입/삭제 연산 성능이 좋지만, 특정 원소에 접근 시의 성능은 ArrayDeque에 비해 떨어진다.
또한 ArrayDeque는 LinkedList에 비해 cache-locality에 더 친숙하여 연산 속도가 더 빠르다.
3. 메모리
ArrayDeque은 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다.
위와 같은 차이점 때문에 ArrayDeque가 LinkedList보다 속도와 메모리 측면에서 더 효율적이라고 할 수 있으며, 이는 자바 공식문서에도 언급되어있다.
- ArrayDeque은 크기 조정이 가능하다.
- ArrayDeque은 null을 요소로 추가할 수 없지만 LinkedList는 null을 추가할 수 없다.
5. Deque 사용법
1. Deque 선언
Deque que = new ArrayDeque(); // 타입 설정x
Deque<DequeDemo> demo = new ArrayDeque<DequeDemo>(); // DequeDemo 클래스 타입으로 선언
Deque<Integer> i = new ArrayDeque<Integer>(); // Integer 타입
Deque<Integer> i2 = new ArrayDeque<>(); // 뒷부분은 생략 가능
Deque<Integer> i3 = new ArrayDeque<Integer>(Arrays.asList(1, 2, 3, 4)); // 선언과 동시에 초기값 세팅
Deque<String> s = new ArrayDeque<String>(); // String 타입
Deque<Character> ch = new ArrayDeque<Character>(); // Char 타입Deque를 선언하려면 new Deque()로 선언이 안된다.
Deque대신 new ArrayDeque<>(), new LinkedList<>() 등으로 선언을 해줘야 한다.
선언 방법에는 Integer, String, Character, 클래스 등 다양한 방법으로 선언이 가능하다.
2. Deque 값 추가
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>(); // Deque 선언
// 값 추가
deque.addFirst("Hello");
deque.offerFirst("Hello");
deque.addLast("World");
deque.offerLast("World");
deque.add("Hello");
System.out.print(deque); // 결과 출력
}
}
// 출력 : [Hello, Hello, World, World, Hello]Deque의 값을 추가하는 메서드는 addFirst(), offerFirst(), addLast(), offerLast(), add() 이렇게 여러 개가 있다.
- addFirst() : Deque의 맨 앞에 데이터를 삽입한다. 용량을 초과하는 경우 Exception이 발생한다.
- offerFirst() : Deque의 맨 앞에 데이터를 삽입한다. 용량을 초과하는 경우 false를 리턴한다.
- addLast() : Deque의 맨 뒤에 데이터를 삽입한다. 용량을 초과하는 경우 Exception이 발생한다.
- offerLast() : Deque의 맨 뒤에 데이터를 삽입한다. 용량을 초과하는 경우 false를 리턴한다.
- add() : addLast()와 동일하다. 맨 뒤에 데이터를 삽입하고 용량을 초과하는 경우 Exception이 발생한다.
3. Deque 값 삭제
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>(); // Deque 선언
// 값 추가
deque.add("Hello1");
deque.add("World2");
deque.add("Hello3");
deque.add("World4");
deque.add("Hello5");
deque.add("World6");
deque.add("Hello7");
deque.add("World8");
System.out.println(deque); // 결과 출력
deque.removeFirst(); // 첫 번째 삭제
System.out.println(deque); // 결과 출력
deque.pollFirst(); // 첫 번째 삭제
System.out.println(deque); // 결과 출력
deque.remove(); // 첫 번째 삭제
System.out.println(deque); // 결과 출력
deque.poll(); // 첫 번째 삭제
System.out.println(deque); // 결과 출력
deque.removeLast(); // 마지막 삭제
System.out.println(deque); // 결과 출력
deque.pollLast(); // 마지막 삭제
System.out.println(deque); // 결과 출력
deque.remove("World6"); // 원하는 데이터 삭제
System.out.println(deque); // 결과 출력
deque.clear(); // 모두 삭제
System.out.println(deque); // 결과 출력
}
}
/* 출력
[Hello1, World2, Hello3, World4, Hello5, World6, Hello7, World8]
[World2, Hello3, World4, Hello5, World6, Hello7, World8]
[Hello3, World4, Hello5, World6, Hello7, World8]
[World4, Hello5, World6, Hello7, World8]
[Hello5, World6, Hello7, World8]
[Hello5, World6, Hello7]
[Hello5, World6]
[Hello5]
[Hello5]
[]Deque의 값을 삭제하는 방법에는 여러가지가 있다.
첫 번째부터 순서대로 삭제하는 방법
removeFirst(), pollFirst(), remove(), poll() 이 있다.
remove와 poll차이점은 remove는 deque가 비어있다면 Exception을 출력하지만 poll은 deque가 비어있다면 null을 리턴한다.
마지막부터 순서대로 삭제하는 방법
removeLast(), pollLast()가 있다.
위의 마찬가지로 remove는 deque가 비어있으면 Exception, poll을 null을 리턴한다.
그 외의 삭제 방법
remove(Object) 메서드를 사용하면 deque에서 Object를 찾아 삭제한다.
clear() 메서드를 사용하면 deque의 모든 데이터를 삭제한다.
4. Deque 크기 구하기
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>(); // Deque 선언
// 값 추가
deque.add("Hello1");
deque.add("World2");
deque.add("Hello3");
deque.add("World4");
deque.add("Hello5");
deque.add("World6");
deque.add("Hello7");
deque.add("World8");
System.out.println("Deque의 사이즈 = " + deque.size()); // 결과 출력
}
}
// 출력 : Deque의 사이즈 = 8size() 메서드로 Deque의 크기를 구할 수 있다. Deque 안의 데이터 개수를 출력한다.
5. Deque 값 출력
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>(); // Deque 선언
// 값 추가
deque.add("Hello1");
deque.add("World2");
deque.add("Hello3");
deque.add("World4");
deque.add("Hello5");
deque.add("World6");
deque.add("Hello7");
deque.add("World8");
System.out.println("첫 번째 값 : " + deque.getFirst() + ", " + deque.peekFirst() + ", " + deque.peek());
System.out.println("마지막 값 : " + deque.getLast() + ", " + deque.peekLast());
/* Iterator 클래스를 사용하여 값 출력 */
Iterator iter = deque.iterator();
while(iter.hasNext())
System.out.print(iter.next() + " ");
}
}
/* 출력
첫 번째 값 : Hello1, Hello1, Hello1
마지막 값 : World8, World8
Hello1 World2 Hello3 World4 Hello5 World6 Hello7 World9
*/Deque의 첫 번째 데이터를 가져오는 방법에는 getFirst(), peekFirst(), peek() 메서드가 있다.
반대로 마지막 데이터를 가져오는 방법에는 getLast(), peekLast() 메서드가 있다.
Iterator클래스를 사용하여 전체 Deque의 데이터를 출력할 수도 있다.
