[자료구조] 스택 (stack)

 

스택이란?

Stack이라는게 뭘까요? 사전적 의미부터 살펴봅시다.

스택은 쌓다, 포개다 라는 의미를 가지고 있습니다. 말 그대로 데이터를 쌓아서 자료를 저장하는 구조입니다.

우리가 책을 위로 쌓아서 보관해놓았다고 생각해봅시다. 맨 밑에 있는 책을 꺼내기 위해선 어떻게 해야 할까요? 위에 있는 책들을 다 어딘가로 치운 다음 꺼내야 할 것입니다.

스택도 마찬가지입니다. 특정 데이터를 꺼내기 위해서는 위에 있는 데이터를 다 빼내야 합니다. 그래서 스택은 후입선출(LIFO; Last In First Out)의 특징을 가지고 있습니다.

 

 

스택 ADT

스택에 요소를 추가하거나 삭제하는 연산, 현재 스택 상태를 검사하는 연산들로 구성됩니다.

create(size) ::= 크기가 size인 스택 생성
is_full(s) ::= if(스택(s)의 원소 수 == size) return true; else return false;
is_empty(s) ::= if(s의 원소 수 == 0) return true; else return false;
push(s, item) ::= if(is_full(s)) return FULLSTACK_ERROR; else stack 맨 위에 item 추가
pop(s) ::= if(is_empty(s)) return EMPTY_ERROR; else stack 맨 위 item 제거 및 반환
top(s) ::= if(is_empty(s)) return EMPTY_ERROR; else stack 맨 위 반환

 

스택 구현

추상 자료형을 바탕으로 스택을 구현해봅시다.

 

스택 구조체

구조체를 이용해 스택의 구조를 지정해주면 됩니다. 예를 들어, 원소를 숫자로 하고 싶다면 element를 int형으로 지정해준 다음 stack 구조체를 생성해주면 됩니다.

#define MAX_STACK_SIZE 100

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

 

 

그렇지 않고 스택의 구조를 더 복잡하게 하고 싶다면 element를 구조체로 만들고 struct { } element; 안에 더 자세하게 구현해주면 됩니다.

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct {
	int sn;
	char name[MAX_STRING];
	char address[MAX_STRING];
} element;

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

 

 

is_empty(s)

스택의 구조체에는 top이라는 변수가 있습니다. top 변수는 가장 최근에 입력되었던 자료를 가리키는데, 이는 스택이 비어있는지 확인하는데 사용할 수 있습니다.

top이 $-1$이라면, 스택이 비어있는 것으로 간주하고 TRUE를 리턴해주면 됩니다.

int is_empty(Stack *s) {
    return s->top == -1;
}

 

is_full(s)

마찬가지로 이 함수에서도 top 변수를 이용해줍니다. top은 인덱스를 가리키고, $0$부터 시작하니 스택이 꽉 찼음은 top이 $size - 1$을 가리킬 때입니다.

int is_full(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

 

push(s)

스택에 원소를 삽입하기 전 스택이 가득 차있는지 검사를 먼저 해야 합니다. 바로 위에 짜 놓은 is_full(s) 함수를 이용하면 됩니다.

 

만약 가득 차지 않았다면,

1. 스택에 값을 포함한 원소를 넣습니다.
2. top을 1 올려줍니다.

void push(Stack *s, element item) {
	if(is_full(s)) {
		fprintf(stderr, "스택이 꽉 찼습니다.");
		return;
	}
	else s->data[++(s->top)] = item;
}

 

pop(s)

스택에 원소를 빼기 전 스택이 비어있는지 검사를 먼저 해야 합니다. 위에 짜 놓은 is_empty(s) 함수를 이용하면 됩니다.

 

만약 비어있지 않다면,

1. 스택에서 원소를 뺍니다.
2. top을 1 빼줍니다.
3. 빼낸 원소를 return 합니다.

element pop(Stack *s) {
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있습니다.");
        exit(1);
    }
    else return s->data[(s->top)--];
}

 

top(s)

top(s)는 원소를 빼지 않는다는 것만 제외하면 pop(s)와 유사한 매커니즘입니다. is_empty(s) 함수를 이용해줍니다.

 

만약 비어있지 않다면,

1. top을 가리키는 원소를 return 합니다.

element top(Stack *s) {
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있습니다.");
        exit(1);
    }
    else return s->data[s->top];
}

 

 

전체 코드는 아래와 같습니다.

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

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

// 스택이 비었는지 검사하는 함수
int is_empty(Stack *s) {
    return s->top == -1;
}

// 스택이 꽉 찼는지 검사하는 함수
int is_full(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

// 스택에 값을 넣는 함수
void push(Stack *s, element item) {
    if(is_full(s)) {
        fprintf(stderr, "스택이 꽉 찼습니다.");
        return;
    }
    else s->data[++(s->top)] = item;
}

// 스택에 값을 빼는 함수
element pop(Stack *s) {
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있습니다.");
        exit(1);
    }
    else return s->data[(s->top)--];
}

// 가장 위의 값을 뽑는 함수
element top(Stack *s) {
    if(is_empty(s)) {
        fprintf(stderr, "스택이 비어있습니다.");
        exit(1);
    }
    else return s->data[s->top];
}

 

동적 배열 스택

위의 코드에서는 #define을 통해 스택의 크기를 미리 결정해서 스택을 선언했습니다. 이를 컴파일 시간에 크기가 결정되었다고 하는데, C언어에서는 malloc() 함수를 호출해 실행 시간에 메모리를 할당할 수 있습니다. 이렇게 되면 동적으로 메모리를 필요할 때마다 늘릴 수 있게 되는 겁니다.

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

typedef int element;
typedef struct {
	element *data;
	int capacity; // 현재 크기
	int top;
} Stack;

// 스택 초기화
void init_stack(Stack *s) {
	s-> top = -1;
	s->capacity = 1;
	s->data = (element *)malloc(s->capacity * sizeof(element));
}

int is_empty(Stack *s) {
	return s->top == -1;
}

int is_full(Stack *s) {
	return s->top == s->capacity - 1;
}

void push(Stack *s, element item) {
	// 데이터가 가득 차있으면 기존 크기의 2배를 늘려 스택 메모리 재할당
	if(is_full(s)) {
		s->capacity *= 2;
		s->data = (element *)realloc(s->data, s->capacity(sizeof(element));
	}
	s->data[++(s->top)] = item;
}

element pop(Stack *s) {
	if(is_empty(s)) {
		fprintf(stderr, "스택이 비었습니다.");
		return;
	}
	else return s->data[(s->top)--];
}

int main() {
	Stack s;
	init_stack(&s);
    	for(int i = 1; i <= 5; i++) {
    		push(&s, i);
  	}
	for(int i = 1; i <= 5; i++) {
	    	printf("%d\n", pop(&s));
	}
	free(s.data);
}

 

표기법 변환

중위 표기법 → 전위 표기법

$(a+b)/c-d\times(a-b)$

$⇒ (((a+b)/c)-(d\times(a-b)))$ 연산자에 의해 계산이 이루어지는 범위마다 괄호를 쳐줍니다.

$⇒ (((+ab)/c)-(d\times(-ab)))$ 괄호를 하나씩 없앨 때마다 연산자를 앞으로 뺍니다.

$⇒ ((/+abc)-(\times d-ab))$

$⇒ -/+abc\times d-ab$

 

중위 표기법 → 후위 표기법

$(a+b)/c-d\times (a - b)$

$⇒ (((a+b)/c)-(d\times (a-b)))$ 연산자에 의해 계산이 이루어지는 범위마다 괄호를 쳐줍니다.

$⇒ (((ab+)/c)-(d\times(ab-)))$ 괄호를 하나씩 없앨 때마다 연산자를 앞으로 뺍니다.

$⇒ (ab+c/)-(dab-\times)$

$⇒ ab+c/dab-\times-$

 

예시 1. 괄호

스택 자료구조를 응용한 것 중 대표적인 문제 중 하나는 괄호 검사입니다. 괄호의 짝을 맞추는 과정에서 스택을 사용하기 때문에 스택 사용에 익숙해지는데 도움이 됩니다. 스택을 사용해 왼쪽 괄호를 넣어 놓고, 문자열을 계속 검사하면서 오른쪽 괄호가 나왔을 때 스택을 꺼내면서 짝이 맞는지 검사하는 식으로 괄호의 오류를 검사할 수 있습니다.

 

키보드 상에서 작성할 수 있는 괄호는 크게 세 가지입니다. 대괄호([, ]) / 중괄호({, }) / 소괄호((, ))가 있습니다. 이 괄호들이 무작위로 작성되어 있는 문자열들을 검사해주면 됩니다. 

 

괄호의 짝을 맞출 때 고려해야 할 점은 아래와 같습니다.

• 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호의 쌍은 서로를 교차하면 안된다. ex) ({[)}]
• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
• 왼쪽 괄호가 나온 다음에 오른쪽 괄호가 나와야 한다. 단, 괄호의 종류가 다르면 안 된다.

 

코드는 아래와 같습니다.

int check_matching(const char *in) {
    Stack s;
    char ch, open_ch;
    int n = strlen(in); // n = 문자열의 길이
    init_stack(&s); // 스택 초기화

    for (int i = 0; i < n; i++) {
        ch = in[i];
        switch(ch) {
        // 여는 괄호이면 스택에 push
        case '(': case '[': case '{':
            push(&s, ch);
            break;
        // 닫는 괄호이면
        case ')': case ']': case '}':
            // 비어있는지 검사하고 비어있으면 왼쪽 괄호가 없다는 뜻이므로 return 0;
            if(is_empty(&s)) return 0;
            else {
                // 스택에 무언가가 있다면 여는 괄호일 것이고 짝이 맞는지 검사 후 아니면 return 0;
                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;
}

 

예시 2. 후위 표기 수식의 계산

컴파일러는 수식을 만나게 되면 어떻게 계산을 할까요? 괄호와 연산자가 있는 수식에서는 스택을 사용해 계산합니다.

프로그래머가 수식을 중위 표기법으로 작성하면 컴파일러는 후위 표기법으로 변환한 후에 스택을 이용해 계산합니다.

 

후위 표기법으로 변환하는 이유는 다음과 같습니다.

• 괄호를 쓰지 않고서도 우선 계산해야 할 내용을 나타낼 수 있음.
• 수식을 읽으면서 바로 계산할 수 있음.

 

예를 들어 하나의 중위 표기 수식을 후위 표기 수식으로 바꿔보겠습니다.

$$(a+b)*c$$

이 식은 우리가 잘 알다시피 우선순위가 괄호 -> 곱하기 순으로 되어있습니다. 괄호 안에 먼저 더하고 곱하기를 해야겠죠? 후위 표기 수식으로 변경하면 다음과 같습니다.

$$ab+c*$$

$ab+$ 부분을 먼저 봅시다. 피연산자를 먼저 두 개 작성한 다음 연산자를 그 다음에 작성한 것을 볼 수 있습니다. 그 결과값이 나오면, 뒤에 있는 피연산자인 $c$와 함께 곱하기를 수행합니다. 위에서 설명했듯 읽으면서 연산을 수행할 수 있어 순차적으로 계산하기 용이합니다. 

 

후위 표기법으로 작성되어 있는 수식을 읽다가,

• 숫자가 나오면(피연산자) → 스택에 push
• 연산자가 나오면 → 스택에 있는 값을 두 번 빼내어 계산 후 다시 스택에 push

하면 됩니다.

// 후위 표기법으로 되어 있는 수식을 계산
int eval(char exp[]) {
    int op1, op2, value = 0, len = strlen(exp);
    char ch;
    Stack s;
    init_stack(&s);

    for(int i = 0; i < len; i++) {
        ch = exp[i];
        // 입력이 피연산자이면 스택에 push
        if(ch != '+' && ch != '-' && ch != '*' && ch != '/') {
            value = ch - '0';
            push(&s, value);
        // 연산자이면 피연산자를 스택에서 pop하고 연산을 수행해 스택에 저장
        } 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);
}

 

 

예시 2-2. 중위 표기법 → 후위 표기법

앞서 프로그래머가 중위 표기법으로 작성하면, 컴파일러에서는 이를 후위 표기법으로 변경해서 계산한다고 작성했습니다. 그 과정을 코드로 작성한 것이라고 보면 됩니다.

 

수식에서 단연코 중요한 점은 우선순위입니다. 우리가 고려해야 할 점은 다음과 같습니다.

1. 연산자(+, -, *, /)들의 우선순위
2. 연산자의 우선순위가 같을 경우
3. 괄호가 포함되어있는지의 여부에 따른 우선순위

첫 번째로, 연산자의 우선순위는 어떻게 정하면 될까요? 일단 우리는 다음을 알고 있습니다.

• 곱셈과 나눗셈이 우선순위가 가장 높음
• 스택은 후입선출

따라서 연산자를 스택에 저장할 때는 우선순위가 높은 연산자가 먼저 나와야 하기 때문에, 곱셈과 나눗셈을 저장해야합니다.

 

두 번째로, 우선순위가 같은 경우입니다. 이 때에는 스택이 제일 위에 있는 원소를 꺼내 출력해주면 됩니다.

 

세 번째로, 괄호가 포함되어 있을때의 우선순위 결정입니다.

• 왼쪽 괄호를 우선순위가 가장 낮다고 정합시다. 따라서 스택에 무조건 저장합니다.
• 오른쪽 괄호를 만나면 스택을 pop() 하면서 왼쪽 괄호가 나올 때까지 연산자를 출력합니다.

위의 고려한 조건들을 모두 작성한 코드는 아래와 같습니다.

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

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

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

// 스택이 비었는지 검사하는 함수
int is_empty(Stack *s) {
	return s->top == -1;
}

// 스택이 꽉 찼는지 검사하는 함수
int is_full(Stack *s) {
	return s->top == MAX_STACK_SIZE - 1;
}

// 스택에 값을 넣는 함수
void push(Stack *s, element item) {
	if(is_full(s)) {
		fprintf(stderr, "스택이 꽉 찼습니다.");
		exit(1);
	} else {
		s->data[++(s->top)] = item;
	}
}

// 스택에 값을 빼는 함수
element pop(Stack *s) {
	if(is_empty(s)) {
		fprintf(stderr, "스택이 비어있습니다.");
		exit(1);
	} else {
		return s->data[(s->top)--];
	}
}

// 가장 위의 값을 확인하는 함수
element top(Stack *s) {
	if(is_empty(s)) {
		fprintf(stderr, "스택이 비어있습니다.");
		exit(1);
	} else {
		return s->data[s->top];
	}
}

// 연산자의 우선순위 반환하는 함수
int prec(char op) {
	switch(op) {
		case '(': case ')': return 0;
		case '+': case '-': return 1;
		case '*': case '/': return 2;
	}
	return -1;
}

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

	init_stack(&s);
	for(int i = 0; i < len; i++) {
		ch = exp[i];
		switch(ch) {
			case '+': case '-': case '*': case '/': // 연산자
				while (!is_empty(&s) && (prec(ch) <= prec(top(&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));
	}
}

int main() {
	char *s = "(2+3)*4+9";
	printf("infix: %d", s);
	printf("postfix: ");
	infix_to_postfix(s);
	printf("\n");
}