원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 자료구조 중에서 중요한 원형큐(Circular-Queue)에 대해서 같이 알아보겠습니다.

 

아직 큐에 대해서 이해가 되지 않는다면 이전 포스팅을 참고해주세요 :)

 

정말 어렵지 않으니 잘 따라와주세요~!

 

 

그림으로 쉽게 이해하는 자료구조 큐(Queue) (ft. 큐를 배열기반에서 절대 선형으로 구현하지 않는 이유)

그림으로 쉽게 이해하는 자료구조 큐(Queue) (ft. 큐를 배열기반에서 절대 선형으로 구현하지 않는

 

 

 

큐(Queue)를 구현하는 방법에는 크게 2가지 방법이 있습니다.

첫 번째는 LinkedList를 이용하는 방법이 있겠고,

 

두 번째는 배열을 이용한 원형 큐를 이용하는 방법이 있겠습니다.

지난 포스팅에서 배열을 이용해서 선형 큐를 구현하면 너무 비효율적인 부분이 있다고 말씀드렸었죠.

 

그래서 원형큐는 배열로 구현을 하되 단점을 보완한 구조라고 보시면 되겠습니다.

 

 

원형큐 그림 예시

 

원형큐는 그림으로 표현하면 이렇게 동그란 모양으로 표현할 수 있겠습니다.

이름 그대로 마치 원형 형태의 구조에서 데이터가 순환되는 것을 말합니다.

원형큐(Circular Queue)도 큐(Queue)이기 때문에 

 

먼저 온 데이터가 먼저 빠지게 되는 선입선출의 순서대로 처리되는 형태임에는 변함이 없습니다.

 

그렇기 때문에 front와 rear의 위치를 기준으로 데이터를 넣고 빼는 연산을 똑같이 해줄겁니다.

지금 그림의 상태는 아직 데이터를 하나도 넣지 않은 초기의 상태입니다.

이때는 front와 rear모두 0번째 인덱스를 가리키고 있겠죠.

 

 

 

 

 

원형큐 그림 예시

 

 

 

이렇게 비어있는 상태에서 데이터가 처음 들어오게 되면 

 

데이터는 rear를 기준으로 삽입이 될 겁니다.

그래서 첫번째 데이터가 들어오게 되면

 

rear가 가리키는 위치에서 +1을 하면서 그 위치에 데이터를 삽입하게 됩니다.

 

 

 

원형큐 그림 예시

 

 

 

그래서 삽입되면서 rear의 위치도 가장 최근의 데이터가 삽입된 위치를 가리키게 됩니다.

그래서 이렇게 그림처럼 첫번째 인덱스에 데이터가 삽입이 되게 됩니다.

 

그 상태에서 또 데이터가 들어온다면

 

마찬가지로 현재 데이터가 들어있던 가장 뒤를 가리키는 rear값에

 

+1이된 인덱스 값에 데이터가 삽입되면서

 

rear의 값도 한 칸 이동하게 됩니다.

 

 

 

 

원형큐 그림 예시

 

 

 

 

이렇게 데이터가 또 들어오게 되면 계속해서 Queue에 가장 뒤쪽인 rear를 기준으로 데이터를 쌓게 됩니다.

데이터가 쌓이면서 rear포인터도 함께 이동하는 모습을 보실 수 있죠.

 

 

 

원형큐 그림 예시

 

 

원형큐 그림 예시

 

이제 이 원형큐에서 데이터를 가져오는 동작을 한 번 보겠습니다.

데이터를 가져올 때는 front에 인덱스를 통해서 데이터에 접근을 하게 됩니다.

현재 front는 아무런 데이터도 가리키지 않고 있는 상황이죠.

여기서 삽입할 때와 마찬가지로 데이터를 가져올 때도

 

front의 위치에서 한칸 +1을 해서 그 위치에 있는 데이터의 값을 가져오게 됩니다.

그러면 0번재 인덱스에서 1번째 인덱스로 이동하게 되면서

 

처음 삽입된 데이터인 10이 있는 위치를 가리키게 되겠죠.

 

 

 

원형큐 그림 예시

 

 

그 후에 또 deq연산으로 데이터를 가져오게 되면

 

front의 인덱스에 +1을 한 위치로 front의 인덱스를 이동시키면서

 

해당위치에 있는 데이터 값을 가져오게 됩니다.

 

 

 

 

원형큐 그림 예시

 

 

 

deq연산을 한 번 더 하면

 

front 인덱스도 한 칸 옮겨지고 세번 째에 있는 데이터 값 30을 가져오게 됩니다.

 

 

 

원형큐 그림 예시

 

 

여기서 한 번더 deq연산을 하면 40의 값을 가져오게 될거고 front와 rear의 위치가 같아집니다.

그러면 실제로 마지막 데이터 값이 빠지면서 큐는 비어있는 상태가 되겠죠.

 

 

 

원형큐 그림 예시

 

이때 Front와 rear의 인덱스가 같다는 것에 주목을 해주셔야 합니다.

즉, 원형큐는 비어있는 상태에서 front와 rear의 상태가 같습니다.

제일 처음 초기화 상태에서는 둘다 인덱스가 0번째로 동일했었죠.

꼭 인덱스가 0번째가 아니더라도 이렇게 

 

인덱스가 같은지 아닌지의 여부로 큐가 비어있는지 아닌지를 판단할 수 있습니다.

 

그럼 이 상태에서 데이터가 새로 삽입이 되면 어떤 모양이 되는지 보도록 하겠습니다.

 

 

 

 

원형큐 그림 예시

 

인덱스의 위치가 0부터가 아닌 계속해서 rear를 기준으로 쌓게 됩니다.

이제 가장 앞에 있는 데이터의 인덱스는 5번째가 됩니다.

그 다음에 계속해서 데이터가 들어오더라도 이전과 동일하게 rear를 기준으로 데이터가 삽입이 될거고

마지막 인덱스인 7번째 인덱스까지 데이터가 삽입이 될 수 있습니다.

그러면 실제로 rear는 배열의 끝 위치에 도달한거죠.

 

 

 

원형큐 그림 예시

 

 

그러면 그 이후에는 어떻게 될까요?

-> 바로 비어 있던 0번째 인덱스에 데이터가 들어가게 됩니다.

 

 

 

원형큐 그림 예시

 

 

 

이렇게 해서 0번부터 7번까지의 인덱스를 가진 직선 배열에서

 

마치 원형적으로 동작하는 큐를 구현을 하는 것을 Circular Queue 즉 원형큐라고 합니다.

 

그렇다면 원형큐에서 데이터가 꽉찼을 때는 어떤 모양이 될까요?

 

 

 

원형큐 그림 예시

 

 

원형큐에서 데이터가 꽉차면 이런 모양이 됩니다.

원형큐에서는 모든 배열 칸에 데이터를 채우지 않고 위 그림 처럼 한칸의 더미 공간을 주어서

꽉 찬 상태와 비어있는 상태를 구분할 수 있습니다.

 

만약 4번째 인덱스에도 값을 채워 넣는다면

 

이렇게 하면 front와 rear의 위치가 동일해지면서 empty상태와 구분하기 어려워지게 됩니다.

그렇기 때문에 한칸 비워 둔 상태에서 rear의 위치에 +1을 한 값이 front와 동일하다면 

 

이 원형큐는 꽉 찬 상태로 볼 수 있습니다.

 

 

- 정리 및 요약

다시 정리하자면 

 

원형큐는 고정된 크기의 배열을 선언해서 구현을 할 것입니다.

위 예시에서 총 8칸 밖에 안되는 배열 구조에서 데이터가 꽉 차지 않는다면 

 

무한하게 계속해서 데이터를 넣고 빼는 작업을 할 수 있겠죠.

 

그러면 메모리도 훨씬 덜 쓰고

 

배열에 인덱스로 접근하기 때문에 데이터 엑세스 속도도 빠르다는 장점이 있습니다.

또 데이터를 넣고 빼는 것에 따라 데이터의 인덱스를 한칸씩 옮겨야 하는 추가 연산도 할 필요가 없습니다.

그렇지만 배열이기 때문에 크기가 정해져 있다는 단점도 분명히 존재하겠죠.

 

 

- 여기서부터는 고수 영역

이제 여기서부터는 고수 영역입니다..
이해 안되셔도 괜찮습니다.

한 번 읽고 그냥 넘어가셔도 괜찮아요.

입문자는 그냥 넘어가셔도 되고, 소화 가능하신 분만 소화하시면 됩니다ㅎㅎ

우리가 사용하는 데이터 구조인 array는 아시겠지만 직선의 데이터 구조를 가지고 있습니다.

하지만 직선의 데이터 구조를 그림으로 본 것처럼

 

마치 데이터가 순환되는 형태로 관리될 수 있게 구현되어야 하기 때문에

원형큐에서 인덱스로 접근을 할 때 인덱스 값에 큐 사이즈를 모듈로 연산을 한 값으로 접근을 할겁니다.

그러면 인덱스의 값은 항상 큐 내에 인덱스 위치를 순환하는 값이 되겠죠.

 

예를 들어 원형큐의 사이즈를 5라고 가정을 했을 때

 

인덱스의 위치가 1이라면 1의 모듈로 5연산을 하면 그 값은 1이 나옵니다.

 

마찬가지로 2일 때 2에다가 모듈로 5연산을 하면 인덱스의 값은 2가 되겠죠.

 

+1, +1을 하면서 이제 인덱스의 위치를 넘어서 6, 7 이런 값이 나올 때

 

여기에 모듈로 연산을 하면 인덱스의 위치는 여전히 1,2 이런식으로 큐 인덱스 범위 내의 값이 나오게 되는거죠.

 

그래서 원형큐에서 포인트는 이 모듈료 연산을 써서 인덱스에 접근한다. 이것이 첫번째 포인트가 될거구요

 

그리고 큐의 데이터를 삽입하는 enq연산과 데이터를 가져오는 deq연산 외에도

 

큐의 상태를 알수 있는 isFull과 isEmpty조건도 함께 기억해주시면 좋을 것 같습니다.

 

다음 포스팅에서는 자료구조 해시에 대해 다루겠습니다.

 

로스윗의 코딩 캠프는

 

미래의 개발자 여러분을 응원합니다!!

 

모두 화이팅입니다!!

 

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)