스택 vs 큐

스택

 

스택은 후입선출(LIFO : Last In First Out)구조를 가지고 있어 나중에 들어온 요소가 먼저 나간다는 특성을 가지고 있다. 스택 자료구조는 특정한 곳에서 사용되는데 문서의 History 기록과 웹사이트의 방문 기록 같은 이전에 작업하던 요소로 되돌아가고 싶을 때 사용하며, 프로그램에서 함수의 호출 스택 같은 개념도 나중에 들어온 함수가 먼저 작업되고 빠져 나가는 방식, 또는 게임에서의 PopupUI, Object Pool 에 이용될 수 있다.

 

스택의 구현 원리

 

스택의 구현 원리는 배열 방식 즉 리스트 방식으로 구현되는데, C#에서는 리스트를 그대로 사용하여 어댑터 방식을 사용할 수 있다. 

 

스택에 요소를 추가하는 Push 함수는 리스트의 Add 함수를 사용할 수 있으며, 스택의 맨 위 요소를 반환하고 삭제하는 Pop 함수는 List의 Remove 함수를 사용하여 맨 마지막 요소를 반환하고, 그 요소를 삭제하는 방식을 사용할 수 있고, Peek 함수도 맨마지막에 위치한 요소를 반환하기만 하면 되므로 List를 이용하여 편리하게 구현할 수 있다. 따라서 Stack의 시간복잡도는 List와 동일하다.

이러한 어댑터 방식을 사용하는 이유는 기존에 만들어 놓았던 함수와 코드를 사용해 코드의 재사용성과 가독성을 높여 효율적으로 구현할 수 있다.

 

 

큐

 

큐는 선입선출(FIFO : First In First Out)구조를 가지고 있어 먼저 들어온 요소가 먼저 나간다는 특성을 가지고 있다. 큐 자료 구조도 특정한 곳에서 사용될 수 있는데 문서 프린트에서 먼저 들어온 문서가 먼저 출력되어야 하는 상황과 메시지 큐 같은 문자열 버퍼에서 먼저 입력된 문자를 먼저 처리하는 곳에 사용될 수 있겠다.

 

큐의 구현 원리

 

큐의 구현 원리는 원형배열 방식과, LinkedList을 사용할 수 있는데, LinkedList를 사용하여 스택과 마찬가지로 어댑터 방식을 사용하면 쉽게 구현 할 수 있지만, C#에서는 노드의 삭제의 빈번한 발생에 있어 가비지 콜렉터(GC)의 호출이 자주 될 수 있으므로 내부적으로 순환 배열을 사용하고 있다.

 

( 큐(Queue)와 덱(Deque) - 7장 (tistory.com) 참고)

 

# 일반적인 배열로만 구현 했을때

 

1. 데이터가 들어갈(enqueue) 인덱스값을 기억할 rear변수.

2. 데이터를 뽑아(dequeue)올 인덱스값을 기억할 front변수.

 

 

실제로 배열에 있는값이 사라지지 않는다는것은 알것이다.

 

처음 FR이 0번째 인덱스를 가리킬때 데이터가 들어오면 R이 가리키는 인덱스에 요소를 집어넣고

한칸 오른쪽으로 옮긴다. 

그리고 데이터를 뽑아올땐 F가 가리키는 인덱스에 요소를 빼오고 한칸 오른쪽으로 옮긴다.

 

이것이 배열기반 큐의 구조.

 

하지만 이렇게 단순히 끝낼수는 없는게 

위의 그림과 같이 분명히 배열에 데이터를 저장할 공간이 남아있지만 다음 데이터를 저장할려고하니 막혀서 삽입이 불가능한 상황인것.

이 때 배열기반 큐는 원형(환형)큐로 구현한다.

 

# 원형 배열로 구현 했을때

 

즉 이름에서도 알 수 있듯이 배열을 둥근형태. 원형의 형태라고 생각하고 F와 R을 움직이자는 것.

 

끝은 아니다.

일반적으로 생각했을땐 F와 R을 통해 환형큐의 가득찬(Full)상태와 빈(Empty)상태를 구분하기는 어렵다.

 

이에 대한 해결책으로 배열의 길이가 N이라면 데이터가 N - 1개가 채워졌을 때, 이를 꽉찬 것으로 간주한다.

 

 

환형 큐의 구현은 데이터를 집어넣고 R을 움직이고, 데이터를 반환하고 F를 움직이는게 아니다.

 

"enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음, R이 가리키는 위치에 데이터를 저장"

"dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음, F가 가리키는 위치에 데이터를 반환"

 

 

이렇게. 우리는 원형 큐의 상태를 이렇게 나타낸다.

 

1. 원형 큐가 텅빈상태 - F와 R이 동일한 위치를 가리킨다

2. 원형 큐가 꽉찬상태 - R이 가리키는 위치의 앞이 F가 가리킨다.

 

※ 정리

큐는 Front와 Rear라는 개념을 가져 Front와 Rear은 같은 위치에서 시작한다. 삽입 시 Rear이 가리키는 위치를 한 칸 이동시킨 다음, 가리키는 위치에 데이터를 저장하며 삭제 시 Front 가 가리키는 위치를 한 칸 이동시킨 다음, 가리키는 위치에 데이터를 반환하는 구조를 가진다.

근데 여기서 문제가 생기는데 Front와 Rear이 만나는 곳이 배열이 전부 비어있는지. 꽉 차있는지 구분할 수 없는 문제가 생기는데 이때 순환배열은 사용하지 않는 배열을 만들고 Rear이 Front 보다 앞에있을 때 다음 위치에 채워질 경우 꽉 찼다고 '판정' 하는 형식으로 구현되어있다.