큐(Queue)

---

큐(Queue)

큐(Queue)?

큐는 FIFO(First In First Out)이라는 개념을 가진 선형 자료구조이며 먼저 들어온 요소가 먼저 나간다. Linear Queue(선형 큐), Circular Queue(환형 큐)가 존재한다.

front : 큐의 맨 앞 요소를 가르킨다.
Rear : 큐의 맨 마지막 요소를 가르킨다.
EnQueue : 큐에 요소를 삽입
DeQueue : 큐에 요소를 삭제

Linear Queue(선형 큐)

• 배열 구현

배열로 구현이 가능하지만 자바스크립트는 배열이 동적으로 커져 배열이 커지면 front, rear 값이 무한이 증가할 수 있다.

배열의 빈 요소가 있으면 앞 땅기는 작업이 별도로 필요하며 이는 O(n)의 시간복잡도를 가진다.

class Queue {
    constructor() {
        this.queue = []
        this.front = 0;
        this.rear = 0;
    }

    enqueue(value) {
        this.queue[this.rear++] = value;
    }

    dequeue() {
        const value = this.queue[this.front];
        
        delete this.queue[this.front];
        this.front += 1;

        return value;
    }

    peek() {
        return this.queue[this.front];
    }

    size() {
        return this.rear - this.front;
    }
}

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4

Circular Queue(환형 큐)

Head = Front
Tail = Rear
EnQueue : 큐에 요소를 삽입
DeQueue : 큐에 요소를 삭제

환형 큐는 front와 rear가 이어져있는 큐다.

보통 배열로 구현하며 연결 리스트는 이점이 없어서 배열 구현이 편리하다.

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    enqueue(newValue) {
        const newNode =  new Node(newValue);

        if(this.head === null) {
            this.head = this.tail = newNode;
        }
        else {
            this.tail.next = newNode;
            this.tail = newNode;
        }

        this.size += 1;
    }

    dequeue() {
        const value = this.head.value;

        this.head = this.head.next;
        this.size -= 1;

        return value;
    }

    peek() {
        return this.head.value;
    }
}

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4

shift() 함수?

사실 자바스크립트에서는 큐를 만들지 않고도 일반 배열의 메소드로 큐를 활용할 수 있다.

push()함수로 enqueue를, shift()함수로 dequeue를 이용할 수 있다. 하지만 shift()함수는 생각한 것 처럼 동작하지 않는다.

shift()함수는 O(n)의 선형 시간복잡도를 가지며 데이터가 커 배열의 길이가 길어지면 많은 시간이 걸려 데이터가 많다면 큐를 구현하여 enqueue 기능을 구현하는 것이 더 효과적이다.