3. 큐 ( Queue, JavaScript 구현 )

큐 ( Queue )

스택은 보통 큐와 비교해서 알아보는데 스택에 대해 알아봤고, 이번엔 큐에 대해 알아보자.

 

Queue 란?

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.

영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

구조

큐는 put(insert)와 get(delete)을 이용하여 구현된다.

put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다.

front(head)와 rear(tail)는 데이터의 위치를 가리킨다.

front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다.

또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow),

큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다.

 

종류

• 선형
  막대 모양으로 된 큐, 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.
• 환형
  선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.

 

언제 사용하는가?

1. 우선순위가 같은 작업 예약 ( ex 인쇄 대기열 )
2. 선입선출이 필요한 대기열 ( ex 티켓 카운터 )
3. 멀티 프로그래밍
4. 비동기 데이터 교환 ( 파일I/O, pipes, sockets )
5. 콜센터 고객 대기시간, 마트 계산대 수 결정 등
6. 다른 알고리즘의 보조 자료구조 ( 트리 Level Order Traversal)

 

구현

먼저 기본적인 큐를 구성해보자.

const Queue = (() => {
    class Queue {
        constructor() {
            this.count = 0;
            this.front = null;
            this.rear = null;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Queue;
})()

Queue 클래스에서 count는 큐의 크기, front와 rear는 처음과 끝 자료를 의미하고,

각 자료는 Node 클래스의 인스턴스로 구성된다.

1. put()

put(value) {
    const node = new Node(value);
    if ( !this.front ) {
        this.front = node;
    } else {
        this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
}

만약 헤드가 비어있다면 헤드에 추가, 아니라면 rear의 next와 rear에 순서대로 추가해주고, 크기를 리턴

2. get()

get() {
    if ( !this.front ) {
        return false;
    }
    const data = this.front.data;
    this.front = this.front.next;
    this.count--;
    return data;
}

헤드가 없다면 false를 리턴해 get이 일어나지 않도록 하고, 이외의 경우라면 data에 추출할 데이터를 담고, 헤드를 뒤로 한칸밀고 추출한 데이터를 리턴.

3. head(), tail()

head() {
    return this.front && this.front.data;
}

tail() {
    return this.rear && this.rear.data;
}

스택과 비슷하지만 자료의 삽입, 제거 방식이 조금 다르므로 차이를 알고 필요한 부분에 쓸 수 있으면 유용할 것 같다.

 

전체 코드

const Queue = (() => {
    class Queue {
        constructor() {
            this.count = 0;
            this.front = null;
            this.rear = null;
        }

        put(value) {
            const node = new Node(value);
            if ( !this.front ) {
                this.front = node;
            } else {
                this.rear.next = node;
            }
            this.rear = node;
            return ++this.count;
        }

        get() {
            if ( !this.front ) {
                return false;
            }
            const data = this.front.data;
            this.front = this.front.next;
            this.count--;
            return data;
        }

        head() {
            return this.front && this.front.data;
        }

        tail() {
            return this.rear && this.rear.data;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Queue;
})()