꿈 꾸는 누렁이

지난 포스팅에서 순회까지 끝냈다. 이제 탐색과 삭제가 남았다.

바로 이어서 탐색을 보자.

이진 탐색 트리의 탐색

이진 탐색 트리에서 탐색과 순회는 다르다. 순회는 모든 노드를 방문하는 것을 이야기하지만, 탐색은 가장 효율적이고 적은 깊이로 노드를 방문하여 원하는 값을 찾는 것인가이다.

1번 : 찾으려고 하는 5 값이 루트 노드의 10 값보다 작으니, 왼쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
2번 : 찾으려고 하는 5 값이 노드의 4 값보다 크니, 오른쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
그 이후 발견.

위와 같이 서브 트리를 대상으로 옮기고, 또 서브 트리의 서브 트리로 대상을 옮기고 하는 과정에서 봤을 때, 재귀로 해결할 수 있다! 탐색 또한 마찬가지로 순회처럼 재귀를 이용하여 문제를 해결해갈 것이다.

코드를 보면 다음과 같다.

매개 변수인 sub_root에는 서브 트리의 루트 노드가 항상 들어온다. 이 서브 트리의 루트 노드와 값을 비교하여 같으면 탐색 완료, 작으면 다시 왼쪽 서브 트리 재탐색을 위한 재귀 호출, 크면 다시 오른쪽 서브 트리 재탐색을 위한 재귀 호출 순서로 조건 및 연산 수행을 진행하면 된다.

이진 탐색 트리의 삭제

아.. 삭제는 ㅋㅋ 여러 유형으로 나뉜다 쉽지가 않다. 왜냐하면? 자식이 없는 단말 노드를 삭제할 경우, 그냥 해당 단말 노드만 제거하면 끝나는 문제이지만 자식 노드가 존재하는 노드를 삭제할 경우 문제가 커진다. 

일단은 그림 형태로 유형 별로 확인한 뒤 코드를 보자.

삭제할 타겟이 단말(리프) 노드인 경우

간단하다. 그냥 끝에 있는 노드이므로 바로 삭제를 하면 되는데, 다만! 삭제할 타겟의 부모의 링크(left or right)가 NULL을 가리키도록 설정해주면 된다. 다음의 그림과 같이 말이다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 하나만 존재하는 경우

이 경우 또한 간단하다. 아래의 그림과 같은 경우인데 삭제할 타겟의 부모의 링크와 삭제할 타겟이 가지고 있는 하나의 자식 노드를 연결해주면 된다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 두 개 모두 존재하는 경우

이 경우는 좀 답이 없다. 물론 설명하기 답이 없다는 것이다. ㅋㅋ 좀만 생각해보면 쉽다! 

먼저, 이전의 노드 삭제 유형들처럼 타겟을 삭제하고 부모와 자식을 연결해주는 등의 간단한 방법으로 끝날 문제가 아니다.

삭제할 타겟 노드가 자식 노드를 두 마리나(?) 가지고 있는 바람에 왼쪽 자식 노드의 서브 트리와 오른쪽 자식 노드의 서브 트리를 만족할 수 있는 값으로 대체 노드 선별해야한다. 

아 그러면? 삭제할 타겟 노드의 자식들 중 하나로 선택하면 되는 것 아니냐?

응 안된다. 왜냐하면 그림에 자세히 설명을 해 놓았다. 아래의 그림에서 두 번째 케이스에 해당하는 경우다. 혼돈하지 말아야 한다.

그러면 자식 중에 아무나 하나를 그냥 올리면 안되면 어떻게 올려야 하나?

왼쪽 서브 트리에서 가장 큰 값을 갖는 노드를 대체 노드로 선별하거나,
오른쪽 서브 트리에서 가장 작은 값을 갖는 노드를 대체 노드로 선별해야한다.

두 경우 중 하나를 선택해야 한다. 그 선택은 뭐 개발자 마음이고, 코드 작성자 마음이다. 선택했다면 다음과 같은 순서를 떠올릴 수 있다.

1. 대체 노드의 링크들을 타겟 노드의 링크로 전부 동기화 한다.
2. 대체 노드의 부모의 링크를 적절한 포인터(노드 혹은 NULL)로 변경한다.
3. 타겟 노드를 제거한다.

이러한 순서를 떠올렸는데 여기서 약간의 꼼수(?)를 쓴다고 하며, 지혜를 발휘한다고 읽는다. 뭐냐하면, 대체 노드를 굳이 드러내어 타겟이 있던 자리로 옮겨서 링크를 수정할게 아니라, 타겟 노드의 값만 대체 노드의 값으로 바꿔준다면 링크들을 굳이 변경할 필요가 없기 때문이다. 

1번 연산이 굉장히 부담 그 자체이다. 헤깔려죽겠는데.. 2번과 3번은 어차피 대체 노드에 대해서 해야할 작업이기 때문에 그렇다 치더라도, 1번 연산은 안 해도 될 일을 하는 것과 다름이 없다! ㅋㅋ

그래서 뭐 어찌 되었든 간에 왼쪽/오른쪽 중에 선택을 했다면, 다음 그림으로 그 선택 이후의 과정을 설명한다. 번호 순서대로 색깔과 연관 지어서 차근 차근 읽으면 된다.

이에 따른 코드는 아래와 같으며, 타겟 노드를 루트 노드로 한 서브 트리의 오른쪽 자식의 서브 트리 군에서 가장 작은 값을 선택하여 타겟 노드의 자리에 대체하기로 하였다.

하.. 이로써 삭제까지 끝이다.

일요일에 정말 집중도 안되고, 포스팅을 하면 할수록 코드 작성 때는 떠 올리지도 않았던 세세한 부분까지 의구심이 들어서 시간이 두배, 세배 드는 것 같다.

뭐 다음 시간에는 코드와 실행 결과만 올린다.

여기에 이어서 이진 탐색 트리에 대해서 분석하고 기록할 것이다.

준비 및 구성

먼저, 이전 포스팅에서의 개념과 조건들을 토대로 어떻게 준비할 것인가이다!

트리 구성의 준비물이 되는 노드이다! 노드의 구성은 다음과 같다.

크게 설명할 것이 없다. 이 노드 구조체를 통해서 값과 이진 탐색 트리 조건에 맞는 자식 노드를 가리킬 포인터 2개의 구성이 끝인 것이다. 

이런 구조체로 노드를 생성할 때에는 꼭 다음과 같은 상태로 초기화되는 것이 보장되어야 한다.

트리에 접근하는 방법(루트 노드에 접근하는 방법)

삽입 연산을 하기 이전에 트리에 접근할 때에는 무조건 루트 노드부터 접근을 시작해야한다. 그 루트 노드로의 접근을 어떤 식으로 할 수 있는지, 그 루트 노드를 어떻게 정하는지를 기록한다.

위 코드는 메인 함수 내에서 실행되는 코드로 root 라고 하는 포인터로 트리의 루트 노드를 가리키도록 설계해놓았다.

트리에 노드 삽입 연산

먼저, 삽입 연산은 그림으로 나타냈을 때, 아래와 같다.

위 삽입 연산에 해당되는 코드를 함께 보는게 좋을 것 같다.

먼저, 트리에 노드가 0개 일 때 의 노드 생성이다.

트리에 노드가 1개 이상일 경우에는 다음처럼 삽입 연산을 수행한다.

트리 순회 연산

트리에 노드를 추가만 해서는 뭘 하는가! 순회도하고 탐색도 할 수 있어야, 탐색 트리이지. 먼저, 순회 연산에 대해 알아본다.

하.. 일단(ㅋ) 순회 연산은.. 여러 종류가 있다. 이 여러 종류의 연산 과정을 내 블로그 내에서 최초 도입한 신개념 비디오 장치를 통해 촬영된 것을 올릴 것이다.

일단 트리에서의 순회는 조금 특이하다. 

첫 노드인 루트 노드를 기준으로 한 큰 트리가 존재하지만, 첫 노드의 자식을 기준으로 또 하나의 서브 트리가 존재한다. 이 서브 트리를 하나의 대상으로 연산이 이루어지고, 또 그 자식 노드를 기준으로 또 서브 트리가 존재하며 단말 노드가 될 때까지 서브 트리 군이 형성된다. -> 재귀적으로 문제를 풀 수 있다는 것이다.

그래서 이 순회에서는 재귀를 통해 순회를 진행할 것이다. 삭제 또한 마찬가지이나 다양한 방법들을 넣기 위해서 순회에만 재귀를 적용하도록하고, 삭제에서는 반복문을 통해 삭제를 진행한다.

전위 순회 : 루트 노드를 기준으로 먼저 루트 노드의 값을 읽고, 그 다음 순차적으로 왼쪽 트리를 방문하고, 그 뒤에 오른쪽 트리를 방문하는 방법이다.

서브 트리의 루트 방문(값 Get) -> 왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문

중위 순회 : 루트 노드를 기준으로 먼저 왼쪽 트리를 방문하고, 그 다음 해당 루트 노드의 값을 읽고, 그 다음 오른쪽 트리를 방문하는 방법이다.

왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 서브 트리의 루트 방문(값 Get) -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문

후위 순회 : 루트 노드를 기준으로 먼저 왼쪽 트리를 방문하고, 그 다음 오른쪽 트리를 방문한 뒤에 해당 루트 노드의 값을 읽는 순회이다.

왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문 -> 서브 트리의 루트 방문(값 Get)

레벨 순회 : 레벨 순회는 레벨 1부터 트리의 말단 리프 노드들이 있는 레벨까지 큐 자료 구조에 순서대로 넣고 출력하여 순회하는 간단한 순회 법이며, 레벨 순서 & 왼 -> 오 순으로 순회가 이루어진다.

각 순회의 실제 결과

다음 포스팅은 이진 탐색 트리에서 탐색과 삭제 연산을 포스팅할 것이다.

오늘은 이진 탐색 트리이다. 

이전까지는 선형 자료 구조를 공부했었다. 뭐 예를 들어, 일반 배열 리스트, 연결 리스트, 스택, 큐 등의 선형 구조만 포스팅했는데, 드디어! 비 선형 자료 구조이다. 

데이터가 선형으로 연속되지 않는만큼 삽입, 삭제, 탐색 연산에 신경쓸게 더 많다. 그래도 이렇게 선형을 끝내고 비선형을 진행하는게 뿌듯하긴 하지만 이게 들이는 시간에 비해 결과가 그렇게 크지 않아서 비선형 자료구조를 여러 가지의 예제로 다양하게 진행하지는 못할 것 같고, 핵심만 파악할 수 있는 그런 알찬 예제로 기록을 해 둘 것이다.

나중에 다시 봐도 아~ 이게 트리지 할 수 있도록.

일단은 나는 연결 리스트 기반의 이진 탐색 트리를 구현할 것이며, 데이터의 삽입, 삭제, 탐색(레벨 순회, 전위 순회, 중위 순회, 후위 순회)까지 구현할 것이다. 

배열 기반의 이진 트리는 Heap 자료 구조에서 구현이 될 것인데, 아래의 링크에서 Heap 구조를 알 수 있다. 기본은 Heap이지만 내용은 거의 우선 순위 큐이다. 다만, 큐 형태로 Wrapping만 하지 않았을 뿐...

특이사항이라면,

이전과 마찬가지로 메모리 관리는 기존에 공부했던 배열 기반 스택을 통해 이루어진다. 
레벨 순회를 위해서 배열 기반 원형 큐를 이용한다.

트리를 제외하고 부가적으로 자료구조를 이용할 때에는 메모리를 할당하지 않는 배열 기반으로 

그렇다면 군말없이 바로 시작해보자!

트리란? 

먼저 트리의 구조나 용어를 설명한다. 트리는 이러하다.

트리는 다음과 같이 여러 형태의 트리들이 올 수 있지만

그 중에 이진 탐색 트리에 대해서 기록할 것이다. 위 그림에서 가운데에 있는 트리 구조가 가장 이진 탐색 트리를 잘 나타낸 이진 탐색 트리의 모형이라고 보면 된다.

그러면 이진 트리란?

이진 트리에 논하기에 앞서, 가장 작은 단위인 노드부터 자세히 살펴보면 다음과 같은 구조로 되어 있다.

이런 노드를 요리조리 이용하면 트리를 완성시킬 수 있는데, 노드가 이렇게 최대 두 개의 자식을 가질 수 있는 형태로 이루어져 있으며, 이러한 노드들로 구성되어 있는 트리를 이진 트리라고 한다.

그러면 이진 탐색 트리는 또 무엇인가? 이진 탐색 트리는 이진 트리이긴 한데, 탐색이 가능한 트리라서 이진 탐색 트리라고 한다! 그러기 위해선 일정 조건들이 추가 되어야 하는데 조건은 다음과 같다.

위와 같은 조건을 가지고 있는 이진 트리가 이진 탐색 트리가 될 수 있다.

다음 포스팅은 삽입, 삭제, 탐색을 적절히 나눠서 여러 차례 포스팅한다.

오늘은 덱? 디큐? 라고 불리우는 자료구조이다.

Dequeue 는 매우 혼종이다. 큐라고는 불리우는데 큐의 특징 이외에 스택의 특징을 가지고 있기 때문이다. 선입선출 / 후입선출 등의 개념을 모두 가지고 있다. 먼저 들어온 놈이 먼저 나갈 수 있고, 나중에 들어온 놈이 먼저 나갈 수도 있다는 것이다.

도데체 어떤 구조이길래 위와 같은 특징을 가지고 있을까? 다음과 같다.

위와 같은 구조이다. 뒤에서도 (tail의 사이드) 추가 및 삭제가 가능해야 하기 때문에 꼭 양방향 링크로 구성이 되어야 한다!!!!! 

그런데 뭐, 이제까지 다 다뤄봤던 구조들이기 때문에 예를 들어, 양방향 링크라든지 head와 tail이 함께 있는 구조라든지 어렵지 않은 부분들이므로 간단하게 설명한다.

초기화와 Dequeue의 비워짐 / 꽉 참의 확인

먼저, 초기화는 Head와 Tail 을 NULL로 초기화 하는 것으로 시작한다.

그리고 이러한 초기화에 따라서, Head와 Tail이 NULL 인 경우가 비워진 경우이고, 해당 Dequeue의 꽉 찬 상태는 확인할 필요가 없다. 왜냐하면 연결 기반의 큐이기 때문에 추가하는 수의 제한이 없다고 보면 되기 때문이다.

노드 추가

위 그림으로 설명이 충분하다고 생각한다. 노란색이 추가되는 노드이고, head와 tail 은 각각 옮겨가는 것을 표현한 것이다.

노드 삭제

노드 그림을 그리지 않고 코드로만 설명해도 되겠다고 판단하여 그림을 그리지 않는다. 코드의 주석만으로 충분한 설명이 되었다고 본다.

탐색

탐색은 다른 리스트들과 마찬가지로 링크들을 타면서 순회하는 것이기 때문에 딱히 구현하지 않았다.

메모리 관리

배열 기반의 원형 큐를 통해 메모리 관리를 한다.

소스 코드 및 실행 결과

리스트 기반 큐는 뭐 간단하다. 그냥 일반 큐인데 연결 리스트로 이루어진 큐이다.

기본 형태는 다음과 같다.

매우 간단하다. 그래서 행복하다 

기본적으로 배열 기반의 큐와 똑같이 동작한다. 그러나 배열 기반 큐와 다른 점은 크기가 정해져 있지 않고 동적이고 가변이기 때문에 뭐, 꽉 찬 것으로 보이지만 비어있네, 마네 뭐 이런 배열 기반 큐의 치명적인 단점을 생각할 필요가 없다.

Front 노드 포인터를 통해서 가장 먼저 들어온 노드를 가리키며, 삭제 연산을 진행할 때마다 Front 노드 포인터를 한 노드씩 옮긴다. 그리고 Rear 노드 포인터를 통해서 가장 마지막에 추가된 노드를 가리키며, 삽입 연산을 진행할 때마다, Rear 노드 포인터를 새로운 노드로 갱신한다. 

삽입 연산

삭제 연산

꽉참/비어짐 확인 연산

꽉 찼는지는 연결 리스트이므로 확인할 필요가 없으니, 비어져있는 상태만 확인하면 되는데 이 역시 매우 간단하다.

메모리 관리

이번에는 연결 리스트 기반 스택으로 관리한다.

코드 및 실행 결과

자 오늘도 학습했던 원형 양방향 연결 리스트를 정리할 때가 됐다. 이게 정리를 바로바로 안 하다보니 후, 코드를 다시 이해해야한다. 뭐 복습도 되고 참 좋다;;;

먼저 오늘 할 것은

원형 - 무한 순회가 가능한 -> 그래서 순회에 조건이 꼭 붙는,
양방향 - 노드의 양쪽 링크가 존재하는 -> 그래서 원형 순회 실현이 가능한
연결 리스트

를 포스팅 한다.

원형이라고 해서 개인적으로 위와 같은 형태로  생각하면 혼란만 가중할 것이라고 생각한다. 아래와 같이 말이다.

그래서 우리는 머릿속의 형태를 정해놓고 시작해보고자 한다.

이러한 형태 임을 꼭 기억하고 있어야 한다.

노드 삽입 연산

삽입 연산은 노드가 없을 때와 있을 때로 나눈다.

크 따로 부가 설명이 필요 없을 것 같다ㅋ 

노드 삭제 연산

삭제는 간단하다. 그림 하나로 표현 가능하다.

그 이외에 순회 연산

순회 연산은 그냥 노드의 링크를 순방향/역방향으로 타는 인덱스 포인터를 만들어서 순회를 하면 된다. 다만, 원형 연결 리스트인 만큼 무한 반복에 빠질 수 있기 때문에 아래와 같은 조건을 넣어 무한 반복에서 탈출하도록 해야한다.

위 코드는 순방향 순회, 역방향 순회 모두 마찬가지로 해당되는 부분이다.

메모리 관리 부분

해당 코드에서 또한 메모리 관리 부분이 따로 있기 때문에 삭제 연산 시에도 바로 메모리를 제거 하지 않고 프로그램 종료 전에 한꺼번에 모두 free 시키도록 되어 있다.

클래스로 stack 컨테이너 어댑터로 아래와 같이 구현되어 있다.

코드 및 실행 결과

스택을 연결리스트로 구현해 보았다.

일단 기본 구조에 대한 예시를 나타낸 것이다.

먼저, 왼쪽 구조를 보자. 우리 스택이라고 생각하는 구조이다. Head는 삽입 인덱스를 나타낸다. 소위 말하는 top 변수. 그 왼쪽의 구조를 단순화시켜서 보면 오른쪽처럼 나타낼 수 있다. 오른쪽 구조에서 Head 노드는 새롭게 노드가 삽입될 때 마다 가리키는 것을 갱신시키는데, 이 현상을 자세히 보면 왼쪽 구조에서 head가 옮겨다니는 것과 같다. 

다른 현상을 가지고 생각하기 나름으로 같은 본질을 끌어냈다 크.. 윤성우 교수님께 박수를...

암튼 왼쪽이든 오른쪽이든 위와 같은 본질의 구조를 구현할 것이다.

삽입 연산

1) 헤드와 기존 최 상단 노드의 연결을 끊고, 2) 새 노드와 최상단 노드를 연결하여 새 노드를 최상단 노드로 변경하고,  그 3) 최상단 노드를 헤드가 가리키도록 헤드 값을 갱신 

삭제 연산

삭제의 기본 동작은 노란색 글씨와 빨간색 글씨로 표현을 해두었다.

파란색 글씨는 대충 이런 말이다. 할당된 메모리는 따로 이전에 만들어 뒀던 자료구조로 따로 저장하여 관리하고 프로그램 종료 시, 일괄로 삭제하기 때문에 관련 포인터만 변경하고(모든 포인터 연결을 삭제 '처리') 삭제 되었다고 생각하고 진행하라는 의미이다. 

비어짐 확인

이런 구조에서 비어짐을 확인하려면 어떻게 하면 될까? 
> Head가 NULL을 가리키면 텅 빈 상태입니다. (O)
이런 구조에서 꽉 참을 확인하려면 어떻게 하면 될까?
> 연결 리스트 기반이라 꽉 찰 것을 걱정하지 않아도 됩니다.(O) 그 걱정대신 작성자 나이 걱정을.... (ㅜ.ㅜ)

뭐 더 쓸 말이 없다.

코드 및 실행 결과

프로그램 코드를 제출하기에 앞서 복습도 할 겸,
이전에 배웠던 원형 큐를 활용하여 메모리가 생성될 때마다 원형 큐에 메모리 주소를 넣고, 프로그램이 종료될 때 일괄적으로 free~~~~~~~ 된다. 그니까 생성만 했다하면 원형 큐에 넣어제끼고, 프로그램이 끝나기 직전에 다 소멸시켜버리는 것이다. 그래서 실행 결과가 지저분하여 실행결과도 약간의 설명을 넣을 예정이다.

혹시 보는 사람이 있다면 스택 부분만 참고하면 될 듯 합니다. 앞으로도 쭉 요래요..ㅋㅋ

스택이란 정말 간단하다.

분명히 내가 이거 그림 그리면서 포스팅을 한거 같은데 아무리 블로그를 뒤져봐도 없다... 그래서 다시 하는 느낌으로 스택 첫 포스팅을 시작한다.

먼저, 

스택이란 무엇인가?

우리는 스택을 이미 알고 있다. 스택은 프링글스이다. 아래의 그림을 보자.

우리는 세 개의 감자칩 중에서 어떤 감자칩이 제일 먼저 들어갔는지 알 수 있다. 바로 A이다. 어떻게 알았지? 출입구가 하나이고, 원통 내부의 크기는 서로가 뭐 어떻게 비집고 해서 바꿀 수 있는 사이즈가 아니다. 

A가 먼저 들어갔고 -> 그 다음 B가 그 위에 쌓이고 -> 그 후 C가 들어가면서 그 위에 쌓이는 것이다.

이렇듯 스택은 쌓이는 특징을 가지고 있다. 그렇다면 안의 감자칩을 꺼내먹을 때에는 어떻게 할까? 

가장 나중에 들어간 C가 제일 먼저 다시 나오고 -> 그 다음 B가 나오고 -> 가장 먼저 들어간 A가 제일 늦게 나온다. 

이렇게 나중에 들어간 값이 제일 먼저 나오는 구조를 후입선출 구조라고 한다.

단순 배열 기반 스택에서의 삽입

어려울 것이 전혀 없다. 그냥 값이 들어오는데로 쌓아올린다고 생각하고 인덱스를 증가시키면서 값을 추가하면 된다.

하나도 어렵지 않다. 이렇게 보면 그냥 배열 끝에 값을 추가하는 것 같다. 우리는 스택에 값을 추가하는 행위를 push 라고 할 것이다. 삭제 연산을 보자. 

단순 배열 기반 스택에서의 삭제

3 값이 튀어나가면서 삭제 처리가 되어 버리고, 삽입 인덱스가 하나 감소한다.

마지막 하나 남은 1이 튀어 나가며 값이 삭제 처리 되고, 삽입 인덱스가 갈 곳을 잃는데 이 때, 삽입 인덱스를 -1로 하자. 그러면 나중에 빈 스택 상태에서 값을 추가할 때, 삽입 인덱스를 증가시키면 [-1] 에서 [0]으로 바뀌어서 자연스럽게 값을 추가하면 될 뿐만 아니라, 스택이 비어있는지 비어있지 않는지 삽입 인덱스가 -1인지 아닌지를 보면 된다.

그리고 우리는 삭제하는 연산을 pop 한다고 할 것이다.

단순 배열 기반 스택에서의 비워짐과 꽉참을 확인

또한 간단하다.
인덱스가 비워져 있는지를 확인하기 위해선 아까 삭제 연산에의 약속대로 삽입 인덱스가 -1인지를 확인하면 된다. 
인덱스가 가득차 있는지를 확인하기 위해선 현재 삽입 인덱스가 배열의 길이랑 같은지를 확인하면 된다.

코드 및 실행 결과

드디어 원형 큐이다. 자기소개 페이지를 좀 작성하느라, 기록을 하지 못했다.. ㅎㅎ ㅠ.ㅠ

일단, 원형 큐이다. 지난 포스팅 기록에서 처럼 구조로 인해 어쩔 수 없는 단점과 문제를 가지고 있는 일반 배열 기반 큐에서 개선된 것이 원형 큐이다. 그 단점이자 문제는 다음과 같다.

아니 그러면, 삽입 인덱스와 꺼냄 인덱스를 모두 초기화 시켜서 다시 앞으로 옮겨오면 되는 것 아닌가? 라는 생각이 들었었는데 이를 반박할 수 있는 사례가 또 나타난다....

바로 이 경우이다. 순서대로 읽으면 된다. 35와 43 값을 추가 후, 배열의 끝이기 때문에 가정했던대로 삽입 인덱스를 초기화 시켜서 다시 삽입하여 공간을 활용하려는 노력이 보이는 그림이다. 그럼 만약에 위 상황에서 데이터를 순회하려면 어떻게 해야하는가?

7 -> 11 -> 15 -> 35 -> 43 으로 순회를 해야할까? 아니다. 이렇게 되면 큐의 기본 원리에 제대로 위배된다. 35와 43이 먼저 나와야한다. 

위 상황에서 큐의 기본 원리를 지키며 데이터를 순회하기 위해서는
1) 꺼냄 인덱스부터 먼저 확인 후 값을 꺼낸 뒤,
2) 다시 꺼냄 인덱스를 초기화하여 인덱스 0부터 들어간 값을 꺼내며 인덱스를 증가시키고,
3) 삽입 인덱스와 접하는지를 확인한다.
-> 2, 3 을 반복한다.

나 같으면 위와 같은 짓, 안 하겠다. 원형 큐에 대해 당장 알아본다.

먼저, 왼쪽과 같은 일반 배열을 오른쪽처럼 가상으로 구부렸다고 생각하고 모든 기록을 전개할 것이다. 기본 세팅에 대해서 좀 더 설명하자면, 다음 그림과 같다.

일반 큐처럼 삽입 인덱스와 꺼냄 인덱스가 존재하며, 이름이 각각 그림과 같이 달라질 뿐이다. 그리고 각 인덱스는 대입 연산이나 삭제 연산이 진행된 후에 증가하는 형태를 기본으로 한다.

그럼 삽입과 삭제는 그림 한 장으로 설명이 가능할 것 같다.

그렇다면 삽입을 하려면 큐가 꽉 찾는지 확인해야하며, 삭제하려면 큐가 비어있는지 확인해야한다. 원형 큐의 문제가 바로 이것이기 때문에 중요하다!!!!

먼저, 다음 그림을 보면 문제가 뭔지 알 수 있다

큐가 모두 비었을 때와 가득 찼을 때의 인덱스들의 상태가 완전히 똑같다. 인덱스의 위치에 상관없이 front가 rear을 따라 잡았다는 소리는 삭제를 모두 완료했다고 볼 수 있다. 그러나, rear이 front를 따라 잡았다는 소리는 삽입을 모두 완료했다고 볼 수도 있기 때문이다. 아주 기가 막힙니다.

그래서 원형 큐를 삽입할 때, 큐의 길이 - 1 만큼만 삽입하도록 할 예정이다. 꽉 찬 상태와 텅 빈 상태는 그림과 같다.

이 약속들만 지킨다면 원형 큐를 구현하면서 기가 막힐 일은 없을 것이다.

코드 및 실행 결과

----