Deque
Double-Ended Queue의 줄임말
큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미
어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다. -> 장점!!
특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다.
JAVA의 Deque
자바에서의 덱은 인터페이스로 구현되었다.
덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, 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에 들어있는 엘리먼트의 개수
JAVA에서 Deque 사용법
deque 생성
Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new ConcurrentLinkedDeque<>();
Deque<String> linkedList = new LinkedList<>();deque 순회
for문이나 Iterator를 이용해 순회할 수 있다.
// for 문을 이용한 순회
for (String elem : deque1) {
System.out.println(elem);
}
// Iterator를 이용한 순회
Iterator<String> iterator = deque1.iterator();
while (iterator.hasNext()) {
String elem = iterator.next();
System.out.println(elem);
}
// 역순순회
Iterator<String> reverseIterator = deque1.descendingIterator();
while (reverseIterator.hasNext()) {
String elem = reverseIterator.next();
System.out.println(elem);
}