큐
- 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
큐는 뒤에서 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 - 선입선출구조(First In First Out)
큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다
큐의 선입선출 구조
큐의 기본 연산
- 삽입: enQueue
- 삭제: deQueue
이 외에도 - createQueue() 공백 상태 큐를 생성하는 연산
- isEmpty() 큐가 공백상태인지 확인하는 연산
- isFull() 큐가 포화상태인지 확인하는 연산
- Qpeek() 큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산
큐의 연산 과정
1) 공백 큐 생성: createQueue();
2) 원소 A 삽입: enQueue(A);
3) 원소 B 삽입: enQueue(B);
4) 원소 반환/삭제: deQueue();
5) 원소 C 삽입: enQueue(C);
6) 원소 반환/삭제: deQueue();
7) 원소 반환/삭제: deQueue();
큐의 구현
-
선형큐
1차원 배열을 이용한 큐
큐의 크기 = 배열의 크기
front: 저장된 첫 번째 원소의 인덱스 / 마지막으로 삭제된 deQueue된 원소의 인덱스
rear: 마지막으로 저장된 원소의 인덱스 -
상태표현
초기 상태: front = rear = -1
공백 상태: front == rear
포화 상태: rear == n-1 (n: 배열의 크기, n-1 배열의 마지막 인덱스) -
초기 공백 큐 생성
크기 n인 1차원 배열 생성
front와 rear를 -1로 초기화
삽입
마지막 원소 뒤에 새로운 원소를 삽입하기 위해
rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리 마련
그 인덱승 해당하는 배열원소 Q[rear]에 item을 저장
삭제
가장 앞에 있는 원소 삭제하기 위해
front 값을 증가시켜 큐에 남아있게 될 첫번째 원소 이동
새로운 첫 번째 원소 리턴 함으로써 삭제와 동일한 기능함
*front가 말하는 자리는 이미 꺼내진 자리
공백상태 및 포화상태 검사: isEmpty(), isFull()
공백상태: front == rear
포화상태: rear == n - 1 (n-1 은 배열의 마지막 인덱스)
검색: Qpeek()
가장 앞의 원소를 검색해 반환하는 연산
현재 front 한자리 뒤(front + 1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소 반환
읽어만 오는 것
선형 큐 이용시의 문제점
- 잘못된 포화상태 인식
원소 삽입 삭제 반보갈 경우 앞 부분에 활용할 공간 있음에도 불구하고 rear=n-1 인 상태, 즉 포화상태로 인식해 더 이상 삽입 수행 안함
- 해결방법1
연산 이루어질 때마다 저장된 원소들을 배열 앞부분으로 모두 이동시킴
원소 이동에 많은 시간 소요ㅚ어 큐의 효율성 급격히 떨어짐
이것도 사실 비효율적
- 해결방법2
1차원 배열 사용하되, 논리적으로는 배열 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용
원형 큐의 논리적 구조
원형 큐 구조
- 초기 공백 상태
front = rear = 0 - 초기 공백 큐
크기 n인 1차원 배열 생성
front와 rear를 0으로 초기화 - Index의 순환
front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함
이를 위해 나머지 연산자 mod를 사용함 - front 변수
공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리 - 삽입 위치 및 삭제 위치
rear의 다음이 front와 같으면
원형 큐 공백 및 포화 상태 검사 isEmpty(), isFull()
- 공백상태 : front == rear
- 포화상태 : 삽입할 rear의 다음 위치 == 현재 front
-(rear) + 1 mod n == front
삽입: enQueue(item)
삭제: deQueue(), delete()
- 알고리즘 문제 풀이 할 때는 원형 대신 선형 큐 만들어도 된다
