큐 (3) - 덱 (Dequeue)

1. Double-ended Queue

• Dequeue은 큐의 출력을 의미하기도 하지만, Double-ended Queue의 준말이기도 하다.
• 즉, Dequeue(덱)은 양쪽에서 넣고 빼고가 가능한 특이한 큐를 의미한다.
• pushBack, pushFront로 뒤/앞으로 넣을 수 있고, popBack, popFront로 뒤/앞에서 뺄 수 있다.
• 덱은 스택과 큐를 합쳐놓은것과 같은데, pushFront + popBack 혹은 pushBack + popFront는 큐
• pushFront + popFront 혹은 pushBack + popBack은 스택과 동일하게 기능한다. (이해 쉽다)

 

2. Dequeue의 종류와 특징

1) Dequeue의 종류

• 스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
• 셀프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱

 

2) Dequeue의 특징

• 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없다.
• 보통 두가지 이유중 하나로 사용하게 됨. (입력과 출력을 추가하는 방식으로 사용)
• 큐에서 양쪽에서 출력할 수 있어야하거나 (스크롤, scroll) - 입력 제한
• 스택에서 양쪽에서 입력하고 싶은경우 (셸프, shelf) - 출력 제한

 

3. Dequeue의 용도

1) 보통 스케줄링을 사용하게 됨

• 스케줄링이 복잡해질수록 큐와 스택보다 덱이 더 효율이 잘 나오는 경우가 있음

 

2) 우선순위를 조절하게 될 때 

• ex) 옛날에 있던걸 우선순위를 높이기 위해서는 앞에서 빼낼수 있어야 되는데 스택에서는 불가능함
• ex) 최근에 들어온걸 우선순위를주고 싶은데 이 역시 큐의 구조에서는 불가능함
• 결국 앞뒤로 다 인출이 가능한 덱(Deque)만이 이 조건을 충족시킴

 

4 Implementation

• Double Linked List를 이용해서 Dequeue를 구현했다.
• Array로도 구현할..수 있으나 너무 오래걸리고 복잡해서 리스트로 쉽게 구현했다.

package data_structure.queue;

/**
 * @author : Hyunwoong
 * @when : 4/30/2020 10:13 PM
 * @homepage : https://github.com/gusdnd852
 */
public class ListDequeue {

    private Node front;
    private Node rear;
    private int size = 0;

    public void pushBack(int data) {
        Node node = new Node();
        node.data = data;

        if (front == null) {
            front = rear = node;
        } else {
            Node r = rear;
            rear = node;
            r.next = rear;
            node.prev = r;
        }

        size++;
    }

    public void pushFront(int data) {
        Node node = new Node();
        node.data = data;

        if (front == null) {
            front = rear = node;
        } else {
            Node f = front;
            front = node;
            f.prev = front;
            node.next = f;
        }

        size++;
    }

    public int popFront() {
        int data = front.data;
        front = front.next;
        front.prev = null;
        
        size--;
        return data;
    }

    public int popBack() {
        int data = rear.data;
        rear = rear.prev;
        rear.next = null;

        size--;
        return data;
    }
    
    public int size(){
        return size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (Node node = front; node != null; node = node.next) {
            builder.append(node.data);
            if (node.next != null) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    private class Node {
        private Node next;
        private Node prev;
        private int data;
    }
}

 

5. Reference

[자료구조] 스택, 큐, 덱

06-자료구조: 덱(Deque)

스택, 큐, 덱(Stack, queue, deque)의 특징에 대해 설명해보세요!