[파이썬] 큐(Queue) 자료구조 정리

Queue

• 스택이 바닥이 막힌 세로로 세운 통이라면 큐는 양쪽이 뚫린 가로로 된 통의 형태
• 삽입, 삭제의 위치가 제한적인 자료구조
• 데이터 값을 저장하는 기본적인 구조이며, 일차원의 선형 자료구조
• 선입선출(First In First Out, FIFO)의 형태를 가짐

활용

• 스트리밍(streaming)
• 너비 우선 탐색(Breath First Search, BFS)

Queue의 주요 연산

• enQueue(tiem) : 큐의 뒤쪽에 원소를 삽입하는 연산
• deQueue() : 큐의 앞쪽에서 원소를 삭제하고 반환하는 연산
• createQueue() : 공백 상태의 큐를 생성하는 연산
• isEmpty() : 큐가 공백상태인지를 확인하는 연산
• isFull() : 큐가 포화상태인지를 확인하는 연산
• Qpeek() : 큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산

큐의 기본 연산과정

1. 공백 큐 생성 : createQueue() : → front = rear = -1
2. 원소 a 삽입 : enQueue(A): → front = -1 rear(A) = 0
3. 원소 b 삽입 : enQueue(B) → front = -1 A=0 rear(B) = 1
4. 원소 반환 삭제 deQueue() : → front인 A 삭제,

알아둘점

큐는 보통 front와 rear로 삽입 삭제 인덱스를 구현하지만 파이썬의 리스트 특성상 front가 굳이 필요하지 않기게 사용하지 않음

Queue의 종류

반응형

선형 큐

• 1차원 배열을 이용하여 큐를 구현한 형태
• 가장 간단하고 기본적인 형태(리스트 사용)

구현

1. 초기 공백 큐 생성 (크기 n인 1차원 리스트 생성)
2. 삽입으로 마지막 원소 뒤에 새로운 원소를 삽입하기 위해 rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련하고, 그 인덱스에 해당하는 리스트원소 Q[rear]에 item 저장

특징

• 삽입, 삭제의 처리 속도가 빠름
• 리스트의 크기를 고정하므로 사용할 큐의 크기만큼을 미리 확보해야 하므로 메모리의 낭비가 발생함 → 원형큐사용으로 메모리 절약
• 삽입 위치 : rear =rear + 1 / front = front +1

원형 큐

1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용

특징

• 초기 공백 상태 : front = rear = 0
• front와 rear의 위치가 리스트이 마지막 인덱스인 n-1를 가리킨 후, 논리적 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야함. 이를 위해 나머지 연산자 %를 사용
• 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠
• 삽입 위치 rear = (rear +1) % n / front = (front + 1) % n

파이썬의 리스트 특성을 사용한 큐

• 리스트는 크기를 동적으로 변경할 수있음 (메모리 절약)
• 삽입, 삭제 시 복사, 데이터를 이동시키는 연산을 수행하는데 많은 시간 소모

연결 큐

단순 연결 리스트를 사용한 큐

• 큐의 원소 : 단순 연결 리스트의 노드
• 큐의 원소 순서 : 노드의 연결 순서, 링크로 연결되어 있음

특징

• 메모리 낭비가 큰 큐의 문제를 극복하기 위해 연결 자료구조 방식을 이용하여 크기에 제한이 없음
• 초기 상태와 공백 상태에는 front = rear = null