조건
다음의 조건을 충족하는 Mydeque 클래스를 구현하시오
제네릭 컬렉션의 사용을 금지하며, 배열을 사용해 구현한다.
클래스의 인스턴스 생성 시 최초 10의 크기를 가진다.
배열의 크기를 넘어서 데이터를 추가할 경우, 배열에 빈 자리가 없다면 현재 배열의 크기의 2배만큼 재할당해야 한다.
아래 필수 구현 메서드 외 내부 동작을 위한 필드 및 메서드 추가는 허용한다.
구현 메서드
- PushFront(T element) : 배열의 맨 앞에 데이터를 추가한다.
- PushBack(T element) : 배열의 맨 뒤에 데이터를 추가한다.
- PopFront() : 배열의 가장 앞의 데이터를 반환하고, 내부 배열에서 삭제한다.
- PopBack() : 배열의 가장 뒤의 데이터를 반환하고, 내부 배열에서 삭제한다.
- Clear() : 배열 내의 모든 데이터를 삭제한다.
수정 전
class Mydeque<T>
{
private T[] array;
private int size;
private int count;
public T[] GetArray => array;
public int Size => size;
public int Count => count;
public Mydeque()
{
size = 10;
array = new T[size];
count = 0;
}
public void PushFront(T element)
{
if (count >= size)
{
size *= 2;
Array.Resize(ref array, size);
}
Array.Copy(array, 0, array, 1, count);
array[0] = element;
count++;
}
public void PushBack(T element)
{
if (count >= size)
{
size *= 2;
Array.Resize(ref array, size);
}
array[count] = element;
count++;
}
public T PopFront()
{
if (count == 0)
return default(T);
T result = array[0];
count--;
Array.Copy(array, 1, array, 0, count);
array[count] = default(T);
return result;
}
public T PopBack()
{
if (count == 0)
return default(T);
count--;
T result = array[count];
array[count] = default(T);
return result;
}
public void Clear()
{
Array.Clear(array, 0, count);
count = 0;
}
}문제점
- 내장함수를 사용하면 더 짧고 쉽게 구현할 수 있겠지만,
배우는 입장에서는 지양하고자 한다.
초기 구현 방식
-
배열의 크기가 2배로 늘어나는건
Array.Resize()를 사용해 늘렸다. -
배열의 맨 앞에 값을 넣는
PopFront()는Array.Copy()를 사용해서array를 한칸 뒤로 밀고,
맨 앞에는array[0] = element를 사용해 값인element를 할당했다. -
배열을 초기화하는
Clear()는Array.Clear(array, 0, count)클리어 내장함수를 사용했다.
과정
-
내장함수를 사용하지 않고 직접 구현하고자 했다.
-
Array.Resize와Array.Copy를 대체할 함수를 만들었다.
T[] GetValues(T[] array)
private T[] GetValues(T[] array)
{
size *= 2;
T[] temp = new T[size];
for (int i = 0; i < count; i++)
{
temp[i] = array[i];
}
return temp;
}-
내장함수인
Array.Resize를 대체하는 함수다. -
현재 배열의 크기인
size를 2배로 만든 후, 그 크기만큼의 새 배열temp를 생성한다. -
for문을 통해temp에 매개변수array배열의 값들을 할당하고temp를 반환한다.
T[] FrontCopy(T[] array)
private T[] FrontCopy(T[] array)
{
T[] temp = new T[size];
for (int i = 0; i < count; i++)
{
temp[i + 1] = array[i];
}
return temp;
} -
PushFront(T element)에서 사용한Array.Copy를 대체할 함수다. -
인덱스를 하나씩 증가시켜 제일 앞인
0을 비워둔다.
public void PushBack(T element)
private T[] PopCopy(T[] array)
{
T[] temp = new T[size];
for (int i = 0; i < count; i++)
{
temp[i] = array[i + 1];
}
return temp;
}-
PopFront()에서 사용한Array.Copy를 대체하는 함수다. -
기존 배열의 인덱스를 하나씩 증가시켜서 한칸 앞으로 당긴다.
PushFront(T element)
// PushFront(T element) : 배열의 맨 앞에 데이터를 추가한다.
public void PushFront(T element)
{
if (count >= size)
{
array = GetValues(array);
}
array = FrontCopy(array);
array[0] = element;
count++;
}-
값을 할당하기 전
size로 크기 체크 및Getvalues(array)로 확장 -
기존 값을 뒤로 밀고 0번째 자리에 값 추가
PushBack(T element)
// PushBack(T element) : 배열의 맨 뒤에 데이터를 추가한다.
public void PushBack(T element)
{
if (count >= size)
array = GetValues(array);
array[count] = element;
count++;
}- 배열 끝에 값 추가
PopFront()
// PopFront() : 배열의 가장 앞의 데이터를 반환하고, 내부 배열에서 삭제한다.
public T PopFront()
{
if (count == 0)
return default(T);
T result = array[0];
array = PopCopy(array);
count--;
return result;
}-
제일 앞의 값을
result에 담고 반환 -
PopCopy(array)로 값들을 한칸씩 당김 -
내부 배열에서 삭제했으니
count감소
PopBack()
// PopBack() : 배열의 가장 뒤의 데이터를 반환하고, 내부 배열에서 삭제한다.
public T PopBack()
{
if (count == 0)
return default(T);
count--;
T result = array[count ];
array[count] = default(T);
return result;
}- 제일 뒤의 값을 반환 후 제거
Clear()
// Clear() : 배열 내의 모든 데이터를 삭제한다.
public void Clear()
{
array = new T[size];
count = 0;
}Array.Clear사용하지 않고 초기화
조건에 맞는 동작들은 전부 작동한다고 생각하지만,
Head와 Tail을 사용하지 않았는데 Deque 라고 할 수 있으려나
