기억보단 기록을

이번에는 스택을 이용해 미로찾기 게임을 만들어보자.

이는 추후 그래프에서 깊이우선탐색과도 큰 연관이 있는데,

미로는 이와같이 주변 벽을 1, 갈수있는 통로를 0, 그리고 시작점을 (1,1)로 두는 미로로 주어진다.

원리는 이렇다

방향을 8등분하여 각각의 이동하는 좌표를 만들어준다. 우리는 N(북쪽방향)부터 시계방향으로 탐색할 것이다.

시작점해서 출발하면 일단 들린곳은 mark 하게 될것이다.

앞으로 시계방향으로 탐색하며, 0인 부분은 일단 들어가고 본다.

또한 들리자마자 mark하게 될텐데, 이는 mark하지않으면 이전 통로로 이동하는 무한반복 Loop에 빠지게 된다.

에를들어 위와같은 상태에서 direction이 3일때 통로가 발견되었으면, 

이렇게 그지점을 방문표시하고 방향까자 포함해 스택에 넣는다. (다음에 돌아왔을때 저장된 방향부터 다시 탐색하기 위함이다.)

이번에는 이전 큐의 단점을 보완한 원형큐를 구현하되

일정 할당량을 넘게되면 계속해서 새로운 할당을 받아 계속 add할 수 있게

하는 큐를 구현해보았다.

원형큐는 front  = rear 일때 완전히 비어있음을 의미하게 되고,

front = rear+1 이 되는 순간 꽉차있는 것을 의미한다. 

front와 rear사이에는 하나의 공간이 비어있게되는데, 이는 큐가 비어있음과 꽉차있음을 구분하기 위해서이다.

원형큐를 사용하다보면 윗그림과 같은 경우가 발생한다. 이때, 큐를 동적할당으로 capacity를 늘려주고, front와 rear를 newQueue 를 사용해 다시한번 정리하게 된다.

코드를보면 다 똑같은데 COPY부분이 이해하기 어렵다.

단순히 front와 rear를 정리하는것인데, 배열 시작점과 끝점을 인자값으로 줘야해서 헷갈린다.

스택(Stack) : 선입후출 혹은 후입선출 , LIFO 구조

시스템 스택에도 스택개념이 사용

스택구현

void printStack(); 스택출력
void stackFull();  스택이 가득차 더이상넣을수 없음을 알리고, 스택요소들을 출력후 종료
student stackEmpty(); 스택이 비어 뺄수없음을 알리고, 에러값 반환
void push(student item); 스택 push
student pop(); 스택 pop 하고 값 반환

큐(Queue) : 선입선출, FIFO 구조

os의 스케쥴링 및 그래프 탐색 알고리즘 등에 사용

void printQueue();
student queueEmpty();
void addq(student item);
student deleteq();
void queueFull(student item);

함수의 구성은 스택과 동일하다.

하지만 큐는 front와 rear가 존재함으로써 rear에 계속해서 데이터가 들어오게 되면 front 쪽에서 데이터가 빠진 자리는 

낭비되기 마련이다. 따라서 array shifting 을통해 큐가 정말꽉차지 않는 이상 계속해서 배열을 쓸수 있도록

하였다. 이러한 문제점을 원형큐를 통해 더 쉽게 해결할 수 있다.