한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관
한쪽에서는 삽입연산: 서비스를 받기 위한 기다림
다른 한쪽에서는 삭제연산: 서비스를 받는 중
선입 선출(FIFO:First-In-First-Out) 또는 선착순 서브(FCFS:First-Come-First-Serve) 알고리즘과 함께 사용됨
(2) 큐의 정의
✅ 2. 큐의 추상 자료형
(1) 큐의 객체 정의
큐의 추상자료형
큐 객체: 0개 이상의 원소를 갖는 유한 순서 리스트
(2) 큐의 연산
큐의 앞(front): 원소의 삭제 연산이 이루어지는 곳
큐의 뒤(rear): 원소의 삽입 연산이 이루어지는 곳
item 은 큐의 들어갈 값을 의미한다.
(3) 큐의 삽입(Add_q) 연산
큐의 삽입 조건으로 full 여부를 파악한 뒤 full 이 아니면 rear 에 item 원소를 삽입
(4) 큐의 삭제(Delete_q) 연산
큐가 비어있는지 여부를 체크 한 뒤, 큐의 front 에 있는 원소를 삭제하고 반환을 한다.
(5) 빈 큐 검사(IsEmpty_q) 연산
(6) 큐의 만원 검사(IsFull_q) 연산
(7) Add/Delete 연산의 실행
(1) Create_q(4): 4개의 Q 공간을 만든다.
(2) Add_q(queue, 'A'): 큐에 A 값을 삽입 해당 부분은 rear 포인터 부분이 됨. ( front 는 항상 동일 -1 위치 )
(3) Add_q(queue, 'B'): 큐에 B 값 삽입 rear 포인터 이동
(4) Add_q(queue, 'C'): 큐에 C 값 삽입 rear 포인터 이동
(5) Delete_q(queue): front 가 이동하면서, 제일 먼저 들어온 A를 삭제 및 반환
(6) Delete_q(queue): front 이동 다음 B 삭제 및 반환
(7) Delete_q(queue): front 이동 다음 C 삭제 및 반환
(8) Add_q(queue, 'D'): 큐에 C 값 삽입 rear 포인터 이동
8번 이후 만약 'E' 를 삽입하게 되면 rear 가 배열의 끝에 도달했기 때문에 더 이상 뒤로 이동할 수 없게됨.
따라서 큐 만원 상태로 인식되어 e를 삽입할 수 없게 된다.
(8) 배열 기반 큐의 문제점
위의 예시와 같이 일반적인 배열 기반 큐의 문제점은 front 와 rear 포인터가 앞으로 다시 돌아가는것이 불가능하여 공간을 재활용하지 못하는 심각한 비효율이 발생하며, 이것을 큐의 오버플로(Overflow) 라고 부르기도 한다.
이것을 해결하기 위해 원형 큐 라는 자료구조가 사용되기도 함.
따라서, 원형 큐와 배열 큐는 큐의 추상 자료형의 공통된 연산인 큐의 삽입, 삭제, 빈 큐 검사, 만원 큐 검사 연산은 공통적으로 구현하는 내용이며 배열 큐와 원형 큐는 해당 공통된 연산을 서로 다른 방식으로 구현하게 된다.
✅ 3. 큐의 응용
(1) CPU의 관리 방법
FCFS 비선점 스케줄링 기법
FCFS(First-Come First-Served)스케줄링 기법은 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받고 작업이 완료될 때까지 CPU를 사용하는 기법이다. ( 해당 방법은 긴 시간의 작업이 오래 CPU를 점유하는 불공평함이 있음. )
Round Robin 스케줄링 기법
RR(Round Robin) 스케줄링 기법은 대화형 시스템에 적합하며, 일정 시간(time slice)만 CPU를 사용하는 스케줄링 방식
쉽게말해, 큐에 도착한 순서대로 CPU 할당을 해주고 정해진 시간 만큼만 프로세스에게 CPU를 할당해준다. 이후, 정해진 시간을 벗어나는 작업은 남은 시간을 가진채 큐의 맨 뒤로 다시 들어가게 되는 방식이다.
(2) 결론
운영체제가 CPU 할당 즉, 스케줄링을 관리할 때 대부분의 기법은 Queue 자료구조를 활용하고 있다.
✅ 4. 배열을 이용한 큐의 구현
큐의 추상자료형을 가지고 구현하는 방식으로, 배열을 이용한 방식으로 보면 된다.
삽입과 삭제에 대한 추상자료형을 구현했다고 보면됨.
(1) 큐의 생성
변수 rear의 초기값은 큐의 공백 상태를 나타내는 '-1'로 시작을 한다.
(2) 큐의 초기 상태
(3) 큐의 삽입 연산
// C
void Add_q(element item) {
if(rear == QUEUE_SIZE-1) {
printf("Queue is full !!");
return;
}
queue[++rear] = item;
return;
}
삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동하고, 삭제 연산이 발생하면 front 변수만 오른쪽으로 이동을 함.
QUEUE_SIZE 는 큐의 할당 된 공간의 값을 의미하며, -1을 하는 이유는 배열의 인덱스는 0부터 시작하기 때문임.
rear 의 위치가 만약 배열의 마지막 부분 즉, 사이즈를 넘어섰기 때문에 꽉찼다고 알려주는 로직임.
(4) 큐의 삭제 연산
// C
element Delete_q() {
if(front == rear) {
printf("Queue is empty");
return;
}
return(queue[++(front)]);
}
삭제 연산의 수행 결과로 삭제된 원소를 Delete_q 연산자의 호출 프로그램에게 반환
✅ 5. 원형 큐
큐의 추상자료형이 정의한 규칙을 충실히 따르면서, 배열이라는 구체적인 자료구조를 사용해 효율적으로 구현하는 방법
기존의 배열 기반 큐(선형 큐)가 가진 메모리 낭비 문제를 해결하기 위해 고안된 것이다.
** 선형 큐는 배열의 맨 앞에서 원소를 삭제하고, 맨 뒤에서 원소를 삽입하는데 이때 원소를 삭제하고 나면 배열의 앞부분에 빈 공간이 생기는데 이 공간은 재사용되지 않고 그대로 버려지게 된다. **
즉, 새로운 원소는 항상 배열의 뒤쪽에만 추가가 되게 되는 문제점 발생이 되는데, 이것이 메모리 낭비와 직결이 된다.
(1) 큐의 빈 상태와 삽입 상태
일반적인 큐에서는 rear 와 front 의 위치가 겹치게 될 때 큐가 비어있다고 판단이 된다.
(2) 큐의 만원 상태
일반적인 큐에서는 QueueSize - 1 == rear 조건을 통해서 Queue 가 만원상태인지 알 수 있음.
하지만 아래와 같은 case 에서는 Queue 0 인덱스의 값이 사라져 있는 상태이지만 동일하게 만원상태로 보게 됨.
즉, front 를 통해 비어진 공간은 사용을 할 수 있음에도 사용을 할 수 없는 상태가 되버림 ( 메모리 낭비 )
(3) 원형 큐의 초기 상태
배열로 구현한 큐의 문제점을 해결하기 위해 원형 큐가 제안이 되었음.
원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태를 의미한다.
(4) 원형 큐의 상태 변환
Queue delete -> front 의 위치 0번 인덱스로 이동
rear 의 현재 위치는 4번 인덱스
Queue delete -> front 의 위치 1번 인덱스로 이동
rear 의 현재 위치는 4번 인덱스
오른쪽의 배열 기반일 경우 rear 이동 즉, 삽입이 더 이상 불가능함.
(5) 원형 큐의 삽입 연산 결과
연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 '나머지 연산자' 을 활용함.
쉽게말해, 해당 큐의 rear 의 위치가 인덱스의 마지막 위치인 경우에 즉, QueueSize - 1 == rear 조건이 true 인 경우에 rear 에 1을 더해주게 되고 결과값에 원형 큐의 크기를 모듈로 연산을 수행해주면 rear 의 위치가 0번 인덱스로 가게 됨.
예를 들면, 위에 마지막 인덱스 4번에 해당 될 때 QueueSize는 5 이므로, -1을 하고 rear 와 비교했을 때 둘 다 4이므로, 마지막 인덱스라는 것을 알게되고, 이후 rear 에 1을 더해주면 5를 얻게 되고 QueueSize(5) 와 모듈로 연산을 하면 0이라는 숫자를 얻게 되는데 이것이 제일 첫 번째 인덱스를 가리키는 구조가 되는 것임.
즉, 이러한 방식을 이용하면 동일하게 rear 와 front가 만나는 지점이 결국엔 큐가 꽉차 있는 경우 또는 비어있는 상태임을 알 수 있게 된다. 이 둘의 구별은 카운트 변수를 통해 삽입 시 count 1 증가 또는 삭제 시 count 1 감소를 통해 구별이 가능하다. 이 뿐만 아니라 포인터를 활용해서도 가능
(6) 정리
큐 추상자료형을 통해 배열로 구현을 해봤더니, 배열로 구현한 방식은 큐 delete로 사라진 공간 즉, 앞의 공간이 남아 있다는 것을 알아도 더 이상 삽입이 불가능했지만, 원형 큐의 연산을 통해 해결이 가능했음. 이것의 구현은 모듈로 연산을 통해 나머지의 값을 인덱스로써 활용함으로써 가능해짐.
