[JS] 연결 리스트로 큐(Queue) 구현

자료구조

[JS] 연결 리스트로 큐(Queue) 구현

okonomiyakki 2023. 9. 17. 03:17

728x90

대부분의 Queue 자료구조를 사용하는 상황에서는 최대 크기가 얼마나 될지 예측하기 어려운 경우가 많다.

때문에 연결 리스트로 구현한 Queue 를 사용하는 것이 훨씬 합리적일 수 있다.

예를 들어 대규모 이벤트 스트림 처리나 비동기 작업 처리를 위해 사용될 수 있다.

메시지 발행량이 예측하기 어려운 경우, Queue 의 크기를 불규칙하게 변할 수 있기 때문이다.

이런 상황에서 Queue 의 크기를 동적으로 조절하기 위한 대비를 해야한다.

이를 위해 Queue 의 최대 크기를 설정하고 이에 따른 예외 처리 방법을 결정할 필요가 있는데,

요청을 기다리는 동안 새로운 요청을 거부하거나 데이터 일부를 대기열에서 제거하는 등의 방법을 고려할 수 있다.

이러한 스케줄링 작업을 위한 Queue 를 단반향 원형 연결 리스트로 구현해보고자 한다.

구현할 메서드

enqueue(e) - 큐의 끝 위치에 원소 e를 삽입한다.
dequeue() - 큐의 맨 앞에 위치한 원소를 반환하고 queue에서 제거한다.
peek(e) - 큐의 맨 앞에 위치한 원소를 반환한다.
isEmpty() - 큐가 비었는지 확인한다.

노드 생성자

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

연결 리스트를 사용하기때문에 노드 객체를 만들기 위한 생성자를 구현해주어야 한다.

Queue 생성자

class Queue {
    constructor() {
        this.tail = null; // 큐의 맨 뒤 위치
        this.size = 0;
    }
}

Queue 의 마지막 위치를 가리키는 포인터를 만들어준다.

단일 원형 연결 리스트에서는 tail 이 첫 번째 노드에 접근 가능하기 때문에, head 를 참조하는 포인터 변수는 선언하지 않는다.

enqueue()

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

        if (this.isEmpty()) {
              newNode.next = newNode // 새로 추가된 노드가 자기 자신을 가리키도록 한다.
            this.tail = newNode; // tail을 새로 추가된 노드로 초기화 한다.
        } else {
            newNode.next = this.tail.next; // 새로 추가된 노드가 첫번 째 노드를 가리키도록 한다.
            this.tail.next = newNode; // 현재 tail인 노드가 새로 추가된 노드를 가리키도록 한다.
            this.tail = newNode; // 현재의 tail을 새로 추가된 노드로 초기화 한다.
        }

        this.size++;
    }

새로운 요소가 추가되면 tail이 가리키는 노드를 새롭게 초기화 해주고,

각 노드를 next로 연결해주는 과정을 구현한다.

dequeue()

    dequeue() {
        if (this.isEmpty()) return null; // Queue에 요소가 존재하지 않으면 null을 반환한다.

        const front = this.tail.next; // tail의 다음 노드를 새로운 front 변수로 초기화 해준다.
        this.tail.next = front.next; // tail의 다음 노드를 front의 다음 노드로 할당한다.

        this.size--;

        return front.data;
    }

해당 Queue 에서는 첫번 째 노드를 가리키는 별도의 포인터 변수를 사용하지 않기 때문에

현재의 메서드에서 tail 의 다음 노드를 front 로 초기화해주는 작업이 필요하다.

이후 front 노드와 연결된 노드 즉 front 노드 다음에 위치한 노드를 마지막 노드와 연결시켜주면 된다.

peek()

    peek() {
        if (this.isEmpty()) return null;

        return this.tail.next.data;
    }

Queue 의 맨 앞에 위치한 요소는 tail 의 다음에 위치해 있기 때문에 위와같이 구현해준다.

isEmpty()

    isEmpty() {
        return this.size === 0;
    }

Queue 의 크기가 0 이면 true 를 반환하고, 그렇지 않으면 false 를 반환한다.

전체 코드

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

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

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

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

        this.size++;
    }

    dequeue() {
        if (this.isEmpty()) return null;

        const front = this.tail.next;
        this.tail.next = front.next;

        this.size--;

        return front.data;
    }

    peek() {
        if (this.isEmpty()) return null;

        return this.tail.next.data;
    }

    isEmpty() {
        return this.size === 0;
    }
}

Big-O (시간 복잡도)

삽입 : O(1)
삭제 : O(1)
탐색 : O(n)

연결 리스트로 구현한 Queue 는 삽입 및 삭제 연산에서 O(1) 이다.

하지만 특정 위치의 원소를 탐색하려면 Queue 를 순회해야 하기 때문에,

Queue 의 연결 리스트를 따라가며 원하는 위치에 있는 원소를 찾는 경우의 시간 복잡도는 O(n) 이 된다.

그러므로 삽입 및 삭제 연산 보다 탐색 연산이 더 빈번하게 사용되는 곳에서는

배열로 구현된 Queue 를 사용하는 것이 더 효율적이다.

728x90