Deque 학습

📗 toArray()

 

queue의 친구쯤 되는 사이이며 데크, 덱, 디큐정도로 불리나 덱이라고 많이 표현합니다.

queue는 단방향이라면 deque는 양방향입니다.

배열이나 연결리스트로 구현을 할 수 있습니다.

 

 

 

이점

1. 작업 스케쥴러의 자료구조

2. 스택이나 노멀 큐의 역할

3. 작업의 실행 취소의 기능

 

 

 

양방향으로 삽입, 삭제가 가능하다.

 

삽입, 삭제연산이 양끝단에서 이루어지므로

요소의 크기와 관계없이 모두 O(1)의 시간복잡도를 가집니다.

 

 

 

 

 

---

 

Java구현

 

연결리스트, 배열중 배열로 구현을 해보겠습니다.

배열을 선형의 이미지로 구현하면 연산작업의 비효율성, 메모리 낭비가 야기되므로

원형 큐의 형식으로 구현하겠습니다.

 

 

 

 

 

인스턴스 변수

DEFAULT_CAPACITY : 배열의 기본 크기

array : 요소가 추가되는 배열

size : 실제 요소의 크기

front : 요소 추가시 반시계 방향으로 이동

tail : 요소 추가시 시계 방향으로 이동

 

여러 형태의 값을 받을 수 있게 Type parameter를 추가합니다.

Clonable은 copy를 위해서 사용합니다.

Generic이나 Copy 모두 자료구조의 공부의 취지에서는 선택적 사항이기 때문에 제외시켜도 됩니다.

 

 

(capacity와 size는 다릅니다. capcity는 배열이 메모리에 할당받은 물리적인 크기이며

size는 배열안에 존재하는 요소의 수를 뜻합니다.)

 

 

 

 

생성자

기본생성자와 capacity를 받는 생성자 2개를 작성합니다.

기본 생성자의 경우 default값을 배열의 크기로 설정합니다.

 

 

 

 

위와 같은 모습으로 자료구조가 시작이 됩니다.

 

 

 

 

 

📗OfferFirst()

 

resize 조건

보통 원형큐에서는 공백 상태와 포화 상태를 구분하기 위해 1칸을 비워두며 front와 tail의 값이 같으면 공백상태로 봅니다.

size == array.length로 resize() 조건을 검사하면 공백을 보장받을 수 없습니다.

사실 1칸의 여백이 없어도 size로 체크하던가 구현 나름이라 생각합니다.

 

 

 

반시계 방향으로 삽입을 합니다.

front의 값은 실제 전방요소의 위치보다 "-1"에 

tail의 값은 후방요소의 위치와 동일하게 위치합니다.

 

size가 capactiy와 같다면 capactiy를 2배 늘려줍니다.

front값에 item을 넣어준 후에 front값에 반시계방향(-1)으로 한칸 이동한 값을 할당합니다.

 

front = (front - 1 + array.length) % arrat.length ?

front -1의 값이 음수이거나 양수이거나 두개의 케이스만 중심적으로 확인해봅니다.

 

 

front - 1 : 음수의 경우

front가 0이라면 0의 위치에 item 삽입을 하고 capcity가 5라면

front에는 4의 값을 넣어줍니다.

 

front = (front - 1 + array.length) % arrat.length;

반시계방향으로 돌리기도 하며 front가 0이면 배열의 마지막으로 이동시키도 하는 로직입니다.

-1은 이동하는 범위이며 쉽게 바라보기 위해 이동연산은 제외하겠습니다.

 

(front + array.length) % array.length;

배열의 크기가 4일때 front값이 -1이라면 (0일때 offerFirst를 호출하면 -1)

"3 % array.length" -> "3 % 4"가 됩니다.

 

 

0에 item을 넣고 front값은 3으로 변경됩니다.

 

front - 1 : 양수의 경우

배열의 크기 4, front 4라고 가정하면 array[4] = item;에 값을 넣고

front 값은 "(4 - 1 + 4) % 4" 3의 값이 됩니다.

 

 

 

 

 

 

 

 

 

 

📗OfferLast()

 

시계 방향으로 삽입을 합니다.

offerFirst()와 같이 용량체크를 하며 이번에는 "(tail + 1) % array.length" 로직으로 시계방향으로 이동합니다.

tail의 다음 값이 배열의 크기와 같다면 tail(3) % capacity(3)은 0이 되며 tail에는 0이 할당되며

array[N] 삽입의 다음 목표는 array[0] 가 됩니다.

tail의 다음 값이 배열의 크기보다 작다면 tail(2) % capacity(3)은 2가 됩니다.

 

 

 

 

 

 

 

 

 

 

📗PollFirst()

전방위치에서 요소를 1개 제거합니다.

front는 반시계 방향으로 데이터가 쌓이므로 제거할 때는 시계방향으로 이동합니다.

front는 -1이 기본적용이 되므로 front + 1 위치의 요소를 삭제합니다.

 

Tip

시계 방향의 인덱스를 얻기 : (idx + 1) % capacity

반시계 방향의 인덱스 얻기 : (idx - 1 + capacity) % capacity

 

 

 

 

array가 Object배열입니다. 하지만 enque, deque연산에서 E type으로 받고 있으니

경고문은 잡아주도록 합니다.

 

capacity가 기본 값보다 크면서 요소의 개수가 capacity의 1/4 미만일 때

resize()를 호출합니다. 

껍데기가 어느 정도 큰데 알맹이가 너무 없는 경우를 확인합니다.

 

reisize()를 사용하는데 최소 DEFAULT_CAPACITY의 크기만큼은 보장을 받습니다.

 

 

 

 

 

 

📗PollLast()

PollFirst()의 반대버전입니다. tail을 참조하여 deque연산을 합니다.

PollFirst()에서 설명하였으니 넘어갑니다.

 

 

 

 

 

 

 

 

 

📗Peek()

요소를 삭제하지 않고 확인만 합니다.

 

 

 

 

 

 

 

📗resize()

배열의 크기에 비해 요소의 수가 너무 적거나 배열이 꽉 찬경우 크기를 변경합니다.

 

i는 새로운 배열의 idx이며 j는 기존배열의 idx입니다.

원형큐는 한 칸을 비워둔 채로 운용하므로 i를 1부터 시작합니다.

할당이 모두 완료되면 front는 1, tail은 size를 할당합니다.

원형큐의 특징으로 실제 요소의 위치 -1에 front값이 배정됩니다.

 

 

 

 

 

 

 

여기서부터는 자료구조의 범위를 벗어납니다.

 

📗 clone()

자기 자신을 복사하여 반환합니다.

 

SuppressWarnings annotation은 위에서 설명하였으므로 제외합니다.

clone()을 사용하려면 해당 클래스가 Cloneable interface를 사용하여야 합니다.

clone()만을 사용하여 반환하는 경우 배열 안의 참조타입 요소들은 얕은 복사를 합니다.

Arrays.copyOf()를 사용하여 깊은 복사를 해줍니다.

clone 된 ArrayDeque class의 배열에 할당하고 반환합니다.

이제 기존 데이터를 참조하는 clone 객체가 아닌 clone 객체가 배열 모두 깊은 복사된 것을 반환합니다.

 

2차원 배열이거나 참조타입 요소 안의 인스턴스 변수가 참조타입인 경우 모두 직접 깊은 복사를 해줘야 합니다.

 

 

 

 

 

 

📗 toArray()

 

이미 존재하는 배열을 받아 ArrayDeque의 배열을 넣어줍니다.

깊은 복사를 해서 반환하는 것이 아니니 사용에 주의가 필요합니다.

 

size가 0인 경우는 newArray를 그대로 반환합니다.

(공백상태와 포화상태를 구분시켰다면 front == tail 로도 가능합니다.)

 

i는 새로운 배열의 idx, j는 기존 배열의 idx입니다.

front + 1이 array.length의 이상이 되는 경우를 고려해 나머지 연산을 합니다.

 

반복문을 돌며 array[j]의 값을 newArray[i]에 넣어주는 것이 끝입니다.

 

반복의 조건은 "i가 새로운 배열의 크기보다 작으면서 또한 기존 배열의 요소의 수보다 작아야 한다" 입니다.

이는 상태가 1️⃣ 새로운 배열을 다 돌았다. 2️⃣ 기존 배열의 요소를 모두 복사했다. 둘 중 하나라도 만족을 하면 복사를 종료하는 것을 뜻 합니다.

 

기존 배열의 값을 새로운 배열에 꽉 차게 복사하거나 기존 배열의 값의 개수가 새로운 배열의 크기보다 작더라도 있는 것이라도 복사한다는 뜻입니다.

 

 

 

 

 

 

 

📗 toArray()

새로운 배열을 받지 않고 기존배열의 값을 모두 복사해서 반환합니다.

 

위에서 작성을 한 toArray(T[] newArray)를 사용합니다.

기존 배열의 요소의 수만큼 크기를 가지는 배열을 만들어 사용합니다.

 

 

 

📗 clear()

배열을 초기화합니다.

 

 

 

 

 

📗 Sort()

배열을 정렬합니다.

toArray로 기존 배열을 받아와 Arrays.sort()로 정렬합니다.

정렬의 기준을 구현한 Comparator를 사용하지 않는 경우 요소에 구현되어 있는 CompareTo()를 사용합니다.

기존 배열은 null로 초기화하고 System.arraycopy()로 기존 배열의 1번부터 정렬된 값을 넣습니다.