기본적으로 두개다 실제로 존재하는 자료구조라기 보단 자료의 처리를 구분하기위한 '규칙'이다.
ADT(abstract data structure) 추상적 자료 구조 -> 자료구조의 방법이 코드로 정의된 것이 아니라, 구조의 행동 양식만 저장됨.
C#에서는 둘다 배열로 구현하고 배열위에 어떠한 규칙을 추가한 것이라고 생각하면 편함.
Stack
Stack이 무엇인가?
FILO(First-in-Last-out) / LIFO(Last-in-First-out)의 구조를 따르는 자료구조이다.
입력과 출력이 같은 곳을 사용하기에 Stack의 Top을 통한 접근이 가능하다.
자료를 넣는것을 Push / 빼는것을 Pop으로 사용함 / Peek또한 존재 빼지않고 확인만 함.
사용하는 곳, 이유, 목적?
가장 최신에 입력된 순서대로 처리해야 되는 경우에 사용이 가능함.
게임 내의 UI나 웹의 뒤로가기버튼 / 재귀호출 등에 사용가능함.
구현
private const int DefaultCapacity = 4;
private T[] array;
private int topIndex;
public Stack()
{
array = new T[DefaultCapacity];
topIndex = -1;
}
//프로퍼티 사용
public int Count {get { return top Index}}
//stack 비우기
public void Clear()
{
array = new T[DefaultCapacity];
topIndex = -1;
}
//top요소 확인
public T Peek()
{
if(IsEmpty())
throw new InvalidOperationException();
return array[topIndex];
}
public bool TryPeek(out T result)
{
if(IsEmpty())
{
result = default(T);
return false;
}
else
{
result = array[topIndex];
return true;
}
}
public T Pop()
{
if (IsEmpty())
throw new InvalidOperationException();
return array[topIndex--];
}
public bool TryPop(out T result)
{
if(IsEmpty())
{
result = default(T);
return false;
}
else
{
result = array[topIndex--];
return true;
}
}
public void Push(T item)
{
if(IsFull())
{
Grow();
}
array[++topIndex] =item;
}
// Stack이 꽉차있을때 추가할경우 배열의크기 키우고 복사.
public void Grow()
{
int newCapacity = array.Length*2;
T[] newArray = new T[newCapacity];
Array.Copy(array, 0, new Array, 0, Count);
array = newArray;
}
//비었는지 유무 확인
private bool IsEmpty()
{
return Count == 0;
}
//차있는지 유무 확인
private bool IsFull()
{
return Count == array.Lenghth;
}cf)Stack overflow / Stack underflow
스택이 가득차 넘치게 될 경우 Stack overflow가 발생하며
아무것도 들어가 있지 않은 스택에서 꺼낼려고 할 경우 Stack underflow가 발생하게 된다.
Queue
Queue는 무엇인가?
FIFO(First-in-First-out) / LILO(Last-in-Last-out)의 구조를 따르는 자료구조이다.
입구와 출구의 통로가 같지않다. 전위 후위의 존재가 필수.
자료를 넣는것을 Enqueue / 빼는것을 Dequeue로 사용함.
사용하는 곳/ 이유? 목적?
들어온 순서대로 작업을 처리해야 되는 경우에 사용이 가능하다. BFS에 사용이 용이함.
프로세스 관리나 대기열 순서등의 우선순위 예약에도 사용이 가능함.
구현
private const int DefaultCapacity = 4;
private T[] array;
public int head;
private int tail;
public Queue()
{
array = new T[DefaultCapacity];
head =0;
tail = 0;
}
public int Count()
{
get
{
if(head <= tail)
return tail = head;
else
return tail + (array.Length -head);
}
}
public void Clear()
{
array = new T[DefaultCapacity];
head = 0;
tail = 0;
}
public void Enqueue(T item)
{
if(IsFull())
{
Grow();
}
array[tail] = item;
MoveNext(ref tail);
}
public T Dequeue()
{
if(IsEmpty())
throw new InvalidOperationException();
T result = array[head];
MoveNext(ref head);
return result;
}
public bool TryDequeue(out T result)
{
if(IsEmpty())
{
result = default(T);
return false;
}
result = array[head];
return true;
}
public T Peek()
{
if(IsEmpty())
throw new InvalidOperationException();
return array[head];
}
public bool TryPeek(out T result)
{
if(IsEmpty())
{
result = default(T);
return false;
}
result = array[head];
return true;
}
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;
}
priavte bool IsFull()
{
if(head > tail)
{
return head == tail +1;
}
else
{
return head == 0 && tail == array.Length-1;
}
}
privat bool IsEmpty()
{
return head == tail;
}
private void MoveNext(ref int index)
{
index = (index == array.Length -1) ? 0 :index+1;
}
cf)
c#에서는 배열로 큐를 만들기에 큐의 앞공간이 빠져서 비었지만 뒤의 공간은 꽉차있는 경우에 앞공간에 저장하여 공간의 활용도를 높인다. 환형 배열 구조 사용함
또한 큐는 꽉차있는지 비어있는지에 대한 비교를 위해 마지막 하나의 배열공간을 비워놓고 head와 tail이 같을 경우 둘의 값이 같고 tail이 head 바로 전에 있을경우 큐가 꽉차있는 것으로 판별한다.
cf1)
기본적으로 둘다 C#의 Generic collection에 포함되어 있으며, IEnumerable을 상속받기에 foreach의 구문이 사용이 가능함.
reference
https://www.youtube.com/watch?v=Nk_dGScimz8
https://github.com/jungtaek6681/CSharp-Algorithm
