15강 환형 큐(Circular Queue)

1일차 ~ 14강 까지는 tistory에 있습니다. velog가 쓰기 더 편해서 옮기려고 합니다.
이번주 주말 내로 옮길 예정입니다!

학습 주제
환형 큐
환형 큐 운용
환형 큐 구현

학습내용

동기적(Synchronous)
어떤 작업을 요청했을 때 그 작업이 종료될때 까지 기다린 후 다음 작업을 수행하는 방식

비동기적(Asynchronous)
어떤 작업을 요청했을 때 그 작업이 종료될때 까지 기다리지 않고 다른 작업을 하고 있다가, 요청했던 작업이 종료되면 그에 대한 추가 작업을 수행하는 방식

또는

처럼
자료의 입력과 자료의 출력이 각기 다른곳에서 이뤄질 수 있다

운영체제 등에서 많이 이용되고 있음.

큐를 활용하는 예제는 고난이도 이번에는 다루지 않음

큐에 담을 수 있는 갯수를 한정함.

Q.enqueue(~)로 순서대로 들어가는 모습을 볼 수 있다. 넣을 때는 먼저 넣었던 값의 다음 공간에 들어간다

Q.dequeue() 할 경우 제일 먼저 넣었던 값이 리턴되는 모습 (참고. 디큐는 무조건 맨 처음 넣었던 값만 리턴)

Q.enqueue(D)의 경우 C의 다음번으로 들어가는 모습을 볼 수 있다.
Q.dequeue()의 경우 마찬가지로 A 다음 순번인 B가 리턴된다.
여기서 유추컨데 값을 넣을 때 자연스레 마지막의 다음번 자리에 들어가고 이는 돌다보면 A가 들어갔던 자리도 나오게 된다.

데이터를 입력받는 위치: rear
데이터를 출력하는 위치: front

이렇게 큐가 다 차는 경우도 생각해 볼 수 있다. 더 이상 데이터를 받으면 안되는 상황이다.
rear와 front의 위치가 같을 때를 데이터가 다 찼을 경우라고 생각하고 할 수도 있지만,
여기선 자체적으로 큐의 길이를 기억하고 있어, 다 찼을 경우 받지 않는 것으로 한다.
(더 편안함)

지난 큐와 동일하나, isFull()이 추가되었다. 큐가 다 차있는지를 확인하기 위한 메서드이다.

Q.dequeue()로 A가 빠져나가 회색이 되면, 비록 배열에는 A가 들어있지만 추상적 자료구조인 환형 큐에선 없어진 값으로 취급한다.

한번 더 dequeue()를 하면 front를 한칸 뒤로 전진시키고 B를 리턴한다. B도 무효한 데이터로 취급

Q.enqueue(E)의 모습 [4]의 인덱스에 E가 들어가 있는 모습. 마찬가지의 rear의 위치도 E를 가리키고 있다.

rear가 다시 0의 위치로 가 G가 A를 덮음

dequeue()시 front 가 앞으로 한칸 전진, C의 값이 r3로 반환, 배열 내 C는 무효화된 값.
6개의 배열에선 인덱스가 5인 상태에선 6이 되는 것이 아닌 다시 0으로 이동함. (재사용)

배열 구현

빈 큐가 초기화될시. 몇개 까지 길이인지를 생성이 받아야함. 인자로 n이 주어짐.
self.data 는 실제 저장될 곳. [None] *n으로 초기화한 리스트 준비

front와 rear를 -1로 선정함. 이후에 코드짜기 편함. -> enqueue시 1칸 전진하지 않을까? 추측

return 시 어떻게 인덱스를 확보해서 데이터를 리턴할 것인지?

연습문제

빈칸 채우기식.

어려웠던 점.
front, rear, peek 모두 (self.(front) + 1) // self.maxCount 라는 점.
peek은 아닐줄 알고 안했더니 계속 마지막 테스트가 에러가 났다.
생각해보니 peek 도 front 위치를 참조하는 점에서 배열 마지막 위치의 다음을 다시 0 위치로 돌려놔야했었다.