른록노트
[DataStructure] Deque (Java) 본문
Deque
Module java.base
Package java.util
Interface Deque<E>
Type Parameters:
E - the type of elements held in this deque
All Superinterfaces:
Collection<E>, Iterable<E>, Queue<E>
All Known Subinterfaces:
BlockingDeque<E>
All Known Implementing Classes:
ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList
public interface Deque<E>
extends Queue<E>설명
양쪽 끝에서 요소 삽입 및 제거를 지원하는 선형 컬렉션입니다.
deque 라는 이름은 "double ended queue"의 약자이며 일반적으로 "deck"으로 발음됩니다. 대부분의 Deque 구현은 포함할 수 있는 요소 수에 고정된 제한을 두지 않지만 이 인터페이스는 용량 제한 deque와 고정 크기 제한이 없는 deque를 지원합니다.
이 인터페이스는 deque의 양쪽 끝에 있는 요소에 액세스하는 메서드를 정의합니다. 요소를 삽입, 제거 및 검사하는 방법이 제공됩니다. 이러한 각 메서드는 두 가지 형식으로 존재합니다. 하나는 작업이 실패하면 예외를 throw하고 다른 하나는 특수 값(작업에 따라 null 또는 false)을 반환합니다. 삽입 작업의 후자 형식은 용량이 제한된 Deque 구현과 함께 사용하도록 특별히 설계되었습니다. 대부분의 구현에서 삽입 작업은 실패할 수 없습니다.
위에서 설명한 12가지 방법은 다음 표에 요약되어 있습니다.
Deque methods 요약
First Element (Head)
- Throws exception
Insert : addFirst(e)
Remove : removeFirst()
Examine : getFirst()
- Returns special value
Insert : offerFirst(e)
Remove : pollFirst()
Examine : peekFirst()
Last Element (Tail)
- Throws exception
Insert : addLast(e)
Remove : removeLast()
Examine : getLast()
- Returns special value
Insert : offerLast(e)
Remove : pollLast()
Examine : peekLast()이 인터페이스는 Queue 인터페이스를 상속받습니다. deque가 queue로써 사용되면 선입선출 동작이 발생합니다.
queue로써 쓰이면 요소들은 deque 의 tail에 추가되고 head에서 remove됩니다.
Queue 인터페이스에서 상속된 메서드는 다음 표에 표시된 것처럼 Deque 메서드와 정확히 동일합니다.
- Queue Method : Equuivalent Deque Method
add(e) : addLast(e)
offer(e) : offerLast(e)
remove() : removeFirst()
poll() : pollFirst()
element() : getFirst()
peek() : peekFirst()Deques는 LIFO(Last-In-First-Out) 스택으로도 사용할 수 있습니다. 이 인터페이스는 레거시 Stack 클래스보다 우선적으로 사용해야 합니다. 데크가 스택으로 사용될 때 요소는 데크의 시작 부분에서 푸시되고 팝됩니다. Stack 메서드는 아래 표에 표시된 대로 Deque 메서드와 동일합니다.
- Stack Method : Equivalent Deque Method
push(e) : addFirst(e)
pop() : removeFirst()
peek() : getFirst();peek 메서드는 deque가 queue이나 stack으로 사용될 때 똑같이 잘 작동합니다. 두 경우 모두 요소는 deque의 HEAD 부분에서 그려집니다.
이 인터페이스는 내부 요소를 제거하는 두 가지 방법인 removeFirstOccurrence 및 removeLastOccurrence를 제공합니다.(매개변수와 동일한 지점에서 동작하는 메서드)
List 인터페이스와 달리 이 인터페이스는 요소에 대한 인덱싱된 액세스를 지원하지 않습니다.
Deque 구현은 null 요소의 삽입을 금지하는 데 엄격하게 요구되지는 않지만 그렇게 할 것을 강력히 권장합니다.
null 요소를 허용하는 모든 Deque 구현 사용자는 null 삽입 기능을 이용하지 않는 것이 좋습니다.
이는 null이 deque가 비어 있음을 나타내기 위해 다양한 메서드에서 특수 반환 값으로 사용되기 때문입니다.
Deque 구현은 일반적으로 equals 및 hashCode 메서드의 요소 기반 버전을 정의하지 않고 대신 클래스 Object에서 ID 기반 버전을 상속합니다.
이 인터페이스는 Java Collections Framework의 구성원입니다.Collecion
Since
1.6
메서드
boolean add(E e)
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 이 deque가 나타내는 queue(즉, 이 deque의 맨 뒤에 있음)에 지정된 요소를 삽입합니다. 성공 시 true를 반환하고 현재 사용 가능한 공간이 없으면 IllegalStateException을 발생시킵니다. .
boolean addAll(Collection<? extends E> c)
collection's iterator에 의해 반환된 순서대로 각 요소에 대해 addLast(E)를 호출하는 것처럼 지정된 컬렉션의 모든 요소를 이 deque의 끝에 추가합니다.
void addFirst(E e)
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 이 deque의 앞에 지정된 요소를 삽입하고 현재 사용 가능한 공간이 없으면 IllegalStateException을 발생시킵니다.
void addLast(E e)
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 이 deque의 끝에 지정된 요소를 삽입하고 현재 사용 가능한 공간이 없으면 IllegalStateException을 발생시킵니다
boolean contains(Object o)
이 deque에 지정된 요소가 포함되어 있으면 true를 반환합니다.
Iterator<E> descendingIterator()
역순으로 이 데크의 요소에 대한 반복자를 반환합니다.
E element()
이 deque가 나타내는 queue의 HEAD(즉, 이 deque의 첫 번째 요소)를 검색하지만 제거하지는 않습니다.
E getFirst()
이 deque의 첫 번째 요소를 검색하지만 제거하지는 않습니다.
E getLast()
이 deque의 마지막 요소를 검색하지만 제거하지는 않습니다.
Iterator<E> iterator()
이 deque의 요소에 대한 반복자를 적절한 순서로 반환합니다.
boolean offer(E e)
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 이 deque가 나타내는 queue(즉, 이 deque의 맨 뒤에 있음)에 지정된 요소를 삽입하고, 성공하면 true를 반환하고 현재 사용 가능한 공간이 없으면 false를 반환합니다.
boolean offerFirst(E e)
용량 제한을 위반하지 않는 한 지정된 요소를 이 deque의 앞에 삽입합니다.
boolean offerLast(E e)
용량 제한을 위반하지 않는 한 지정된 요소를 이 deque의 끝에 삽입합니다.
E peek()
이 deque가 나타내는 queue의 HEAD(즉, 이 deqeu의 첫 번째 요소)를 검색하지만 제거하지는 않으며, 이 deque가 비어 있으면 null을 반환합니다.
E peekFirst()
이 deque의 첫 번째 요소를 검색하지만 제거하지는 않습니다. 이 deque가 비어 있으면 null을 반환합니다.
E peekLast()
이 deque의 마지막 요소를 검색하지만 제거하지는 않습니다. 이 deque가 비어 있으면 null을 반환합니다.
E poll()
이 deque가 나타내는 queue의 HEAD(즉, 이 deque의 첫 번째 요소)를 검색하고 제거하거나, 이 deque가 비어 있으면 null을 반환합니다.
E pollFirst()
이 deque의 첫 번째 요소를 검색하고 제거하거나 이 deque가 비어 있으면 null을 반환합니다.
E pollLast()
이 deque의 마지막 요소를 검색하고 제거하거나 이 deque가 비어 있으면 null을 반환합니다.
E pop()
Pops an element from the stack represented by this deque.
이 deque가 나타내는 stack에서 요소를 pop합니다.
void push(E e)
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 이 deque가 나타내는 stack(즉, 이 데크의 헤드)에 요소를 푸시하고 현재 사용 가능한 공간이 없으면 IllegalStateException을 발생시킵니다.
E remove()
이 deque가 나타내는 queue의 HEAD(즉, 이 deque의 첫 번째 요소)를 검색하고 제거합니다.
boolean remove(Object o)
이 deque에서 지정된 요소의 첫 번째 발생을 제거합니다.
E removeFirst()
이 deque의 첫 번째 요소를 검색하고 제거합니다.
boolean removeFirstOccurrence(Object o)
이 deque에서 지정된 요소의 첫 번째 발생을 제거합니다.
E removeLast()
이 deque의 마지막 요소를 검색하고 제거합니다.
boolean removeLastOccurrence(Object o)
이 deque에서 지정된 요소의 마지막 항목을 제거합니다.
int size()
이 deque의 요소 수를 반환합니다.
#### Methods declared in interface java.util.Collection ####
clear, containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray, toArray
#### Methods declared in interface java.lang.Iterable ####
forEach사용법
import java.util.*;
public class Test {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<String>();
deque.add("test1");
deque.add("test2");
deque.addFirst("test3");
deque.addLast("test4");
Iterator<String> iter = deque.iterator();
while(iter.hasNext()) {
System.out.println(iter.next());
}
}
}
/* 결과
test3
test1
test2
test4
*/시간복잡도
add() - deque TAIL에 요소를 추가합니다. 따라서 TAIL만 업데이트하므로 O(1) - queue 상속
remove() - deque HEAD에 요소를 제거합니다. O(1) - queue 상속
addLast(e) - 위와 비슷하므로 O(1)
offerLast(e) - 위와 비슷하므로 O(1)
removeFirst() - 위와 비슷하므로 O(1)
pollFirst() - 위와 비슷하므로 O(1)
getFirst() - 위와 비슷하므로 O(1)
peekFirst() - 위와 비슷하므로 O(1)