[JAVA] 스택(Stack) vs 덱(Deque)

Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공합니다.

Stack<E> st = new Stack<E>();

더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 됩니다.

Deque<E> st = new ArrayDeque<E>();

단, ArrayDeque 클래스는 Stack 클래스와는 달리 search() 메소드는 지원하지 않습니다.

Java SE 6부터 지원되는 ArrayDeque 클래스는 스택과 큐 메모리 구조를 모두 구현하는데 가장 적합한 클래스입니다.

---

위의 내용은 자바 도큐먼트 사이트에서 직접 명시된 내용입니다.

 

왜 이런 구조로 되어있는 것일까요??

 

그에 대한 분석이 2013년에 BaddotRobot이라는 사이트에서 다루고 있었습니다.

내용을 대강 요약해보면 이렇습니다.

 

Java는 오랫동안 "잘못 작성된" Stack 구현을 가지고 있습니다.

( Java는 Stack의 기본 원칙을 무시하고 Vector 클래스를 상속받습니다 )

• Vector를 상속받는 다른 Stack클래스를 새로 만들경우 LIFO(후입선출)원칙이 아닌 중간에 데이터가 삽입되거나 삭제될 수 있는 치명적 문제 발생

 

하지만! Java는 이전 버전과의 호환성 원칙에 따라 실수를 수정할 수가 없다고 합니다.(Sun / Oracle)

 

대신 스택을 스택답게 사용하기 위해 저희는 코드를 일부 유연하게 overriding하여 수정이 가능하다고 알려주고 있습니다.

그 방법은 다음과 같습니다.

 

public interface Stack<T> {
    void push(T object);
    T pop();
}

먼저, 다음과 같이 사용할 메소드들을 정의한 Stack 인터페이스를 만들어 줍니다.

(자바 API에서 Stack 인터페이스는 따로 존재하지 않습니다.)

 

public class DequeStack<T> implements Stack<T> {

    private final Deque<T> deque = new ArrayDeque<T>();

    @Override
    public void push(T object) {
        deque.addFirst(object);
    }

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

그 후, DequeStack이라는 클래스를 만들고 Stack의 일부 기능인 push와 pop 메소드만을 따로 오버라이딩하여 사용합니다.

이런 식으로 사용할 경우 Deque가 가지고 있는 큐의 기능을 제한할 수 있습니다.

하지만 implements로 가져왔기 때문에 Deque의 기능을 완전히 제한했다고 볼 수 없고 일부 가렸다고 표현하는 것이 좀 더 정확합니다.

 

public class BoundedStack<T> extends DequeStack<T> {

    // ...

    @Override
    public void push(T object) {
        if (count < UPPER_BOUND) {
            count++;
            deque.addFirst(object);
        }
    }

    @Override
    public T pop() {
        count--;
        return deque.removeFirst();
    }
}

따라서 다음과 같이 위에서 만든 DequeStack을 상속받아 한번더 오버 라이딩해주는 것이 더 안전하다 라고 할 수 있습니다. 이렇게 만든 경우 Vector클래스와 Deque클래스 둘 중 어느 것이라도 BoundedStack클래스와 is-a관계가 성립이 되지 않기 때문에 안전한 방법입니다.

아래와 같은 느낌으로 보시면 될것 같습니다.

 

요지는 이렇지만 알고리즘을 풀 때 마다 매번 이렇게 구현할 수는 없으니까

push()와 pop()만을 필요로 한다고 한다면 ArrayDeque를 사용하여 stack을 사용하면 좋을것 같습니다.

 

Vector를 상속받는 Stack의 장점이라고 하면 아무래도 search()메소드의 존재입니다.

만약 배열처럼 특정 값의 위치를 스택에서 알고 싶다고 한다면 Stack을 사용하시면 됩니다.

하지만, 사실 이 시점에서 스택이라고 불리기는 좀 애매한(?) 자료구조인것은 확실한것 같습니다.

---

** 참고 사이트

http://tcpschool.com/java/java_collectionFramework_stackQueue

https://docs.oracle.com/javase/8/docs/api/

http://baddotrobot.com/blog/2013/01/10/stack-vs-deque/