선형 큐

1차원 리스트를 이용한 큐

큐의 크기 = 리스트 크기

front 저장된 첫 번째 원소의 인덱스

rear 저장된 마지막 원소의 인덱스

 

초기 상태 : front = rear = -1

공백 상태 : front = rear

포화 상태 : rear = n-1 (n : 리스트 크기, n-1 : 리스트의 마지막 인덱스)

 

✨ 선형 큐의 구현

1. 초기 createQueue()

초기 공백큐 생성

크기가 n인 1차원 리스트 생성

front = rear = -1

2. 삽입 : enQueue(item)

마지막 원소 뒤에 새로운 원소를 삽입하기 위해 rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련

그 인덱스에 해당하는 리스트원소 Q[rear]에 item을 저장

3. 삭제 deQueue()

가장 앞에 있는 원소를 삭제하기 위해

front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소로 이동

새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능을 함

4. 공백상태 및 포화상태 검사 : isEmpty(), isFull()

공백상태 : front = rear

포화상태 : rear = n-1 (n : 리스트 크기, n-1 : 리스트의 마지막 인덱스)

5. 검색 : Qpeek()

가장 앞에 있는 원소를 검색하여 반환하는 연산

현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소 반환

 

선형 큐의 장점 : 삽입, 삭제 처리속도 빠름

선형 큐의 문제점 : 잘못된 포화 상태 인식!

리스트 크기를 고정 -> 사용할 큐의 크기만큼을 미리 확보 -> 메모리 낭비 발생

삽입, 삭제를 계속할 경우 리스트의 앞부분에 활용할 수 있는 공간이 있음에도 rear=n-1인 상태 즉, 포화 상태로 인식

더 이상의 삽입을 수행할 수 없음

 

선형 큐의 단점 해결 방법

원형 큐 사용으로 메모리 절약

파이썬의 리스트 특성을 사용한 큐 사용으로 메모리 절약(삽입, 삭제 시 복사, 데이터 이동시키는 연산 수행에 많은 시간 소모)

단순연결 리스트로 구현한 큐 사용으로 메모리 동적 확보

큐 라이브 사용

 

 

 

by SW expert academy