[C언어로 쉽게 풀어쓴 자료구조] 4장 스택

C언어로 쉽게 풀어쓴 자료구조: 4장 스택

 

스택(Stack)이란?

데이터를 쌓아 올린 구조, 후입선출(LIFO, Last In First Out)

➡️ 뒤로가기, 쌓여있는 상자 

 

 

스택의 추상자료형(ADT)

create(size) = 최대 크기가 size인 공백 스택을 생성한다.

is_full(s) = 
    if(스택의 원소수 == size) return TRUE;
    else return FALSE;

is_empty(s) = 
    if(스택의 원소수 == 0) return TRUE;
    else return FALSE;
    
push(s, item) = 
    if( is_full(s) ) return ERROR_StackFull
    else 스택의 맨 위에 item을 추가한다.
    
pop(s) = 
    if( is_empty(s) ) return ERROR_StackEmpty;
    else 스택의 맨 위의 원소를 제거해서 반환한다.
    
peek(s) = 
    if( is_empty(s) ) return ERROR_StackEmpty;
    else 스택의 맨 위의 원소를 제거하지 않고 반환한다.

 

 

---

4.2 스택의 구현

스택의 요소를 구조체로 하기

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

 

 

스택에 저장되는 데이터를 구조체  정의

typedef int 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;
}

---

※ fprintf 함수, stderr 스트림

기능	printf	fprinf
기본 출력	표준 출력(일반적으로 화면)	표준 출력(stdout), 오류 스트림(stderr) 또는 파일 등 다양한 스트림을 지정할 수 있다
구문	printf("텍스트\n");	fprintf(stream, "text\n"); 여기서 stream은 stdout, stderr 또는 파일 포인터일 수 있다
오류 처리	항상 stdout으로 인쇄	더 나은 가시성과 일반 출력과의 분리를 위해 stderr에 오류 메시지를 보낼 수 있다
즉시 출력	버퍼링됨(인쇄하기 전에 기다릴 수 있음)	stderr(오류 스트림)은 버퍼링되지 않으므로 메시지가 즉시 표시된다
파일 출력	직접 파일 지원 없음	fprintf(file, "text\n");를 사용하여 파일에 직접 인쇄할 수 있다.
사용 사례 예시	일반 메시지, 표준 출력	오류 또는 경고(stderr), 파일에 기록, 별도의 스트림이 필요한 경우

라고 하네요..

 

---

삭제 함수

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];
}

 

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));
}

 

 

---

4.4 스택의 응용: 괄호 검사 문제

조건

1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
2. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
3. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안된다.

int check_matching(const char *in)
{
	StackType s;
	char ch, open_ch;
	int i, n = strlen(in);  	// n= 문자열의 길이
	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;
			else {
				open_ch = pop(&s);
				if ((open_ch == '(' && ch != ')') ||
					(open_ch == '[' && ch != ']') ||
					(open_ch == '{' && ch != '}')) {
					return 0;
				}
				break;
			}
		}
	}
	if (!is_empty(&s)) return 0; // 스택에 남아있으면 오류
	return 1;
}

 

 

---

후위 표기 수식 계산

int eval(char exp[])
{
	int op1, op2, value, i = 0;
	int len = strlen(exp);
	char ch;
	StackType s;

	init_stack(&s);
	for (i = 0; i<len; i++) {
		ch = exp[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
			value = ch - '0';	// 입력이 피연산자이면
			push(&s, value);
		}
		else {	//연산자이면 피연산자를 스택에서 제거
			op2 = pop(&s);
			op1 = pop(&s);
			switch (ch) { //연산을 수행하고 스택에 저장 
			case '+': push(&s, op1 + op2); break;
			case '-': push(&s, op1 - op2); break;
			case '*': push(&s, op1 * op2); break;
			case '/': push(&s, op1 / op2); break;
			}
		}
	}
	return pop(&s);
}

 

---

중위 표기 수식 ➡️ 후위 표기 수식

void infix_to_postfix(char exp[])
{
	int i = 0;
	char ch, top_op;
	int len = strlen(exp);
	StackType s;

	init_stack(&s);					// 스택 초기화 
	for (i = 0; i<len; i++) {
		ch = exp[i];
		switch (ch) {
		case '+': case '-': case '*': case '/': // 연산자
											// 스택에 있는 연산자의 우선순위가 더 크거나 같으면 출력
			while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
				printf("%c", pop(&s));
			push(&s, ch);
			break;
		case '(':	// 왼쪽 괄호
			push(&s, ch);
			break;
		case ')':	// 오른쪽 괄호
			top_op = pop(&s);
			// 왼쪽 괄호를 만날때까지 출력
			while (top_op != '(') {
				printf("%c", top_op);
				top_op = pop(&s);
			}
			break;
		default:		// 피연산자
			printf("%c", ch);
			break;
		}
	}
	while (!is_empty(&s))	// 스택에 저장된 연산자들 출력
		printf("%c", pop(&s));
}

 

 

※ ' ( ' 의 경우 ' ) '를 만나면 Pop

 

---

미로 찾기 문제

1. 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽의 순서로 스택에 저장
2. 스택에서 맨위의 위치를 꺼내어 현재의 위치로 한다음에, 같은 작업은 반복한다.
3. 현재의 위치가 출구와 같거나 모든 위치를 다 검사해 볼 때까지 계속 반복한다.

maze_search():

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

 

 

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' },
};
// 위치를 스택에 삽입
void push_loc(StackType *s, int r, int c)
{
	if (r < 0 || c < 0) 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;
	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);
	}
	printf("성공\n");
	return 0;
}