1. 개요

Java Stack 클래스는 스택 데이터 구조를 구현합니다. Java 1.6 은 양쪽 끝에서 요소 삽입 및 제거를 지원하는 "양방향 대기열"을 구현하기위한 Deque 인터페이스를 도입했습니다 .

이제 Deque 인터페이스를 LIFO (Last-In-First-Out) 스택으로 사용할 수도 있습니다. 또한 Stack 클래스 의 Javadoc을 살펴보면 다음을 볼 수 있습니다.

보다 완전하고 일관된 LIFO 스택 작업 세트는 Deque 인터페이스 및 해당 구현에 의해 제공 되며이 클래스보다 우선적으로 사용해야합니다.

이 튜토리얼에서는 Java Stack 클래스와 Deque 인터페이스 를 비교합니다 . 또한 LIFO 스택에 Deque over Stack 을 사용해야하는 이유에 대해 설명합니다 .

2. 클래스 대 인터페이스

Java의 스택  은  클래스입니다 .

public class Stack<E> extends Vector<E> { ... }

즉, 자체 스택 유형 을 생성 하려면 java.util.Stack 클래스 를 상속해야합니다 .

Java는 다중 상속을 지원하지 않으므로 클래스가 이미 다른 유형의 하위 클래스 인 경우 Stack 클래스 를 확장하기 어려울 수 있습니다 .

public class UserActivityStack extends ActivityCollection { ... }

위의 예에서 UserActivityStack 클래스는 ActivityCollection 클래스 의 하위 클래스입니다. 따라서 java.util.Stack 클래스 도 확장 할 수 없습니다 . Java Stack 클래스 를 사용하려면 데이터 모델을 다시 설계해야 할 수 있습니다.

반면에 Java의 Deque 는 인터페이스입니다.

public interface Deque<E> extends Queue<E> { ... }

클래스가 Java에서 여러 인터페이스를 구현할 수 있다는 것을 알고 있습니다. 따라서 인터페이스를 구현하는 것이 상속을 위해 클래스를 확장하는 것보다 더 유연합니다.

예를 들어, UserActivityStack 이 Deque 인터페이스를 구현하도록 쉽게 만들 수 있습니다  .

public class UserActivityStack extends ActivityCollection implements Deque<UserActivity> { ... }

따라서 객체 지향 디자인 관점에서 Deque 인터페이스는 Stack 클래스 보다 더 많은 유연성을 제공합니다 .

3. 동기화 된 방법 및 성능

우리는 것을 본 적이 스택 클래스의 서브 클래스 java.util.Vector의 . 벡터 클래스는 동기화됩니다. 스레드 안전성을 달성하기 위해 전통적인 방법을 사용합니다 . 즉 , 방법을 " 동기화 " 합니다. ”

서브 클래스로, 스택 클래스입니다 동기화 뿐만 아니라.

반면에, Deque와 인터페이스는 스레드 안전하지 않습니다 .

따라서 스레드 안전성이 요구 사항이 아닌 경우 Deque 는 Stack 보다 더 나은 성능을 제공 할 수 있습니다 .

4. 반복 주문

Stack 과 Deque 는 모두 java.util.Collection 인터페이스의 하위 유형이므로 Iterable 입니다.

그러나 흥미로운 점은 동일한 순서로 동일한 요소를 Stack 객체와 Deque 인스턴스에 푸시하면 반복 순서가 다르다는 것입니다.

예제를 통해 자세히 살펴 보겠습니다.

먼저 일부 요소를 Stack 객체에 푸시  하고 반복 순서가 무엇인지 확인합니다.

@Test
void givenAStack_whenIterate_thenFromBottomToTop() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the bottom.",
      "I am in the middle.",
      "I am at the top.");
}

위의 테스트 메서드를 실행하면 통과합니다. 즉, Stack 객체 의 요소를 반복 할 때 순서는 stack bottom에서 stack top 순입니다 .

다음으로 Deque 인스턴스 에서 동일한 테스트를 수행해 보겠습니다  . 테스트 에서는 ArrayDeque 클래스를 Deque 구현으로 사용합니다.

또한 ArrayDeque 를 LIFO 스택으로 사용할 것입니다  .

@Test
void givenADeque_whenIterate_thenFromTopToBottom() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the top.",
      "I am in the middle.",
      "I am at the bottom.");
}

이 테스트는 실행하면 통과 할 것입니다.

따라서 Deque 의 반복 순서는 위에서 아래로 입니다.

LIFO 스택 데이터 구조에 대해 이야기 할 때 스택의 요소에 대한 적절한 반복 순서는 위에서 아래로 이루어져야합니다.

즉, Deque 의 반복자는 스택에 대해 예상하는 방식으로 작동합니다.

5. 유효하지 않은 LIFO 스택 작업

고전적인 LIFO 스택 데이터 구조는 push () , pop () 및 peek () 작업 만 지원 합니다. 양쪽 스택 클래스와 Deque와의 인터페이스 지원 그들. 여태까지는 그런대로 잘됐다.

그러나  LIFO 규칙을 위반하므로 LIFO 스택의 인덱스에 의해 요소에 액세스하거나 조작 할 수 없습니다 .

이 섹션에서는 Stack 및 Deque를 사용 하여 잘못된 스택 작업을 호출 할 수 있는지 살펴 보겠습니다 .

5.1. java.util.Stack의 클래스

부모 Vector  는 배열 기반 데이터 구조이므로 Stack 클래스는 인덱스로 요소에 액세스 할 수 있습니다.

@Test
void givenAStack_whenAccessByIndex_thenElementCanBeRead() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element."); //index 0
    myStack.push("I am the 2nd element."); //index 1
    myStack.push("I am the 3rd element."); //index 2
 
    assertThat(myStack.get(0)).isEqualTo("I am the 1st element.");
}

실행하면 테스트가 통과됩니다.

테스트에서는 세 가지 요소를 Stack 객체에 푸시 합니다. 그런 다음 스택 맨 아래에있는 요소에 액세스하려고합니다.

LIFO 규칙에 따라 하단 요소에 액세스하려면 위의 모든 요소를 ​​팝해야합니다.

그러나 여기, 와 스택 객체, 우리는 단지 그 인덱스로 요소에 액세스 할 수 있습니다 .

또한 Stack 객체 를 사용하면 index로 요소를 삽입하고 제거 할 수도 있습니다 . 그것을 증명하는 테스트 방법을 만들어 봅시다 :

@Test
void givenAStack_whenAddOrRemoveByIndex_thenElementCanBeAddedOrRemoved() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(2);

    myStack.add(1, "I am the 2nd element.");
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(myStack.get(1)).isEqualTo("I am the 2nd element.");

    myStack.remove(1);
    assertThat(myStack.size()).isEqualTo(2);
}

실행하면 테스트도 통과됩니다.

따라서 Stack 클래스를 사용 하면 배열로 작업하는 것처럼 요소를 조작 할 수 있습니다. 이것은 LIFO 계약을 깨뜨 렸습니다.

5.2. java.util.Deque 인터페이스

Deque 는 인덱스로 요소에 액세스, 삽입 또는 제거하는 것을 허용하지 않습니다. Stack 클래스보다 낫습니다 .

그러나 Deque 는 "양방향 대기열"이므로 양쪽 끝에서 요소를 삽입하거나 제거 할 수 있습니다.

즉, Deque 를 LIFO 스택으로 사용할 때 스택 맨 아래에 직접 요소를 삽입 / 제거 할 수 있습니다 .

어떻게 이런 일이 일어나는지 테스트 방법을 만들어 보겠습니다. 다시 테스트에서 ArrayDeque 클래스를 계속 사용할 것입니다 .

@Test
void givenADeque_whenAddOrRemoveLastElement_thenTheLastElementCanBeAddedOrRemoved() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 2nd element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(3);

    //insert element to the bottom of the stack
    myStack.addLast("I am the NEW element.");
    assertThat(myStack.size()).isEqualTo(4);
    assertThat(myStack.peek()).isEqualTo("I am the 3rd element.");

    //remove element from the bottom of the stack
    String removedStr = myStack.removeLast();
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(removedStr).isEqualTo("I am the NEW element.");
}

테스트에서 먼저 addLast () 메서드를 사용하여 스택의 맨 아래에 새 요소를 삽입합니다 . 삽입이 성공하면 removeLast () 메서드를 사용하여 제거하려고합니다 .

테스트를 실행하면 통과합니다.

따라서 Deque 는 LIFO 계약도 준수하지 않습니다 .

5.3. Deque 기반 LifoStack 구현

LIFO 계약을 준수하기 위해 간단한 LifoStack 인터페이스를 만들 수 있습니다 .

public interface LifoStack<E> extends Collection<E> {
    E peek();
    E pop();
    void push(E item);
}

LifoStack  인터페이스의 구현을 만들 때 Java 표준 Deque 구현을 래핑 할 수 있습니다 .

의는 만들어 보자 ArrayLifoStack를 빨리 이해하는 예로 클래스를 :

public class ArrayLifoStack<E> implements LifoStack<E> {
    private final Deque<E> deque = new ArrayDeque<>();

    @Override
    public void push(E item) {
        deque.addFirst(item);
    }

    @Override
    public E pop() {
        return deque.removeFirst();
    }

    @Override
    public E peek() {
        return deque.peekFirst();
    }

    // forward methods in Collection interface
    // to the deque object

    @Override
    public int size() {
        return deque.size();
    }
...
}

ArrayLifoStack 클래스에서 알 수 있듯이 LifoStack 인터페이스 및 java.util.Collection 인터페이스에 정의 된 작업 만 지원합니다 .

이런 식으로 LIFO 규칙을 위반하지 않습니다.

6. 결론

Java 1.6부터 java.util.Stack 과 java.util.Deque를 모두  LIFO 스택으로 사용할 수 있습니다. 이 기사에서는이 두 유형의 차이점에 대해 설명했습니다.

또한 LIFO 스택으로 작업하기 위해 Stack 클래스 에서 Deque 인터페이스를 사용해야하는 이유도 분석했습니다 .

또한 예제를 통해 논의했듯이 Stack 과 Deque는 모두 LIFO 규칙을 어느 정도 위반합니다.

마지막으로 LIFO 계약에 따라 스택 인터페이스를 만드는 한 가지 방법을 보여주었습니다.

항상 그렇듯이 전체 소스 코드는 GitHub에서 사용할 수  있습니다 .