방송대 자료구조 교재 요약 제4 장 - 큐

제4 장 큐)

 

개관)

큐는 줄을 서는 순서에 따라서 공평하게 서비스하는 경우에 많이 사용된다.

자원의 할당을 받으려는 작업들 간의 순서를 관리하는 경우도 마찬가지다.

큐의 입력 연산 시에는 수행 전에 정의된 큐의 크기와 저장된 데이터를 항상 확인해야 한다.

크기보다 더 많은 자료를 입력하면 에러가 발생하기 때문이다.

삭제 연산을 하기 전에 큐가 비어 있진 않은 지 확인해야 하는 것도 같은 맥락이다.

+ 뒤에 큐를 이용한 CPU 할당 방법과 원형 큐에 대한 이야기가 나온다.

 

정처기에 나올 것 같은 문제..!

FCFS 스케줄링(FIFO 스케줄링): 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해 주는 기법

RR(Round Robin) 스케줄링 기법: 작업(프로그램)이 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받으며, 일정한 크기의 시간 할당량을 모든 작업에 주고 그 시간 동안 작업이 완료되지 못 하면 준비 큐의 맨 뒤에 다시 배치되는 기법

원형 큐:

https://www.geeksforgeeks.org/introduction-to-circular-queue/

 

글 보다 이미지가 더 이해하기 좋다!

 

1. 큐의 개념

...

2. 큐의 추상 자료형

원소의 삭제가 이루어지는 곳이 앞(front)이고 삽입이 이루어지는 곳이 뒤(rear)다.

ADT에서부터 큐의 크기에는 제한이 있다(그래서 isFull, isEmpty 같은 메서드가 생기는 것.).

큐에 여유가 있으면 add를 계속 할 수 있다. <- 스택에서 add, remove라고 한다면 큐에서는 보통 offer, poll이라는 단어를 쓴다. 그런데 교재에서 굳이 그 단어를 안 써서 나도 그냥 편한 걸로 쓴다.

여유가 없으면 add가 안 된다.

큐에 원소가 있으면 remove를 할 수 있다.

큐에 원소가 없으면 remove가 안 된다.

큐에 원소가 있을 때 remove를 하면 원소가 해당 큐에서 삭제되면서 배열의 길이도 하나 준다.

지금 이야기하는 것은 ADT다. 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수 있으며, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있다.

따라서 지금은 '큰 그림'을 이해하는 걸로 충분하다.

 

지금 요소가 추가, 삭제될 때 배열 사이즈가 어떻게 변하는지, front와 rear 포인트는 어떻게 변하는지 궁금할 텐데

교재 74페이지에 아주 잘 나와 있다.

https://www.studytonight.com/data-structures/queue-data-structure

 

교재랑 포인터 위치에서 아주 약간 차이가 있는데 지금 크게 중요하지 않으니 넘어가자.

...

3. 큐의 응용

...

4. 배열을 이용한 큐의 구현

이 책에서는(다른 책에서는 어떤지 모르겠어서) 큐의 front랑 rear 포인터가 모두 -1에서 시작한다.

그러다가 요소가 추가되면 +1 되어 4까지 인덱스가 올라가는 스타일.

...

5. 원형 큐

mod(modulus) 연산자를 잘 써서 rear 값을 관리하면 된다.

mod 연산자를 사용해서 연속된 공간을 관리하는 건 개발 중에 굉장히 자주 유용하게 쓰이니 꼭 기억해 두는 게 좋다.

...

끝!