알고리즘의 Queue: 데이터 구조의 중요한 부분

 

안녕하세요! goodchuck 입니다!

블로그에 방문해주셔서 감사합니다!

 

 Queue의 개념

 

Queue(큐)는 선입선출(FIFO, First-In-First-Out) 원칙에 따라 동작하는 데이터 구조입니다. 가장 먼저 삽입된 항목이 가장 먼저 삭제됩니다. 이는 은행의 대기열이나 티켓 카운터에서 번호표를 받는 것과 유사한 개념으로 이해할 수 있습니다.

 

 Queue의 등장 이유

 

Queue는 다음과 같은 상황에서 사용됩니다:

- 작업 대기열: 여러 작업이 동시에 발생할 때, 순서대로 처리하기 위해 Queue를 사용합니다.

- 네트워크 통신: 네트워크에서 수신된 데이터를 순서대로 처리하기 위해 Queue를 사용합니다.

- 프린터 대기열: 여러 사용자가 프린터를 사용할 때, 출력할 문서를 순서대로 저장하기 위해 Queue를 사용합니다.

 

 Queue의 장단점

 

**장점:**

- 데이터의 삽입 및 삭제가 빠름

- 선입선출의 특성으로 인한 효율적인 자료 관리

 

**단점:**

- 고정된 크기의 제한된 메모리를 사용

- 데이터의 중간 삽입, 삭제가 어려움

 

 Queue의 시간복잡도

 

Queue의 주요 연산인 enqueue(삽입)와 dequeue(삭제)는 모두 상수 시간 O(1)에 수행됩니다. 따라서 Queue의 크기에 관계없이 항상 일정한 시간이 소요됩니다.

 

 Queue와 비교되는 다른 알고리즘: 스택(Stack)

 

큐(Queue)는 스택(Stack)과 반대되는 개념으로, 선입선출(FIFO)의 원칙에 따라 동작합니다. 스택과는 달리 가장 먼저 삽입된 항목이 가장 먼저 삭제됩니다.

 

 Queue의 실제 활용도

 

Queue는 다음과 같은 분야에서 실제로 활용됩니다:

- 프로세스 스케줄링에서의 작업 대기열

- 운영 체제에서의 입출력 대기열

- 네트워크에서의 데이터 전송 대기열

- 쓰레드 풀(Thread Pool)에서의 작업 처리

 

 Node.js로의 Queue 구현

class Queue {

    constructor() {

        this.items = [];

    }



    enqueue(item) {

        this.items.push(item);

    }



    dequeue() {

        if (!this.isEmpty()) {

            return this.items.shift();

        }

    }



    front() {

        if (!this.isEmpty()) {

            return this.items[0];

        }

    }



    isEmpty() {

        return this.items.length === 0;

    }

}



// Queue 인스턴스 생성

const queue = new Queue();



// Queue에 데이터 추가

queue.enqueue(1);

queue.enqueue(2);

queue.enqueue(3);



// Queue에서 데이터 제거

console.log(queue.dequeue()); // 출력: 1

 

이상 글 읽어주셔서 감사합니다 다음에도 또 뵐수있길 빌겠습니다!