알고리즘 - (3) stack/queue
1. Stack
1.1. 개요
- 스택은 어느순간 숨쉬듯이 쓴다.

<후하후하>
- 순서대로 뽑아낸다의 느낌이다.
- 명칭상 LIFO 구조를 띈다(Last In First Out).

<LIFO는 늦게왔으니 그러니 퇴근도 일찍 하겠습니다..총총>
1.2. 내용
- 코드 상에서는 다음과 같다.

- 제네릭 컬랙션을 지원한다.
- 자주 쓰는 것들은 정해져있는데 Push, Pop이 가장 흔하게 사용되고 간혹 맨 위에 Peek을 통해 알아본다. (앞서 연결 리스트에서 사용했던 Count, Clear, Contains도 내장은 되어 있음)
- 실제로 써보면

- 여기서 가장 먼저 추가된 것은 5이고 마지막은 35인데 이 상황에서

- 스택에서 데이터를 뽑아서 출력한다는 것인데



- 이런 식으로 된다.
- 그런데 비스무리하게 직접 구현해본 적이 있었는데 그게 Object Pool이었다.
- 당시 배열 하나를 추가하고 마지막에 추가되게끔 하는 것이 있었는데 그게 스택이었다.
- List처럼 내부적 배열이 돌아가는 것이다.
- Pop과 Peek의 차이점이라면 Pop만 반복하면


- 터진다.
- Pop은 스택에서 하나씩 제거하면서 뽑아왔지만 Peek의 경우는


- 맨 위에 뭐가 있는지만을 확인했다.
1.3. 내부 메커니즘
- 내부에서 배열로 관리가 되는데 Capacity, Count와 같이 돌아간다.
- 특성상 맨 뒤만 추가되고 Pop이면 맨 뒤에 있는 것이 빠져나옴.

2. Queue
2.1. 개요
- 들어간 순서대로 빠져나가야 한다.

<꽉꽉 막힌 큐를 보니 내 개인 프로젝트가 생각나는구나..>
- 내부적으론 배열로 관리
- 구현이 좀 흥미로움.
- 식당이나 온라인 게임 구현할 때, 서버가 포화 상태가 되면 접속 대기를 거는데 Queue에다가 순서대로 걸어둔다.

<띱! 내가 먼저함 ㅅㄱ>
- 큐를 쓰면 Scene에서 Awake 타이밍을 잡는 것인데 순서가 꼬여 Null Reference가 뜨는데 Queue를 통해 관리를 하게 하고 초기화 기능이 있는 인터페이스 선언 후, 들고 있다가 Queue에 돌리면서 해도 된다.
- 물론 엔진에서 우선순위를 걸어준다거나 할 수 있다.
- 큐에다가 엑션을 담아 절차적 수행이 가능하도록 사용할 수도 있다.
- 대기열 자체, 순차적 처리가 필요할 때 쓸 수 있는 자료구조이다.
- 그래서 Queue의 경우 FIFO로 Stack과 반대되는 개념(First In First Out).

<아 자리라고 ㅋㅋ>
2.2. 사용
- 소스 코드에서 바로 보도록 하자.

- 큐에서는 로그를 작성해보면


- 추가한 순서대로 뽑혀져 나온다.
- 가장 많이 쓰는 것은 Enqueue, Dequeue, Peek.
2.3. 내부 메커니즘
- C# 제네릭 컬랙션은 내부적으로 흥미롭게 구현되어 있다.
- 최초의 데이터가 추가가 되었다고 가정을 한다.

- 여기서 Dequeue를 하면 맨 앞이 뽑힌다.

- 빈공간인데 데이터 추가를 하다가 이런 상황일 때

- 보통의 경우 재할당을 하고 복사가 일어난다.

- 리스트와 스택의 구동은 이랬었다.
- 남은 빈 공간을 써도 될 것 같다가 시발점이다.
- 추가 제거가 많은 상황에 사용이 될 것이다.
- 이 상황에서 재할당은 빈공간이 아깝게 버려질 수 있다고 생각했다.
- 그래서 C#에서는 원형으로 구현하였다.

- 배열은 일렬이라고 생각했었는데 원형 구조는 2가지 개념이 추가가 되면 가능하다.

- 배열에서 int형으로 관리가 되다 보니 현재 머리와 꼬리의 index를 미리 기억해두는 형식이라면

- 데이터가 추가되었을 때 Head index를 기준으로 추가가 된다.

- 만일 데이터가 Dequeue가 되면 tail을 당겨준다가 되고

- head의 경우 추가할 것에 대한 index인데 배열 크기에 도달하면 다시 앞으로 돌아가서 데이터 추가할 수 있고의 느낌

- 이 곳에서 데이터를 추가하고 싶을 때는 index 번호가 동일하면 재할당이 일어난다.
- 그래서 원형의 형태가 된다는 의미이다.
- 코드상에서도 구현해볼 때 2개의 index만 잘 관리하면 된다.
- 큐는 생각보다 쓸 일이 많으며 몬스터의 경우도 움직일 때 특정 위치에 도달하면 순차적 처리스타크래프트 유닛 생산 등이 Queue의 예시라고 생각하면 좋을 것 같다.

<큐 그 자체인 스타...>
- 원하는 타입을 키 값으로 쓰고 등록하는 형식




