큐(Queue)

[wongakim-99]

Python으로 구현하는 자료구조 : Queue

[wongakim-99]

1. 큐(Queue)

큐는 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조이다. 큐는 줄서기를 생각하면 된다.

• 선입선출 (First-In First Out : FIFO) 의 자료구조이다. 먼저 들어간 데이터가 먼저 나오는 구조를 따른다
• 일상생활의 관공서, 은행, 우체국, 병원 등 번호표를 이용한 줄서기 등을 예시로 들 수 있다.

2. 큐의 특징

1. 삽입 (Enqueue) ㄴ 데이터를 큐의 뒤쪽(rear) 에 추가한다.
2. 삭제 (Dequeue) ㄴ 데이터를 큐의 앞쪽(front) 에서 제거한다.
3. 프론트 (Front) ㄴ 가장 먼저 삽입된 데이터의 위치이다.
4. 리어 (Rear) ㄴ 가장 마지막에 삽입된 데이터의 위치이다.

3. 큐의 종류

1. 일반 큐 (Simple Queue) ㄴ 기본적인 FIFO 구조를 따르는 큐이다.(선형 큐)
2. 원형 큐(Circular Queue) ㄴ 큐의 마지막(rear) 이 끝나면 처음 (front)으로 연결되어 공간 낭비를 줄이는 구조이다.
3. 우선순위 큐 (Priority Queue) ㄴ 데이터에 우선순위를 부여하여, 우선순위가 높은 데이터가 먼저 처리된다. FIFO가 아닐 수도 있다.
4. 이중 큐 (Dequeue, Double-Ended Queue) ㄴ 데이터를 앞(front) 과 뒤 (rear)에서 모두 삽입하고 삭제할 수 있는 구조이다.