큐(Queue) 구현 및 테스트 (JavaScript, Python)

1.  Queue 개념

■ 선입선출 (FIFO): 큐에서 데이터는 먼저 들어온 순서대로 출력된다.

■ enqueue: 큐에 데이터를 삽입하는 작업

■ dequeue: 큐에서 데이터를 제거하는 작업

■ Front: 큐의 앞쪽 (데이터가 제거되는 곳)

■ Rear[또는 Tail]: 큐의 뒤쪽 (새로운 데이터가 추가되는 곳)

 

2. 핵심요약

■ BFS (너비 우선 탐색, Breadth-First Search) 알고리즘에서는 Queue 자료구조가 필수적으로 활용된다.

■ BFS는 그래프나 트리에서 시작 노드에서부터 인접한 노드들을 차례대로 방문하여 탐색을 진행한다.

■ 이때 선입선출(FIFO) 방식이 BFS 탐색의 특성과 잘 맞아떨어지기 때문에 Queue 자료구조를 사용한다.

 

3. JavaScript 코딩

// Queue 클래스를 정의
class Queue {
    // 생성자: Queue 클래스 인스턴스를 생성할 때 실행됨
    constructor() {
        this.items = {};        // 데이터를 저장할 객체, index를 키로 사용하여 값들을 저장
        this.headIndex = 0;     // 큐의 앞부분을 나타내는 인덱스
        this.tailIndex = 0;     // 큐의 뒷부분을 나타내는 인덱스
    }
    
    // 큐에 아이템을 추가하는 메소드
    enqueue(item) {
        this.items[this.tailIndex] = item;  // tailIndex 위치에 item을 추가
        this.tailIndex++;                   // tailIndex를 증가시켜 큐의 끝을 업데이트
    }
    
    // 큐에서 아이템을 제거하는 메소드
    dequeue() {
        const item = this.items[this.headIndex];    // headIndex 위치에서 아이템을 가져옴
        delete this.items[this.headIndex];          // 해당 위치의 아이템을 삭제하여 메모리에서 제거
        this.headIndex++;           // headIndex를 증가시켜 큐의 앞부분을 업데이트
        return item;                // 제거된 아이템을 반환
    }
 
    // 큐의 앞부분에 있는 아이템을 반환하는 메소드 (삭제하지 않음)
    peek() {
        return this.items[this.headIndex];         // headIndex 위치의 아이템을 반환
    }
 
    // 큐에 있는 아이템의 개수를 반환하는 메소드
    getLength() {
        return this.tailIndex - this.headIndex;   // 큐에 남아있는 아이템의 개수를 계산
    }
}
 
// Queue 클래스를 외부 모듈로 내보내기
module.exports = Queue;
 
// 큐 인스턴스를 생성
let queue = new Queue();
queue.enqueue(5);       // 큐: 5
queue.enqueue(3);       // 큐: 5, 3
queue.dequeue();        // 큐: 3
queue.enqueue(4);       // 큐: 3, 4
queue.enqueue(1);       // 큐: 3, 4, 1
queue.dequeue();        // 큐: 4, 1
queue.enqueue(7);       // 큐: 4, 1, 7
queue.enqueue(6);       // 큐: 4, 1, 7, 6
queue.dequeue();        // 큐: 1, 7, 6
 
// 큐가 비어있지 않으면 계속해서 dequeue를 통해 큐의 모든 아이템을 출력
while (queue.getLength() > 0) {
    console.log(queue.dequeue());  // 큐의 앞부분 아이템을 출력 후 제거
}
 

 

4. 파이썬 코딩

■ Python에서는 collections.deque를 사용하여 큐 자료구조를 구현할 수 있다.

■ deque는 **덱(Deque, Double-ended Queue)**을 구현한 자료구조로, 큐와 스택 모두에 효율적으로 사용할 수 있다.

■ deque는 큐의 앞과 뒤에서 삽입과 삭제가 모두 효율적이기 때문에 큐 구현에 매우 적합하다.

from collections import deque
 
class Queue:
    def __init__(self):
        self.items = deque()
 
    def enqueue(self, item):
        self.items.append(item)  # 큐에 아이템 추가 (뒤에 추가)
 
    def dequeue(self):
        if self.get_length() > 0:
            return self.items.popleft()  # 큐에서 아이템 제거 (앞에서 제거)
        return None  # 큐가 비었을 경우 None 반환
 
    def peek(self):
        if self.get_length() > 0:
            return self.items[0]  # 큐의 첫 번째 아이템 확인 (삭제하지 않음)
        return None
 
    def get_length(self):
        return len(self.items)  # 큐의 크기 반환
 
# Test
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.dequeue()
queue.enqueue(4)
queue.enqueue(5)
queue.enqueue(6)
queue.dequeue()
 
while queue.get_length() > 0:
    print(queue.dequeue())