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

1.  Queue 개념

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

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

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

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

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

 

2. 핵심요약

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

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

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

 

3. JavaScript 코딩

■ JavaScript에서는 기본적으로 Queue를 위한 내장 함수나 클래스는 제공되지 않는다.

■ JavaScript에서 Queue는 배열(Array)을 이용하여 구현할 수 있다.

class Queue {
    constructor() {
        this.items = [];
        this.headIndex = 0;
        this.tailIndex = 0;
    }
 
    enque(item) {
        this.items[this.tailIndex] = item;
        this.tailIndex++;
    }
 
    deque() {
        const item = this.items[this.headIndex];
        delete this.items[this.headIndex];
        this.headIndex++;
        return item;
    }
 
    peek() {
        return this.items[this.headIndex];
    }
 
    getLength() {
        return this.tailIndex - this.headIndex;
    }
}
 
// Test
let queue = new Queue();
queue.enque(1);
queue.enque(2);
queue.enque(3);
queue.deque();
queue.enque(4);
queue.enque(5);
queue.enque(6);
queue.deque();
 
while (queue.getLength() > 0) {
    console.log(queue.deque());
}

 

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())