Deque over Stack을 사용해야 하는 이유

Deque over Stack을 사용해야 하는 이유

필요한 건Stack데이터 구조입니다.데이터 구조에 항목을 푸시할 수 있고 스택에서 마지막 항목만 가져오면 됩니다.Java Doc for Stack에는 다음과 같이 표시됩니다.

보다 완전하고 일관된 LIFO 스택 운영 세트가 Deque 인터페이스와 그 구현에 의해 제공되며, 이 클래스에서 우선적으로 사용해야 합니다.예를 들어 다음과 같습니다.

Deque<Integer> stack = new ArrayDeque<>();

이 데이터 구조를 메서드에 대해 로컬로 사용할 것이기 때문에 여기서 동기화된 동작을 원하지 않습니다.이것과는 별도로, 이 방법을 사용하는 것이 좋은 이유는 무엇입니까?Deque에 걸쳐서Stack여기?

추신: Deque의 javadoc은 다음과 같이 말합니다.

데크는 LIFO(Last-In-First-Out) 스택으로도 사용할 수 있습니다.이 인터페이스는 레거시 스택클래스보다 우선적으로 사용해야 합니다.

우선, 그것이 상속의 측면에서 더 합리적입니다.이 사실은Stack확장Vector제가 보기엔 정말 이상해요Java 초기에는 상속이 IMO를 과도하게 사용하였습니다.Properties또 다른 예로 들 수 있습니다.

저는 당신이 인용한 문서에서 중요한 단어가 일치합니다. Deque컬렉션의 시작 또는 끝에서 항목을 가져오기/추가/삭제할 수 있는 일련의 조작을 공개합니다.그것이 끝입니다.위치별로 요소에 접근할 수 있는 방법은 의도적으로 없습니다.Stack서브클래스이기 때문에 공개한다Vector.

아, 그리고Stack인터페이스가 없기 때문에 필요한 경우Stack특정 콘크리트 클래스로 커밋하게 되는 작업은 일반적으로 좋은 생각이 아닙니다.

그리고 댓글에 지적된 것처럼Stack그리고.Deque역반복순서 지정:

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3


Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1

이는 Deque.iterator()의 JavaDocs에도 설명되어 있습니다.

이 deque의 요소 위에 올바른 순서로 반복기를 반환합니다.요소는 첫 번째(머리)에서 마지막(꼬리) 순서로 반환됩니다.

Deque가 Stack보다 뛰어난 이유는 다음과 같습니다.

객체 지향 설계 - 상속, 추상화, 클래스 및 인터페이스:스택은 클래스, Deque는 인터페이스입니다.확장 가능한 클래스는 1개뿐이지만 Java에서는 임의의 수의 인터페이스를 단일 클래스로 구현할 수 있습니다(여러 유형의 상속).Deque 인터페이스를 사용하면 콘크리트 스택클래스와 그 이전 클래스에 의존하지 않고, 예를 들어 다른 클래스를 확장하거나 Deque의 다른 실장(Linked List, Array Deque 등)을 자유롭게 교환할 수 있습니다.

불일치:스택은 인덱스로 요소에 액세스할 수 있는 벡터 클래스를 확장합니다.이는 스택이 실제로 수행해야 하는 작업과 일치하지 않기 때문에 Deque 인터페이스가 선호됩니다(이러한 운영은 허용되지 않습니다). 허용된 운영은 FIFO 또는 LIFO 데이터 구조가 허용하는 것과 일관됩니다.

퍼포먼스:스택이 확장하는 벡터 클래스는 기본적으로 ArrayList의 "스레드 세이프" 버전입니다.동기화에 의해, 애플리케이션의 퍼포먼스가 큰폭으로 저하할 가능성이 있습니다.또한 불필요한 기능(#2 참조)으로 다른 클래스를 확장하면 오브젝트가 비대해져 메모리 및 퍼포먼스 오버헤드가 커질 수 있습니다.

「」를 사용하는 더 .Deque에 걸쳐서StackDeque에는 LIFO 개념을 적용한 상태로 스트림을 목록으로 변환하는 기능이 있지만 Stack에는 적용되지 않습니다.

Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new ArrayDeque<>();

stack.push(1);//1 is the top
deque.push(1)//1 is the top
stack.push(2);//2 is the top
deque.push(2);//2 is the top

List<Integer> list1 = stack.stream().collect(Collectors.toList());//[1,2]

List<Integer> list2 = deque.stream().collect(Collectors.toList());//[2,1]

Stack 클래스의 설명에 기재되어 있는 모순에 대한 저의 해석은 다음과 같습니다.

여기서 범용 구현을 살펴보면 세트, 맵 및 목록의 구현에 일관된 접근 방식이 있음을 알 수 있습니다.

• 세트 및 맵에는 해시 맵과 트리를 사용한2가지 표준 구현이 있습니다.첫 번째 것이 가장 많이 사용되며 두 번째 것이 순서 있는 구조가 필요할 때 사용됩니다(또한 자체 인터페이스인 SortedSet 또는 SortedMap도 구현됩니다).

• 할 수 .Set<String> set = new HashSet<String>();이유를 보려면 여기를 클릭하십시오.

그러나 스택 클래스: 1) 자체 인터페이스가 없습니다. 2) 크기 조정 가능한 어레이를 기반으로 하는 벡터 클래스의 서브 클래스입니다.그러면 스택의 링크 리스트 실장은 어디에 있습니까?

Deque 인터페이스에서는 두 가지 구현(크기 조정 가능한 어레이 - ArrayDeque, 링크드 리스트 - Linked List)을 포함하여 이러한 문제는 발생하지 않습니다.

저는 이 점을 간과하고 있었습니다.스택은 Vector에서 파생된 Threadsafe이지만 대부분의 디큐 구현은 그렇지 않으므로 단일 스레드에서만 사용하면 더 빠릅니다.

성능이 원인일 수 있습니다.사용한 알고리즘은 Stack을 Deque로 대체하는 것만으로 7.6분에서 1.5분으로 단축되었습니다.

언급URL : https://stackoverflow.com/questions/12524826/why-should-i-use-deque-over-stack