[자료구조] 4강 - 큐

✅ 1. 큐의 개념

(1) 큐의 의미

• 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄을 의미한다.
• 쉽게말해, 들어간 순서대로 하나씩 순서대로 처리하는 방식을 의미함.
• 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관
• 한쪽에서는 삽입연산: 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제연산: 서비스를 받는 중
• 선입 선출(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) 원형 큐의 삽입 연산 결과

• 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 '나머지 연산자' 을 활용함.
• 모듈로 연산을 활용해 현재 이미지의 큐 크기인 5값과 인덱스 4 + 1 한 결과값 5
• 현재 이미지의 큐 크기인 5값과 현재 rear 위치의 인덱스가 마지막 인덱스 4인 경우에는 4 + 1을 하여, 5와 5를 모듈로 연산을 통해 나온 값인 0을 다시 인덱스로 쓰게 되면서 해당 인덱스에 값을 넣을 수 있게 된다.
• 즉, 이러한 방식을 이용하면 동일하게 rear 와 front가 만나는 지점이 결국엔 큐가 꽉차 있는 경우 또는 비어있는 상태임을 알 수 있게 된다. 이 둘의 구별은 카운트 변수를 통해 삽입 시 count 1 증가 또는 삭제 시 count 1 감소를 통해 구별이 가능하다. 이 뿐만 아니라 포인터를 활용해서도 가능

(6) 정리

• 큐 추상자료형을 통해 배열로 구현을 해봤더니, 배열로 구현한 방식은 큐 delete로 사라진 공간 즉, 앞의 공간이 남아 있다는 것을 알아도 더 이상 삽입이 불가능했지만, 원형 큐의 연산을 통해 해결이 가능했음. 이것의 구현은 모듈로 연산을 통해 나머지의 값을 인덱스로써 활용함으로써 가능해짐.