지금까지 배웠던 자료구조에 관해서, Deque까지 포함하여 직접 구현해보며 원리를 이해하는 시간을 가져 보려 한다.
1. Stack
스택 (Stack)
선입후출(FILO), 후입선출(LIFO) 방식의 자료구조로 가장 최신 입력된 순서대로 처리해야 하는 상황에 이용한다.
스택을 구현할 수 있는 방법은 배열을 사용하는 방법과, 리스트를 사용하는 방법이 있다.
1.1 배열을 사용해 구현한 Stack
배열을 사용해 구현하려고 할 때, 구현 조건을 정해 놓고 구현하는 것이 좋다. 따라서 아래와 같은 전제 조건을 달고 구현해보려고 한다.
- StackT 클래스의 사용을 금지하며, 배열을 사용해 구현한다.
- 클래스의 인스턴스 생성 시 최초 10의 크기를 가진다. 배열의 크기를 넘어서 데이터를 추가할 경우, 현재 배열의 크기의 2배만큼 재할당해야 한다.
- 아래 필수 구현 메서드 외 내부 동작을 위한 필드 및 메서드 추가는 허용한다.
- Push(T element) : 배열의 맨 뒤에 데이터를 추가한다.
- Pop() : 가장 마지막에 추가한 데이터를 반환하고, 내부 배열에서 삭제한다.
- Peek() : 가장 마지막에 추가한 데이터를 반환한다.
- Clear() : 배열 내의 모든 데이터를 삭제한다.
이와 같은 스택의 기능을 구현하는 데에 있어서의 핵심은, int top이라는 변수를 두어 배열의 빈 칸을 가리키게 하는 방식을 활용하는 것이다. 데이터를 추가하면 top을 1씩 증가시키고, 데이터를 제거하면 top을 1씩 감소시키는 방식으로 스택을 구현하였다.
public class MyStack<T>
{
const int arraySize = 10;
private T[] array = new T[arraySize];
private int top = 0;
public void Push(T item)
{
if (top == array.Length)
{
T[] newArray = new T[2* array.Length];
Array.Copy(array, newArray, array.Length);
array = newArray;
}
array[top] = item;
top++;
}
public T Pop()
{
T temp;
if(top > 0)
{
temp = array[top-1];
Array.Clear(array, top-1, 1);
top--;
return temp;
}
else
{
return default;
}
}
public T Peek()
{
if (top > 0)
{
return array[top-1];
}
else
{
return default;
}
}
public void Clear()
{
Array.Clear(array,0,array.Length);
top = 0;
}
}특히나 구현이 어려웠던 점은 Push를 넣을 때 배열이 꽉 찼을 시 배열을 늘리는 방법이었는데, 이를 해결하기 위해서 Stack의 함수 구조 자체를 분석해보기도 했다. 핵심은 Array.Copy라는, 함수를 복사할 수 있는 기능을 활용하는 것이었고 이와 같이 만들어낸 스택 함수로 기능이 정상작동하는 것을 확인하였다.
1.2 리스트로 구현하기
리스트로 구현할 경우 훨씬 더 구현이 쉬워진다.
우선 리스트의 경우에는 배열처럼 크기 제한이 없으므로 아래와 같이 구현 가능하다.
public class MyStack2<T>
{
private List<T> list = new List<T>();
// 스택의 개수를 세기 위함
public int count => list.Count();
public void Push(T item)
{
list.Add(item);
}
public T Pop()
{
T result = list[list.Count-1];
list.RemoveAt(list.Count-1);
return result;
}
public T Peek()
{
T result = list[list.Count - 1];
return result;
}
public void Clear()
{
list.Clear();
}
}2. Queue 구현하기
큐(Queue)
선입선출(FIFO), 후입후출(LILO) 방식의 자료구조로, 입력된 순서대로 처리해야 하는 상황에 이용한다.
큐 또한 구현해 보려고 한다. 큐의 경우 배열로 구현하는 방법과 연결리스트로 구현하는 방법이 있으나, 연결리스트로 구현하는 방법은 효율이 좋지 않기 때문에 배열로 구현하는 방법만 시도해 보았다. 아래와 같이 조건을 정하여 구현해 보기로 했다.
- QueueT 클래스의 사용을 금지하며, 배열을 사용해 구현한다.
- 클래스의 인스턴스 생성 시 최초 10의 크기를 가진다. 배열의 크기를 넘어서 데이터를 추가할 경우, 현재 배열의 크기의 2배만큼 재할당해야 한다.
- 아래 필수 구현 메서드 외 내부 동작을 위한 필드 및 메서드 추가는 허용한다.
- Enqueue(T element) : 배열의 맨 뒤에 데이터를 추가한다.
- Dequeue() : 제일 처음에 추가한 데이터를 반환하고, 내부 배열에서 삭제한다.
- Peek() : 다음에 처리할 데이터를 반환한다.
- Clear() : 배열 내의 모든 데이터를 삭제한다.
큐의 경우에는 스택보다 구현 방법이 조금 더 복잡하다. 구조 상으로 효율성을 위해 Head와 Tail 두 가지 변수가 필요하다는 특징이 있기 때문이다.
- Head : Dequeue할 데이터를 가리켜야 하는 변수
- Tail : Enqueue할 공간을 가리켜야 하는 변수
이와 같은 점을 유념하여 아래와 같이 Queue를 구현해 보았다.
public class MyQueue<T>
{
private const int DefaultCapacity = 4;
private T[] array;
private int head;
private int tail;
private int count;
public MyQueue()
{
array = new T[DefaultCapacity];
head = 0;
tail = 0;
}
public void Enqueue(T item)
{
if (IsFull())
{
Grow();
}
array[tail] = item;
count++;
MoveNext(ref tail);
}
public T Dequeue()
{
if (IsEmpty())
throw new InvalidOperationException();
T result = array[head];
Array.Clear(array, head, 1);
count--;
MoveNext(ref head);
return result;
}
public T Peek()
{
if (IsEmpty())
throw new InvalidOperationException();
return array[head];
}
public void Clear()
{
array = new T[DefaultCapacity];
head = 0;
tail = 0;
}
private void Grow()
{
int newCapacity = array.Length * 2;
T[] newArray = new T[newCapacity];
if (head < tail)
{
Array.Copy(array, head, newArray, 0, tail);
}
else
{
Array.Copy(array, head, newArray, 0, array.Length - head);
Array.Copy(array, 0, newArray, array.Length - head, tail);
}
array = newArray;
tail = count;
head = 0;
}
private bool IsFull()
{
if (head > tail)
{
return head == tail + 1;
}
else
{
return head == 0 && tail == array.Length - 1;
}
}
private bool IsEmpty()
{
return head == tail;
}
private void MoveNext(ref int index)
{
index = (index + 1) % array.Length;
}
}특히나 구현할 때 상당히 어려웠던 부분이 Enqueue 부분이지 않았을까 싶다. 배열을 늘리는 방법은 스택에서 가져올 수 있었지만, tail을 이동시키는 방법에 대해 고민이 필요했다.
본래라면 tail을 맨 끝까지 이동하고, 맨 앞칸부터 비어있을 경우 다시 이동시킬 방법을 강구해야 했다. 하지만, 배열의 크기를 늘리는 과정에서 앞의 빈 칸 부분을 삭제하고 복사하는 방식으로 이를 해결했다.
