5. 큐(Queue)

1. 큐(Queue)

1-1. 큐(queue)

 

- 정의 및 사용 

  * 큐는 일상생활에서 줄을 서 기다리는 것과 유사한 자료 구조이다.

 

 - 작동 방식(선입선출, FIFO) 

  * 큐는 선입선출 ( First In First Out) 구조를 가진다.

  * 먼저 들어간 데이터가 먼저 나오는 순서로 작동한다.

 

 - 주요 용어

  * Front : 큐의 앞쪽 끝을 가리킨다. 데이터를 꺼내는(dequeue) 위치이다.

  * Rear/Back : 큐의 뒤쪽 끝을 나타낸다. 데이터를 넣는(enqueue) 위치이다.

 

- 기본 연산

 * Enqueue : 큐의 뒤쪽(rear)에 데이터를 추가한다.

 * Dequeue : 큐의 앞쪽(front)에서 데이터를 꺼낸다.

 

1-2. 스택(Stack)과의 비교

 - 스택은 후입선출(Last In First Out, LIFO) 구조를 가진다. 즉 마지막에 들어간 데이터가 가장 먼저 나온다.

 - 스택에서 top이라는 단일 접근점을 통해 데이터를 추가(push)하거나 제거(pop)한다.

 - 큐는 입구와 출구가 별도로 존재하며, 한쪽 끝에서 데이터를 추가하고 반대편에서 데이터를 제거하는 구조이다.

 

1-3. 큐 구현 설명

1-3-1. Node 클래스

 - 각 큐 요소를 나타내는 클래스이다.

 - data는 노드의 값을 저장하고, next는 다음 노드를 가리키는 포인터이다.

 

1-3-2. Queue 클래스

 - 큐의 기본 구조를 정의한다.

 - front는 큐의 첫 번째 요소를, rear는 큐의 마지막 요소를 가리킨다.

 - __init__ : 큐를 초기화한다. 

 

1-3-3. Enqueue 연산

 - 큐에 끝에 새 요소를 추가하는 연산이다.

 - 큐가 비어있으면 front와 rear 모두 새 노드를 가리킨다.

 - 큐가 비어있지 않으면, rear.next를 새 노드로 설정하고, rear를 새 노드로 업데이트한다.

 

1-3-4. Dequeue 연산

 - 큐의 앞에서 요소를 제거하고 그 값을 반환하는 연산이다.

 - front를 다음 노드로 이동시키고, 이전 front 노드의 데이터를 반환한다.

 - 큐가 비게 되면 front와 rear 모두 None를 가리킨다.

 

1-3-5. IsEmpty 연산

 - 큐가 비어있는지 확인하는 연산이다.

 - front가 None이면 큐가 비어 있는 것으로 판단한다.