DeQueue
덱(Dequeue)은 Doubly-Ended-Queue의 약자로 양 끝에서 데이터의 추가, 삭제가 가능한 선형 자료구조이다. 스택과 큐의 장점을 모아서 만들어진 형태로, 제한에 따라 선입선출, 후입선출 등 다양한 쓰임에 활용될 수 있다.
Dequeue 장점
- 입력과 출력이 양방향이 가능하며, 활용에 따라서 스택처럼 또는 큐처럼 사용이 가능하다.
- 추가와 삭제의 실행속도가 O(1)으로 추가, 삭제가 빈번하게 일어나는 구조에 장점을 갖는다.
Dequeue 구현
C#에서는 덱이 구현이 안되어있기 때문에, 다양한 방법으로 구현이 가능하며 이 중 나는 속도가 빠른 배열로 구현했다.
Field
public class MyDeQueue<T>
{
private int capacity = 10;
private T[] array;
private int head;
private int tail;
}우선 Queue와 같이 head와 tail을 활용해 Dequeue를 구현하고자했다. head는 front의 입출력을 tail은 rear(back)의 입출력을 담당하며, 기본 배열 크기는 10에 데이터가 모두 차있는 경우 배열의 크기를 2배로 늘려 추가를 진행한다.
Init, First
public MyDeQueue() => Init();
public void Clear() => Init();
public void Init()
{
array = new T[capacity];
head = 0;
tail = 0;
}
public bool First(T element)
{
if (head == 0 && tail == 0)
{
array[0] = element;
head = array.Length - 1;
tail++;
return true;
}
return false;
}Init() 을 초기화 메서드로 작동할 수 있게 하고, 생성자와 Clear를 Init()에 연결시켰다. First의 경우 맨 처음 데이터를 추가하는 경우 작동되도록 하여, 데이터가 가득 찬 상황과 초기 상황을 구분지었다.
Duplicate
public void Duplicate()
{
T[] newArray = new T[array.Length * 2];
if(head < tail)
{
Array.Copy(array, head, newArray, 0, tail - head);
}
else
{
Array.Copy(array, head, newArray, 0, array.Length - head);
Array.Copy(array, 0, newArray, array.Length - head, tail + 1 );
}
head = 0;
tail = array.Length;
array = newArray;
}Duplicate()는 데이터가 가득 찬 상태에서 Push를 진행하는 경우 배열의 크기를 2배로 늘리는 메서드이다. 복제 과정에서 데이터가 head - tail 순으로 정리되도록 구현했다.
Push
public void Pushfront(T element)
{
if(First(element)) return;
if (IsUnPushable()) Duplicate();
if(head == 0)
{
array[head] = element;
head = array.Length - 1;
}
else
{
array[head] = element;
head--;
}
}
public void PushBack(T element)
{
if (First(element)) return;
if (IsUnPushable()) Duplicate();
if (tail == array.Length - 1)
{
array[tail] = element;
tail = 0;
}
else
{
array[tail] = element;
tail++;
}
}처음으로 데이터를 저장하는 경우 First()로 구동이 되고, 그 이후부터는 front는 head에 의해 back은 tail에 의해 저장되도록 구현하였다.
Pop
public T PopFront()
{
if(head == array.Length)
{
head = 0;
T temp = array[head];
array[head] = default(T);
return temp;
}
else
{
T temp = array[++head];
array[head] = default(T);
return temp;
}
}
public T PopBack()
{
if (tail == 0)
{
tail = array.Length - 1;
T temp = array[tail];
array[tail] = default(T);
return temp;
}
else
{
T temp = array[--tail];
array[tail] = default(T);
return temp;
}
}Pop()은 데이터를 제거하는 함수로, Push와 마찬가지로 front는 head에 의해, back은 tail에 의해 제거되도록 구현했다.
Main Method
static void Main(string[] args)
{
MyDeQueue<int> myDeQ = new();
for (int i = 1; i < 15; i++)
{
if(i % 2 == 0)
{
myDeQ.Pushfront(i);
}
else
{
myDeQ.PushBack(i);
}
}
}10 8 6 4 2 1 3 5 7 9 11 13 ... 14 12실제로 1부터 14까지의 수를 번갈아 저장할 때 다음과 같이 저장되는 것을 볼 수 있다.
시행착오
DeQueue를 잘못 이해하여 나의 첫 Dequeue는 양방향 선입선출로 탄생했다. 꽤 작업이 오래걸렸기도하고, 섣부른 이해로 잘못된 알고리즘을 또 다시 구현하지 않도록 첫 Dequeue 코드를 이 글에 박제하려한다.
Field, 초기화
public class MyDeQueue<T>
{
private int capacity = 10;
private T[] array;
private int frontHead;
private int frontTail;
private int backHead;
private int backTail;
private int crossing;
public MyDeQueue() => Init();
public void Init()
{
array = new T[capacity];
frontHead = 0;
frontTail = 0;
backHead = capacity - 1;
backTail = capacity - 1;
}
public void Clear() => Init();
}Duplicate
public void Duplicate()
{
int newCapacity = capacity * 2;
T[] Newarray = new T[newCapacity];
Array.Copy(array, frontHead, Newarray, 0, crossing - frontHead);
Array.Copy(array, crossing + 1, Newarray, newCapacity - (backHead - crossing), (backHead - crossing));
array = Newarray;
frontTail = crossing - frontHead;
frontHead = 0;
backTail = newCapacity - (backHead - crossing + 1);
backHead = newCapacity - 1;
}Pushable, Popable
public bool IsUnPopFrontable()
{
if (frontHead != frontTail)
{
return array[frontHead].Equals(default(T));
}
else
{
return false;
}
}
public bool IsUnPopBackable()
{
if (backHead != backTail)
{
return array[backHead].Equals(default(T));
}
else
{
return false;
}
}
public bool IsPushFrontUnAddable()
{
if (frontTail < backTail)
{
return (frontTail + 1 == frontHead);
}
else
{
return (frontHead == 0);
}
}
public bool IsPushBackUnAddable()
{
if (frontTail < backTail)
{
return (backTail - 1 == backHead);
}
else
{
return (backHead == 0);
}
}Push
public void PushFront(T element)
{
if(IsPushFrontUnAddable())
{
Duplicate();
}
array[frontTail] = element;
++frontTail;
ChangeTail();
}
public void PushBack(T element)
{
if (IsPushBackUnAddable())
{
Duplicate();
}
array[backTail] = element;
--backTail;
ChangeTail();
}Pop
public T PopFront()
{
if(IsUnPopFrontable())
{
ChangefrontHead();
}
if (!array[frontHead].Equals(default(T)))
{
T temp = array[frontHead];
array[frontHead] = default(T);
frontHead++;
return temp;
}
else return default(T);
}
public T PopBack()
{
if (IsUnPopBackable())
{
ChangebackHead();
}
if (!array[backHead].Equals(default(T)))
{
T temp = array[backHead];
array[backHead] = default(T);
backHead--;
return temp;
}
else return default(T);
}Change Index
public void ChangeTail()
{
if (frontTail == backTail)
{
crossing = frontTail;
frontTail = 0;
backTail = array.Length - 1;
}
}
public void ChangefrontHead()
{
frontHead = 0;
}
public void ChangebackHead()
{
backHead = array.Length - 1;
}
뚠뚠뚠뚠