알고리즘 - (3) stack/queue

이형눈이이상해
이형눈이이상해
∙∙조회 4

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의 예시라고 생각하면 좋을 것 같다.

<큐 그 자체인 스타...>

  • 원하는 타입을 키 값으로 쓰고 등록하는 형식