04. 스택(Stack)

스택은 말그대로 "쌓이다"라는 개념을 가져가면 좋을것이다. 어떤 물건이 하나씩 쌓이게 되면 꺼낼때도 맨위에서부터 차례로 꺼내는 것이 정석일 것이다. 이러한 과정을 나중에 들어온것이 먼저 꺼내진다고 하여 후입 선출(Last In First Out) LIFO 라고 불린다.
우리는 상상해보면 맨위에서 모든 일이 다 일어남을 알 수 있다. 물건을 쌓을때 중간에 쌓지는 않지 않은가?
스택이 이렇다. 따라서 스택의 모든연산은 스택의 맨 위 공간을 의미하는 stack top에서만 일어난다.
이때 하나도 쌓이지 않은 상태를 공백 스택(Empty Stack)이라고 하고 이때는 stack top이 -1을 가리킨다.
다음과 같은 상황이다.

우리는 C언어 함수호출에서 스택이 쌓임을 알 수 있다. 먼저 맨 처음에는 main()함수가 stack위에 올라갈 것이다. 그 이후 어떤 함수를 호출하여 stack위에 올라가고 호출한 함수에서 또 다른 함수가 호출돼서 Stack에 올라갈 것이다. 하지만 Return은 어떻게 진행이 되는가? 마지막에 호출된 함수부터 return이 진행이 된다.

스택에는 두가지 기본연산이 있다. 하나는 삭제연산으로 pop연산이 있고 다른하나는 삽입연산으로 push연산이 있다. push pop의 ADT를 한번 보자.

push(s,item)::=
	if( is_full(s) ) return ERROR_STACKFULL;
    else 스택의 맨 위에 item을 추가한다

pop(s)::=
	if( is_empty(s) ) return ERROR_STACKEMPTY;
    else 스택의 맨 위의 원소를 제거해서 반환한다.

이번엔 push pop의 pseudo code를 보자

push(s, x):

if is_full(s)
	then error "overflow"
    else top<-top+1
    	stack[top]<-x
        

Caution
top을 하나 먼저 증가시킨후 값을 대입한다

pop(s,x):
if is_empty(s):
	then error "underflow"
    else e<-stack[top]
    	 top<-top-1
    return e

Caution
top을 감소시키기 전에 값을 뺀 이후 top을 감소시킨다.

하나더 참고로 알아야할 사항은 pop연산은 데이터를 완전히 제거하는 것이고 peek(s)연산도 있는데 이는 데이터를 제거하지 않고 반환만 하는 연산이다.

우리는 스택을 배열, 구조체, 동적할당으로 만든 동적배열 스택을 알아볼 것이다.
배열을 사용한 동적배열 스택

#include <stdio.h>
#include <stdlib.h> 

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
typedef int element;		// 데이터의 자료형
element stack[MAX_STACK_SIZE]; // 1차원 배열
int top = -1;			

// 공백 상태 검출 함수
int is_empty()
{
	return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
	return (top == (MAX_STACK_SIZE - 1));
}
//위의 두함수는 비교연산자로 True or False를 반환한다.

// 삽입 함수
void push(element item)
{
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
	//stack의 index를 하나 증가시키고 값을 대입한다.
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--]; 
	//반환하고 index를 내림으로써 값이 삭제된 효과를 낸다.
}
// 피크 함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
	//index를 내리지 않음으로써 삭제된 효과는 내지 못한다.
}
//element는 int형으로써 보면 된다.

int main(void)
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	//1,2,3을 삽입하고 1,2,3을 받는다.
	return 0;
}

만약 여기서 그저 숫자를 넣는것이 아닌 어떤 구조를 넣는다고 가정을 해보자. 그렇다면 구조체 배열을 사용해서 이를 처리할 수 있다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100


typedef struct {
	int student_no;
	char name[MAX_STRING];
	char address[MAX_STRING];
} element;
element  stack[MAX_STACK_SIZE]; //구조체를 저장할 수 있는 배열
int  top = -1;

// 공백 상태 검출 함수
int is_empty()
{
	return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
	return (top == (MAX_STACK_SIZE - 1));
}
//위의 두함수는 비교연산자로 True or False를 반환한다.

// 삽입 함수
void push(element item)
{
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
	//stack의 index를 하나 증가시키고 값을 대입한다.
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--]; 
	//반환하고 index를 내림으로써 값이 삭제된 효과를 낸다.
}
// 피크 함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
	//index를 내리지 않음으로써 삭제된 효과는 내지 못한다.
}
//element는 int형으로써 보면 된다.
int main(void)
{
	element ie = { 	20190001,
			"Hong",
			"Soeul"	};
	element oe;

	push(ie);
	oe = pop();

	printf("학번: %d\n", oe.student_no);
	printf("이름: %s\n", oe.name);
	printf("주소: %s\n", oe.address);
	return 0;
}

우리는 여태까지 전역변수로써 하나의 배열을 생성하고 그 배열을 가지고 pop도 해보고 push도 해보고 이런저런 연산을 진행해봤다 하지만 이는 전역변수 이기에 하나의 프로그램에서 여러개의 stack을 만들어 사용할 수 없다. 따라서 우리는 구조체안에 배열과 top을 넣어서 우리가 원할때마다 배열을 생성하는 상황을 상상할 수 있다. 코드를 보면서 이해해보자.

#include <stdio.h>
#include <stdlib.h>

// 차후에 스택이 필요하면 여기만 복사하여 붙인다. 
// ===== 스택 코드의 시작 ===== 
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE]; //stack으로 사용할 배열생성
	int top; //위 스택의 top위치로 사용할 변수
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s)
{
	s->top = -1; //StackType형 변수의 top에 -1을 대입함
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1); 
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item) //int형 item
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item; 
	//StackType형 구조체의 top변수를 참조해서 top을 하나 증가시킨후 
	//StackType형 구조체의 스택의 index로써 넣어서 item을 대입해준다.
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
	//StackType형 구조체의 top변수를 참조해서 data의 index로 사용해 
	//스택의 값을 하나취한후 top변수를 하나 감소 시켜준다
}
// 피크함수
element peek(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}
// 데이터를 참조하기만 한다
// ===== 스택 코드의 끝 ===== 


int main(void)
{
	StackType s;

	init_stack(&s); //포인터변수를 사용했기 때문에 변수의 주소를 넣어줘야한다.
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
}

위의 코드가 복잡해지는 이유는 C언어에서 함수 매개변수 전달 방식이 기본적으로 값 전달 방식(call by value)이기 때문이다. 즉 구조체 자체를 함수의 매개변수로 전달할 경우 구조체의 복사본이 전달되서 원본에는 아무영향을 미치지 못한다. 따라서 우리는 원본에 대한 변화를 주고싶어서 주소를 직접전달하는 포인터를 사용하는 것이다. 이걸 꼭 구조체로 생각할 필요 없고 매개변수로 정수를 전달한다고 생각해보자

파이썬도 call by value 방식이다

우리는 여태껏 구조체 배열을 사용했다.
하지만 배열을 생각해보자. 배열은 크기가 지정되면 크기를 실시간으로 바꿀수가 없다. 하지만 동적할당을 이용하면 크기를 실시간으로 지정받을 수 있다.

참고: 하지만 가변길이 배열이 비표준으로써 존재하긴한다.
https://int-i.github.io/cpp/2020-05-10/vla/

잠시 realloc의 사용법을 알아보자
realloc(포인터변수, 재할당Size) 이와 같이 사용하고, 다음과 같은 특성이 있다.
1. 동적할당된 메모리 크기를 변경해 재할당함 (기존 주소일수도 있고, 새로운 주소일 수도 있음)
2. (새로운 주소에 할당한 경우) 기존 주소에 있던 값을 새로운 주소에 복사하고 원래 주소는 할당해제함
realloc 사용 시 주의할 것은 기존에 할당된 메모리를 가리키는 포인터에 바로 realloc 리턴값을 대입하면 안된다는 것. NULL 반환시 기존에 할당된 메모리에 접근할 방법이 없어지기 때문이다.
->
realloc은 size가 0이거나 size바이트만큼 할당할 수 없다면 ptr은 그대로 살려둔채로 NULL을 반환한다.
보통 realloc을 다음과 같이 사용하는데, 이 경우 기존 ptr이 사라지면서 힙 영역에 할당된 메모리 주소를 잃어버리게 된다. 따라서 메모리 누수가 발생한다. 즉 다음 코드에서 realloc에 실패하면 buffer는 기존 주소를 잃어버리게 된다. 따라서 기존 주소를 백업해두는 루틴이 필요하다.

void ReallocExample()
{
   char* buffer = (char*)malloc(4);
   buffer = (char*)realloc(buffer, 8); //NULL반환시 malloc으로 할당된 데이터 주소를 잃어버린다.
}

[출처] https://woo-dev.tistory.com/124

이제 동적할당을 통해 스택을 구현한 코드를 살펴보자

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element *data;		// data은 포인터로 정의된다. 
	int capacity;		// 현재 크기
	int top;
} StackType;

// 스택 생성 함수
void init_stack(StackType *s)
{
	s->top = -1;
	s->capacity = 1;
	s->data = (element *)malloc(s->capacity * sizeof(element));
	//처음에는 4바이트의 메모리 공간이 할당된다.
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType *s, element item)
{
	if (is_full(s)) {
		s->capacity *= 2;
		s->data =
			(element *)realloc(s->data, s->capacity * sizeof(element)); 
			// 기존의 데이터에 새로운 size의 메모리를 재할당 한다.
			// 동적할당을 사용하는 이유라고 볼 수 있다.
	}
	s->data[++(s->top)] = item; //int형 item을 저장한다.
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
int main(void)
{
	StackType s;
	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d \n", pop(&s));
	printf("%d \n", pop(&s));
	printf("%d \n", pop(&s));
	free(s.data); //결국 하나의 메모리공간을 설정한것이므로 해제도 하나만 해주면 된다.
	return 0;
}

이제 스택을 응용하는 문제를 다뤄보자.

• 괄호 검사 문제
• 후위표기식 계산
• 미로문제

괄호 검사 문제
프로그램에서는 여러 가지 종류(,[,{,},],)의 괄호들이 사용되는데 이들은 규칙에 맞게 사용돼야 한다
1. 왼쪽 괄호와 오른쪽 괄호의 개수가 같다.
-> 즉, (의 개수와 )의 개수가 같아야 한다.
2. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
-> (이 )보다 먼저 나와야 한다.
3. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안된다.
-> 서로를 포함하는 관계여야 한다는 말로 ( [ ) ] 와 같은 것이 안된다

2번은 너무나 당연한 것이므로 1,3번을 한마디로 정리하자면
짝이 맞는 괄호들이 서로를 포함하는 관계가 되어야 한다 로 정리할 수 있겠다.

검사 알고리즘의 pseudo code를 확인해 보겠다.

check_matching(expr)

while (입력 expr의 끝이 아니면)
ch<-expr의 다음 글자
switch(ch)
	case '(': case '[': case'{':
    	ch를 스택에 삽입
        break 
        // 위와 같이 쓸 수 있는 이유는 
        // switch~case문은 조건에 안맞으면 통과시키는데 조건이 맞으면 그 조건아래에 있는 조건들은 따져
        //보지 않고 모두 실행을 시키기 때문에 (,[,{중 하나가 존재한다면 무조건 아래에 구문을 실행시킨다.
        // 그후 break를 만나 빠져나가게 된다.
    case ')': case ']': case '}':
    	if( 스택이 비어 있으면 )
        	then 오류
            else 스택에서 open_ch를 꺼낸다
            	if (ch와 open_ch가 같은 짝이 아니면)
                	then 오류 보고
   		break
if( 스택이 비어 있지 않으면 )
	then 오류
   

검사 알고리즘의 C code를 확인해보겠다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef char element;		// 교체!
							// 차후에 스택이 필요하면 여기만 복사하여 붙인다. 
							// ===== 스택 코드의 시작 ===== 
#define MAX_STACK_SIZE 100


typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
...
// ===== 스택 코드의 끝 ===== 
int check_matching(const char *in) //프로그래머가 바꾸지못하도록 함
{
	StackType s;
	char ch, open_ch;
	int i, n = strlen(in);  	// n= 문자열의 길이
	//printf("%c",*in);			
	// out:h -> in은 문자열의 시작 주소 즉 { 을 가리키고 있다.
	// in은 문자열의 시작 주소를 가리키고 있기 때문에 in+1을 할경우에는 { 다음 문자를 가리킬 것이다.

	init_stack(&s);			// 스택의 초기화

	for (i = 0; i < n; i++) {
		ch = in[i];		// ch = 다음 문자
		switch (ch) {
		case '(':   case '[':    case '{':
			push(&s, ch);
			break;
		case ')':   case ']':    case '}':
			if (is_empty(&s))  return 0; // stack이 비어있으면 오류
			else {
				open_ch = pop(&s); // stack의 top에 있는 item을 받아옴 "여는 괄호" 를 의미하는 open_ch
				if ((open_ch == '(' && ch != ')') || 
					(open_ch == '[' && ch != ']') ||
					(open_ch == '{' && ch != '}')) {
					// 여는괄호가 아닌 다른 숫자나 문자면 통과
					// 여는괄호일 경우에는 문자열에서 받아온 문자가 여는 괄호와 짝을 이루면 통과 아니면 실패
					return 0; 
				}
				break;
			}
		}
	}
	if (!is_empty(&s)) return 0; // 스택에 남아있으면 오류
	return 1;
}

int main(void)
{
	char *p = "{ A[(i+1)]=0; }";
	// printf("%s",p);         
	// out은 위에 String이 나오게 된다.
	// 이것이 어색하지 않은 이유는 잘 생각해보면 우리는 
	// char a[10] = "ABC";
	// printf("%s",a);
	// 위와 같이 printf를 통해 String을 출력하고는 한다
	// 이때 a는 배열의시작 주소를 의미하고
	// 맨위의 p는 문자열의 시작 주소를 의미한다. 따라서 자연스럽게 출력이 가능한 것이다.
	// 위에 포인터로 상수형 문자열을 선언한 경우는 상수형 문자열이기 때문에 접근을 통한 삭제가 불가능하다
	//포인터로 문자열 선언
	if (check_matching(p) == 1)
		printf("%s 괄호검사성공\n", p);
	else
		printf("%s 괄호검사실패\n", p);
	return 0;
}

후위 표기식 계산
우리는 너무나 당연하게도 컴퓨터로 계산을 진행해왔다. 하지만 인간이 표기하는 수식과 컴퓨터가 표기하는 수식은 상이하다. 컴파일러는 스택을 사용해서 수식을 계산하는데, 먼저 수식을 표기하는 종류에 대해 언급하겠다.
수식은 중위 표기법 후위 표기법 전위 표기법 3가지의 방법이 있는데, 연산자가 피연산자 사이에 있으면 중위, 연산자가 피연산잔 뒤에 있으면 후위이고 연산자가 피연산자 앞에 있으면 전위라고 한다.

인간은 중위표기법으로 수식을 표기하지만 컴퓨터는 후위 표기법으로 수식을 표기한다.
전위 표기법은 2+3*4이고 이를 후위 표기법으로 고치면 234*+가 된다.

먼저 후위표기식을 계산하는 방법을 알아보겠다.

후위 표기식을 왼쪽에서 오른쪽으로 따라가면서 피연산자(숫자)의 경우에는 스택에 담아두고 연산자가 나올경우 스택에서 2개를 빼서 계산을 한후 다시 넣어준다. 위 그림은 이를 설명한다.

이제 중위 표기식을 후위 표기식으로 고치는 방법부터 알아보겠다. 즉, 우리가 적은 수식을 컴퓨터가 이해할 수 있게 고쳐보고 싶은 것이다.
우리는 위에 후위표기식을 계산하는 것과 비슷한 논리로 이를 해결할 수 있다. 이번엔 반대로 연산자를 스택에 담아두는 것이다. 그리고 피연산자가 나오게 되면 그대로 써준다. 예를 들어서 a+b*c가 있다고 해보자 이를 후위표기법으로 고치면 abc*+가 될 것이고 이를 다시 위에서 언급한 후위표기식을 계산하는 방식으로 계산을 진행하면 b*c+a가 될것이다.

하지만 여기서 문제는 연산자들의 우선순위이다.
예를 들어서 위의 식을 살짝 바꾼 a*b+c를 생각해보자 이를 위에서 말한 후위표기식으로 바꾼다면 abc+*가 될것이고 이를 다시 풀면 b+c*a가 될 것이다. 따라서 원래의 식에서 값이 바뀌게 된다.

우리는 연산자의 우선순위를 고려해줌으로써 이문제를 해결할 것이다.

연산자의 우선순위를 고려하기 위해서 몇가지 규칙을 설정하겠다. 예시를 통해 확인해보자
Ex>
우리는 위에서 든 예시인 ab+c를 생각해보자.
1. a는 피연산자 이므로 후위표기식에 그대로 쓰인다.
2. 은 연산자 이므로 스택에 쌓인다.
3. b는 피연산자 이므로 후위표기식에 그대로 쓰인다.
4. +는 연산자이지만 스택안에있는 모든 연산자와 비교해서 +보다 연산자 우선순위가 높은 것들은 출력해주고 스택에 집어넣는다.
5. c는 피연산자이므로 후위표기식에 그대로 쓰인다.
6. 식이 끝났으므로 스택안에있는 연산자들을 써준다.

이제 좀더 복잡한 식을 가지고 해보자

2*3+4/5-3을 그림을 그려가며 바꿔보겠다

추가규칙 1

• -의 연산자 우선순위는 +와 같다. 하지만 연산자 우선순위가 높거나 같은 경우 스택에서 pop을 해서 후위표기식에 추가시켜준다

다음에는 괄호가 나오는 예시를 살펴보자

추가규칙2
우리는 왼쪽 괄호를 제일 우선순위가 낮은 연산자로 생각한다.
또한 오른쪽 괄호를 만나게 되면 왼쪽괄호가 삭제될 때까지 왼쪽괄호위에 쌓여있는 모든 연산자를 출력한다

• 이때 괄호는 후위 표기 수식에 적지 않는데 이것이 후위 표기 수식의 장점으로써 작용한다.

미로 탐색 문제
미로 문제(maze solving problem)이란 미로에 갇힌 생쥐가 출구를 찾는 문제이다.
생쥐는 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽(거꾸로 4)의 순서로 스택에 저장하고 스택에서 맨위의 위치를 꺼내어 현재의 위치로 하고 같은 작업을 반복한다. 이러한 반복은 현재의 위치가 출구와 같거나 모든 위치를 다 검사해 볼때까지 계속된다. 한번 거쳐간 위치를 다시 검사하지 않도록 이미 검사한 위치는 표시를 하여 무한 루프에 빠지지 않게 한다.
이때, 순서는 우리가 정할 수 있다.

미로 탐색 프로그램의 Pseudo Code를 작성해 보겠다.

maze_search():

스택 s와 출구의 위치 x, 현재 생쥐의 위치를 초기화
while( 현재의 위치가 출구가 아니면 ) do
	현재위치를 방문한 것으로 표기
    if( 현재위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고 갈수 있으면)
    	then 그 위치들을 스택에 push
    if( is_empty(s) ) 
    	then 실패
    else 스택에서 하나의 위치를 꺼내어 현재 위치로 만든다;
성공;

우리는 C언어로 미로 탐색 프로그램을 짜기전에 몇가지 약속을 해두어야 한다. 미로는 2차원 배열로 미리 입력돼있고, 생쥐의 위치는 (행,열)의 좌표값으로 표시한다 또한 방문이 끝난 위치는 . 으로 바꾸어 다른 위치들과 구별시킨다. 만약 스택이 비어있는데도 출구를 찾지 못했다면 미로 탐색은 실패했음을 출력하고 프로그램을 끝낸다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6

typedef struct {		// 교체!
	short r;
	short c;
} element;

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s)
{
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 

// element는 구조체로써 row와 column이 저장돼있다.
element here = { 1,0 }, entry = { 1,0 };
//현재 위치와 입구의 위치
char maze[MAZE_SIZE][MAZE_SIZE] = {
	{ '1', '1', '1', '1', '1', '1' },
{ 'e', '0', '1', '0', '0', '1' },
{ '1', '0', '0', '0', '1', '1' },
{ '1', '0', '1', '0', '1', '1' },
{ '1', '0', '1', '0', '0', 'x' },
{ '1', '1', '1', '1', '1', '1' },
};
// 미로를 미리 선언 
// e가 입구
// 위치를 스택에 삽입
void push_loc(StackType *s, int r, int c)
{
	if (r < 0 || c < 0) return;
	// 존재하지 않는 곳이므로 return
	if (maze[r][c] != '1' && maze[r][c] != '.') {
		// 왔던곳이 아니고 장애물로 가로막혀져 있지 않는다면
		element tmp; 
		tmp.r = r;
		tmp.c = c;
		// 이위치를 기억해서
		push(s, tmp);
		// 스택에 올림
	}
}
// 미로를 화면에 출력한다. 
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE])
{
	printf("\n");
	for (int r = 0; r < MAZE_SIZE; r++) {
		for (int c = 0; c < MAZE_SIZE; c++) {
			printf("%c", maze[r][c]);
		}
		printf("\n");
	}
}

int main(void)
{
	int r, c; // 행과 열로 위치 파악
	StackType s;

	init_stack(&s);
	here = entry; //현재 위치는 entry
	while (maze[here.r][here.c] != 'x') {//도착하기전까지
		r = here.r;
		c = here.c;
		maze[r][c] = '.';
		maze_print(maze);
		push_loc(&s, r - 1, c); //위
		push_loc(&s, r + 1, c); //아래
		push_loc(&s, r, c - 1); //좌
		push_loc(&s, r, c + 1); //우
		if (is_empty(&s)) {
			printf("실패\n");
			return;
		} //스택이 비면 갈곳이 없으므로 실패
		else
			here = pop(&s); //현재위치는 stack에 최상단
	}
	printf("성공\n");
	return 0;
}