[자료구조] 덱(Deque)의 이해와 구현 with 자바

 

🤔 Deque?

Deque는 'Double Ended Queue'의 약자로 큐의 기능을 확장한 자료구조로 볼 수 있습니다.

큐는 뒤쪽(rear)에서 삽입 앞쪽(front)에서 삭제 연산이 가능했다면 기능을 확장하여 큐의 양쪽에서 모두 삽입과, 삭제가 가능합니다.

즉, stack의 LIFO과 queue의 FIFO 특징을 모두 사용할 수 있습니다.

사진출처:https://leejinseop.tistory.com/39

 

 

✔ Deque 구현하기

큐를 확장한 자료구조임으로 이전에 만든 큐 인터페이스를 implements하여 기능을 추가하여 구현 하겠습니다.

실제 자바의 덱 자료구조에는 여러가지 기능을 하는 메서드들이 더 있지만, 덱의 가장 큰 특징인 양쪽에서의 삽입,삭제에 관한 기능을 구현하도록 하겠습니다.

메소드명	리턴 타입	설명
offerFirst(E e)	E	큐의 첫 번째(Front)에 요소를 추가합니다
offerLast(E e)	E	큐의 마지막(Rear)에 요소를 추가합니다.
pollFirst()	E	큐의 첫 번째(Front)요소를 제거하고 제거 된 요소를 반환합니다.
pollLast()	E	큐의 마지막(Rear)요소를 제거하고 제거 된 요소를 반환합니다.
peekFirst()	E	큐의 첫 번째(Front)요소를 제거하지 않고 반환합니다.
peekLast()	E	큐의 마지막 (Rear)요소를 제거하지 않고 반환합니다.

먼저 큐와 마찬가지로 LinkedList기반으로 덱을 구현하려고 합니다.

그러기 위해서 데이터를 담을 Node를 구현해 보겠습니다.

 

Node.java

덱은 큐와 달리 양방향에서 삽입,삭제가 이루어지기 때문에 노드의 다음(next), 이전(prev)에 대한 연결(link)이 필요합니다.

그래서 참조할 다음과 이전 노드들을 선언하고 생성자를 통해서 초기화 해줍니다.

public class Node<E> {

    E data;
    Node<E> next; // 다음 노드
    Node<E> prev; // 이전 노드

    public Node(E data){
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

LinkedListDeque.java

public class LinkedListDeque<E> implements Queue<E> {

    private Node<E> front; // 덱의 가장 앞의 노드
    private Node<E> rear; // 덱의 가장 뒤의 노드
    private int size; // 덱 전체 요소의 개수

    //생성자를 통해 초기화
    public LinkedListDeque() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    @Override
    public boolean offer(E e) {
        return offerLast(e);
    }

    public boolean offerFirst(E e){
        Node<E> newNode = new Node<>(e); // 추가할 노드
        newNode.prev = front; // 추가할 노드의 이전 노드로 가장 앞(front)노드를 연결

        // front가 null이 아닐경우 즉 덱이 비어있지 않을 경우
        if( front != null ){
            front.next = newNode; // 덱의 front노드의 다음노드를 추가할 newNode와 연결한다.
        }
        front = newNode; // 덱의 front노드로 newNode를 설정
        size++; // 덱 요소의 개수를 증가시킨다

        // front로 설정된 노드의 이전 노드가 null이면 즉, 덱이 비어 있었다면
        if( front.prev == null ){
            rear = front; // 요소가 추가할 노드 1개이기 때문에 front와 rear를 같게 설정한다
        }
        return true;
    }

    public boolean offerLast(E e){
        Node<E> newNode = new Node<>(e); // 추가할 노드
        newNode.next = rear; // 추가할 노드의 다음 노드로 가장 뒤(rear)노드를 연결

        // rear가 null이 아닐경우 즉, 덱이 비어있지 않을 경우
        if( rear != null ){
            rear.prev = newNode; // 덱의 rear노드의 이전노드를 추가할 newNode와 연결한다.
        }
        rear = newNode; // 덱의 rear노드로 newNode를 설정
        size++; // 덱 요소의 개수를 증가시킨다

        // rear로 설정된 노드의 다음 노드가 null이면 즉, 덱이 비어 있었다면
        if( rear.next == null ){
            front = rear; // 노드가 1개이기 때문에 front와 rear를 같게 설정한다
        }
        return true;

    }

    @Override
    public E poll() {
        return pollFirst();
    }

    public E pollFirst(){
        if( size == 0 ){
            return null;
        }
        E data = front.data; // 덱의 front data를 변수에 변수에 저장

        Node<E> prevNode = front.prev; // front 노드의 이전 노드를 변수에 저장

        // 현재 설정된 front노드 값 제거
        front.data = null; 
        front.next = null;

        // front노드의 이전노드가 null이 아니라면 즉, 덱의 요소가 2개 이상이라면
        if( prevNode != null ){
            prevNode.next = null; // 이전 노드의 다음 노드를 삭제
        }
        front = prevNode; // 덱의 front에 이전 노드를 설정한다
        size--; // 덱의 요소의 개수를 감소

        // 위의 연산으로 덱의 요소가 0이라면
        if( size == 0){
            rear = null; // 덱의 rear 을 null로 설정(삭제)한다
        }

        return data;
    }

    public E pollLast(){
        if( size == 0 ){
            return null;
        }
        E data = rear.data;

        Node<E> nextNode = rear.next;

        rear.data = null;
        rear.next = null;

        if( nextNode != null ){
            nextNode.prev = null;
        }
        rear = nextNode;
        size--;

        if( size == 0){
            rear = null;
        }

        return data;
    }



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

    public E peekFirst(){
        if( size == 0 ){
            return null;
        }

        return front.data;
    }

    public E peekLast(){
        if( size == 0 ){
            return null;
        }

        return rear.data;
    }
}

📌

덱의 핵심이 되는 양쪽에서의 추가,삭제,추출 메서드들을 구현해 보았습니다.

덱은 양방향으로 큐와 달리 앞뒤 노드를 연결(link)해야하기 때문에 조금 더 복잡한 것 같습니다.

하지만 front와 rear의 방향과 노드의 참조를 잘 생각해본다면 이해가 편할 것 입니다.

또한 last와 first가 붙은 메서드들은 반대로 하면 되기 때문에 하나를 구현한다면 나머지 하나는 쉽게 구현할 수 있습니다.

 

---

📚 Reference : https://st-lab.tistory.com/187