큐(Queue)

큐(Queue)?

표를 사기 위해 줄서는 것. 즉, 대기열을 의미합니다.

 

특징

데이터가 들어오는 위치가 가장 뒤에 있고, 데이터가 나가는 위치는 가장 앞에 있어서 먼저 들어오는 데이터가 먼저 나가게 됩니다. 이 때문에 FIFO(First In First Out), 선입선출 구조라고 불립니다.

데이터를 넣는 것은 put, 데이터를 꺼내는 것은 get 이라는 메소드를 사용합니다. 데이터를 넣는 위치는 rear(tail)이라 하고, 데이터를 꺼내는 위치는 front(head)라고 합니다.

 

어디에 쓰일까요?

• 게임 대기열
• 프린터 출력 데기열

 

장점

입력한 순서대로 처리하는 작업과 동작에 유리한 자료구조입니다.

 

단점

배열로 구현할 경우에는 데이터를 꺼내는 과정에서 인덱스 갱신이 불가피하기 때문에 O(n)의 시간복잡도를 갖습니다. 그러므로 좀 더 성능을 높이기 위해 연결리스트를 사용해 구현하거나, 배열을 사용해서 구현할 때는 원형 큐를 구현합니다.

 

구현

배열로 구현한 원형 큐

class QueueByArray {
    // 배열의 길이를 받아 원형 큐 생성
    constructor(val) {
        this.front = 0;
        this.rear = 0;
        this.size = val;
        this.arr = Array(val).fill(null);
    }
    // 삽입
    put(input) {
        // 원형 큐가 꽉 차있을 때는 삽입 불가
        if (this.arr[this.rear] !== null && this.rear === this.front) {
            console.log("데이터 입력 불가")
            return
        }
        this.arr[this.rear] = input;
        // rear가 배열의 길이를 넘지 못하도록 1을 더한 값을 길이로 나눈 나머지를 할당.
        this.rear = (this.rear + 1) % this.size;;
    }
    // 추출
    get() {
        // 원형 큐가 비어있을 때는 추출 불가
        if (this.arr[this.front] === null && this.front === this.rear) {
            console.log("데이터 추출 불가")
            return null;
        }
        const result = this.arr[this.front];
        this.arr[this.front] = null;
        // front가 배열의 길이를 넘지 못하도록 1을 더한 값을 길이로 나눈 나머지를 할당.
        this.front = (this.front + 1) % this.size;
        return result;
    }
}
let queue = new QueueByArray(2);
queue.put(1);
queue.put(2);
queue.put(3);
console.log(queue.get());
console.log(queue.get());
console.log(queue.get());
/* 실행 결과
데이터 입력 불가
1
2
데이터 추출 불가
null
*/

연결리스트로 구현한 큐

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
class QueueByLinkedList {
    constructor() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }
    // 삽입
    put(input) {
        // 입력 데이터로 새로운 노드 생성
        const newNode = new Node(input);
        if (this.size === 0) {
            this.front = newNode;
            this.rear = newNode;
        } else {
            // 마지막 node의 다음에 넣는다.
            this.rear.next = newNode;
            this.rear = newNode;
        }
        this.size++;
    }
    // 추출
    get() {
        // 큐가 비어있으면 null 반환
        if (this.size === 0) {
            return null
        }
        const result = this.front.data;
        // 길이가 1이면 front, rear를 동시에 null로 변경
        if (this.size === 1) {
            this.front = null;
            this.rear = null;
        } else { // 길이가 1 보다 크면 front만 다음 노드로 변경
            this.front = this.front.next;
        }
        this.size--;
        return result
    }
}
let queue = new QueueByLinkedList();
queue.put(1);
queue.put(2);
queue.put(3);
console.log(queue.get());
console.log(queue.get());
console.log(queue.get());
console.log(queue.get());
console.log(queue.get());

/* 실행 결과
1
2
3
null
null
*/

 

Reference

• https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)
• https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)