[책 정리] Chapter 05. 스택

5.1 스택 추상 자료형

후입 선출(LIFO: Last-In First-Out): 가장 최근에 들어온 자료가 가장 먼저 나가는 것
스택(stack): 후입 선출의 형식으로 입출력이 일어나는 자료구조

• 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조
• 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없음
• 스택에서 입출력이 이루어지는 부분: 스택 상단(stack top) / 반대쪽인 바닥 부분: 스택 하단(stack bottom) / 스택에 저장되는 것: 요소(element) / 스택에 요소가 하나도 없을 때: 공백 스택(empty stack)

<ADT 5.1.1> 추상 자료형 stack

객체: n개의 element 타입의 요소들의 순서 있는 모임
연산:
	create() ::= 스택 생성
    is_empty(s) ::= 스택이 비어 있는지 검사
    is_full(s) ::= 스택이 가즉 찼는지 검사
    push(s,e) ::= 스택의 맨 위에 요소 e를 추가
    pop(s) ::= 스택의 맨 위에 있는 요소를 삭제
    peek(s) ::= 스택의 맨 위에 있는 요소를 삭제하지 않고 반환

Quiz

1. 스택과 같은 입출력 형태를 후입 선출(LIFO)라고 한다.
2. 스택을 사용하여서 a, b, c, d, e를 입력하고 b, c, d, e, a와 같은 출력을 얻으려면 입력과 출력의 순서를 어떻게 해야하는가?
   -> push(a) -> push(e) -> push(d) -> push(c) -> push(b) -> pop() -> pop() -> pop() -> pop() -> pop()

5.2 배열로 구현한 스택

• top 변수: 스택에서 가장 최근에 입력되었던 자료를 가리키는 변수, 아무런 데이터가 없을 경우 -1, top 값이 (MAX_STACK_SIZE-1)이면 배열의 끝까지 요소가 채워져 있음을 의미

<알고리즘 5.2.1> 스택의 is_empty 연산

is_empty(s)

if top = -1
	then return TRUE
    else return FALSE

<알고리즘 5.2.2> 스택의 is_full 연산

is_full(s)

if top = (MAX_STACK_SIZE -1)
	then return TRUE
    else return FALSE

<알고리즘 5.2.3> 스택의 push 연산

push(S,x)

if is_full(S)
	then error "overflow"
    else top <- top + 1 // top의 값이 먼저 증가
    	 stack[top] <- x

<알고리즘 5.2.4> 스택의 pop 연산

pop(S)

if is_empty(S)
	then error "underflow"
    else e <- stack[top]
    	 top <- top-1
         return e

전역 변수로 구현하는 방법

• 스택을 표현하는 1차원 배열과 top변수를 모두 전역 변수로 구현

<프로그램 5.2.1> 정수 배열 스택 프로그램

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

#define MAX_STACK_SIZE 100
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;

// 공백 상태 검출 함수
int is_empty(){
    return (top == -1);
}

// 포화 상태 검출 함수
int is_full(){
    return (top == MAX_STACK_SIZE - 1);
}

// 삽입 함수
void push(element data){
    if(is_full()){
        fprintf(stderr, "overflow\n");
        return;
    }else{
        stack[++top] = data;
    }
}

// 삭제 함수
element pop(){
    if(is_empty()){
        fprintf(stderr, "underflow\n");
        exit(1);
    }else{
        return stack[top--];
    }
}

// 피크 함수
element peek()
{
    if (is_empty()) {
        fprintf(stderr, "underflow\n");
        exit(1);
    } else {
        return stack[top];
    }
}

// 주 함수
int main(){
    push(1);
    push(2);
    push(3);

    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", is_empty());
    return 0;
}

<프로그램 5.2.2> 구조체 배열 스택 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.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);
}

// 삽입 함수
void push(element data){
    if(is_full()){
        fprintf(stderr, "overflow\n");
        return;
    }else{
        stack[++top] = data;
    }
}

// 삭제 함수
element pop(){
    if(is_empty()){
        fprintf(stderr, "underflow\n");
        exit(1);
    }else{
        return stack[top--];
    }
}

// 피크 함수
element peek()
{
    if (is_empty()) {
        fprintf(stderr, "underflow\n");
        exit(1);
    } else {
        return stack[top];
    }
}

// 주 함수
int main(){
    element ie, oe;
    strcpy(ie.name, "HongGilDong");
    strcpy(ie.address, "Seoul");
    ie.student_no = 20053001;
    push(ie);
    oe = pop();

    printf("name: %s\n", oe.name);
    printf("address: %s\n", oe.address);
    printf("student number: %d\n", oe.student_no);
    return 0;
}

관련된 데이터를 함수의 매개변수로 전달하는 방법

• top과 stack 배열을 하나의 구조체로 결랍시켜서 이 구조체의 포인터를 함수의 매개변수로 전달

<프로그램 5.2.3> 일반적인 배열 스택 프로그램

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

#define MAX_STACK_SIZE 100
typedef int element;
typedef struct{
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;

// 스택 초기화 함수
void init(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 data){
    if(is_full(s)){
        fprintf(stderr, "overflow\n");
        exit(1);
    }else{
        s->stack[++(s->top)] = data;
    }
}

// 삽입 함수
element pop(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "underflow\n");
        exit(1);
    }else{
        return s->stack[(s->top)--];
    }
}

// 피크 함수
element peek(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "underflow\n");
        exit(1);
    }else{
        return s->stack[(s->top)];
    }
}

// 주 함수
int main(){
    StackType s;

    init(&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));
    printf("%d\n", is_empty(&s));

    return 0;
}

Quiz

1. 스택에서 top이 가리키는 것은 무엇인가? -> 가장 최근에 들어온 자료를 가리키는 변수
2. top이 8이면 현재 스택에 저장된 데이터의 총수는 몇 개 인가? -> 9개

5.3 연결 리스트로 구현한 스택

연결된 스택(linked stack): 연결 리스트를 이용해서 구현된 스택이나 큐

typedef int element;
typedef struct StackNode{
	element item; // 데이터 필드
    struct StackNode *link; // 링크 필드
} StackNode;

typedef struct{
	StackNode *top; // 노드를 가리키는 포인터로 선언됨
} LinkedStackType;

<프로그램 5.3.1> 연결된 스택 프로그램

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

typedef int element;
typedef struct StackNode{
    element item;
    struct StackNode* link;
} StackNode;

typedef struct {
    StackNode* top;
}LinkedStackType;

// 초기화 함수
void init(LinkedStackType *s){
    s->top = NULL;
}

// 공백 상태 검출 함수
int is_empty(LinkedStackType *s){
    return (s->top == NULL);
}

// 삽입 함수
void push(LinkedStackType *s,element item){
    StackNode* tmp = (StackNode*)malloc(sizeof(StackNode));
    if(tmp == NULL){
        fprintf(stderr, "memory allocate error\n");
        return;
    }else{
        tmp->item = item;
        tmp->link = s->top;
        s->top = tmp;
    }
}

// 삭제 함수
element pop(LinkedStackType *s){
    if(is_empty(s)){
        fprintf(stderr, "underflow\n");
        exit(1);
    }else{
        StackNode* tmp = s->top;
        element e = tmp->item;
        s->top = s->top->link;
        free(tmp);
        return e;
    }
}

// 피크 함수 
element peek(LinkedStackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "underflow\n");
        exit(1);
    } else {
        return s->top->item;
    }
}

int main(){
    LinkedStackType s;
    init(&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));
    printf("%d\n", is_empty(&s));

    return 0;
}

Quiz

1. 연결 리스트로 스택을 구현하는 경우의 장점? -> 크기가 제한되지 않는다는 장점이 있다. 동적 메모리 할당만 할 수 있으면 스택의 새로운 요소를 삽입할 수 있음.
2. 연결 리스트로 구현된 스택의 경우 top 변수의 의미는 무엇인가? -> 가장 최근에 들어간 노드를 가리키는 포인터

5.4 괄호 검사

괄호 검사 조건
조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함
조건 2: 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함
조건 3: 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안됨

{A[(i+1)]=0;} -> 오류 없음
if((i==0) && (j==0) -> 오류: 조건 1 위반
A[(i+1])=0; -> 오류: 조건 3 위반

괄호 사용의 오류를 검사라는데 스택을 사용할 수 있음
1. 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입
2. 오른쪽 괄호를 만나면 스택에서 맨 위의 괄호를 꺼낸 수 짝은 맞는지 검사
-> 이때, 스택이 비어 있으면 조건 1 또는 조건 2 등을 위반하게 되고, 괄호의 짝이 맞지 않으면 조건 3에 위반, 마지막 괄호까지 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위반
3. 오료 검사 결과 위반인 경우 FALSE 반환 아닌 경우 TRUE를 반환

<알고리즘 5.4.1> 스택의 pop 연산 괄호 검사

check_matching(expr)

while(입력 expr의 끝이 아니면) do
	ch <- expr의 다음 글자
    swich(ch)
    	case '(' : case '[' : case '{':
        	check를 스택에 삽입
            break;
        case ')' : case ']' : case '}':
        	if(스택이 비어 있으면}
            	then 오류
                else 스택에서 open_ch를 꺼냄
                	if(ch와 open_ch가 같은 짝이 아니면)
                    	then 오류
            break
	if(스택이 비어 있지 않으면)
    	then 오류

<프로그램 5.4.1> 괄호 검사 프로그램

typedef char element; // 스택 객테 자료형 정의

// <프로그램 5.2.3> 일반적인 배열 스택 프로그램 코드를 여기에 포함

// 괄호 검사 함수
int check_matching(const char* in)
{
    StackType s;
    int n = strlen(in);
    char ch, open_ch;
    init(&s);

    for (int i = 0; i < n;i++){
        ch = in[i];
        switch (ch)
        {
        case '(': case '[': case '{':
            push(&s, ch);
            break;
        case ')' : case ']': case '}':
            if(is_empty(&s))
                return false;
            else{
                open_ch = pop(&s);
                if((open_ch == '(' && ch !=')') || (open_ch == '[' && ch != ']') ||(open_ch =='{' && ch !='}' )){
                    return false;
                }
            }
            break;
        }
    }

    if(!is_empty(&s)){ // 스택에 남아 있으면 오류
        return false;
    }
    return true;
}

// 주 함수
int main()
{
    if ( check_matching("{A[(i+1)]=0;}") == true){
        printf("success\n");
    }else{
        printf("fail\n");
    }
    return 0;
}

Quiz

1. 다음과 같은 수식이 스택을 이용하여서 어떨게 처리되는지 그림으로 설명해라

{(a+b)*k[2+3*n]}
{[(2+10)*u]/3}

5.5 수식의 계산

후위 표기 수식의 계산

중위(infix) 표기: 연산자가 피연산자 사이에 있는 경우
후위(postfix) 표기: 연산자가 피연산자 뒤에 있는 경우
전위(prefix) 표기: 연산자가 피연산자 앞에 있는 경우

[수식의 3가지 표기법]

중위 표기법	후위 표기법	전위 표기법
2+3*4	234*+	+2*34
a*b+5	ab*5+	+*ab5
(1+2)*7	12+7*	*+127

• 컴파일러는 후위 표기 방법을 선호 -> 괄호가 필요 없기 때문, 우선 계산해야할 내용을 나타낼 수 있음, 수식을 읽으면서 바로 계산 가능
• 중위 표기법이 주어지면 컴파일러는 후위 표기법으로 변환한 후 스택을 이용하여 계산

후위 표기 수식 계산
1. 수식을 왼쪽에서 오른꼿으로 스캔하여 피연산자면 스택에 저장
2. 연산자이면 필요한 수 만큼의 피연산자를 스택에서 꺼내 연산 실행 후 그 결과를 다시 스택에 저장
ex) 82/3-32*+

]

토큰	스택
[0]	[1]	[2]	[3]	[4]	[5]	[6]
8	8
2	8	2
/	4
3	4	3
-	1
3	1	3
2	1	3	2
*	1	6
+	7

<알고리즘 5.5.1> 후위 표기 수식 계산 알고리즘

스택 s를 생성하고 초기화함
for item in 후위표기식 do
	if(item이 피연산자이면)
    	then push(s, item)
    if(item이 연산자이면)
    	then second <- pop(s)
        	 first <- pop(s)
             result <- first op second // op는 +-*/ 중의 하나
             push(s, result)
final_result <- pop(s)

<프로그램 5.5.1> 후위 표기식 계산

// <프로그램 5.2.3> 일반적인 배열 스택 프로그램 코드를 여기에 포함

// 후위 표기 수식 계산 함수
int eval(char exp[]){
    int n = strlen(exp);
    StackType s;
    init(&s);
    for (int i = 0; i < n;i++){
        if(exp[i] >='0' && exp[i] <='9'){
            push(&s, exp[i]-'0'); // 입력이 피연산자이면 
        }else{ // 연산자이면 피연산자를 스택에서 제거
            int second = pop(&s); 
            int first = pop(&s);
            switch(exp[i]){ // 연산을 수행하고 스택에 저장
                case '+':
                    push(&s, first + second);
                    break;
                case '-':
                    push(&s, first - second);
                    break;
                case '*':
                    push(&s, first * second);
                    break;
                case '/':
                    push(&s, first / second);
                    break;
            }
        }
    }
    return pop(&s);
}

// 주 함수
int main()
{  
    int result;
    printf("postfix: 82/3-32*+\n");
    result = eval("82/3-32*+");
    printf("result: %d", result);
    return 0;
}

중위 표기 수식을 후위 표기 수식으로 변환

• 중위 표기법과 후기 표기법의 공통점은 피연산자의 순서가 동일

1. 입력 수식을 왼쪽에서 오른쪽으로 스캔
2. 피연산자를 만나게 되면 바로 후위 표기 수식에 출력
3. 연산자를 만나게 되면 언딘가 잠시 저장 -> 기본적으로 가장 나중에 스캔된 연산자가 가장 먼저 출력되어야 함(연산자의 스캔 순서대로 연산자의 우선순위가 높을 떄 올바름)

중위 표기법	후위 표기법
a+b	ab+
(a+b)*c	ab+c*
a+b*c	abc*+
a*b+c	ab*c+

<알고리즘 5.5.2> 중위 표기 수식을 후위 표기 수식으로 변환하는 알고리즘

infix_to_posfix(exp)

스택 s를 생성하고 초기화
while(exp에 처리할 문자가 남아 있으면) do
	ch <- 다음에 처리할 문자
    switch(ch)
    	case 연산지:
        	whlie(peek(s)의 우선순위 >= ch의 우선순위) do
            	e <- pop(s)
                e를 출력
            push(s,ch);
            break;
        case 왼쪽 괄호:
        	push(s,ch);
            break;
        case 오른쪽 괄호:
        	e <- pop(s)
            while(e != 완쪽 괄호) do
            	e를 출력
                e <- pop(s)
            break;
        case 피연산자:
        	ch를 출력
            break;
while(not is_empty(s) ) do
	e <- pop(s)
    e를 출력

<프로그램 5.5.2> 중위 표기 수식을 후위 표기 수식으로 변환하는 프로그램

typdef char element;

// <프로그램 5.2.3> 일반적인 배열 스택 프로그램 코드를 여기에 포함

// 연산자의 우선순위를 반환
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[]){
    int len = strlen(exp);
    StackType s;
    init(&s);
    char top_op;

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

// 주 함수
int main()
{
    infix_to_postfix("a+b");
    infix_to_postfix("(a+b)*c");
    infix_to_postfix("a+b*c");
    infix_to_postfix("a*b+c");
    infix_to_postfix("(2+3)*4+9");
    
    return 0;
}

5.6 미로 탐색 문제

1. 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽 순서로 스택에 저장
2. 스택 맨 위의 위치를 꺼내어 현재의 위치로 한 다음 같은 작업을 반복
3. 이런한 반복은 현재의 위치가 출구와 같거나 모든 위치를 다 검사해볼 때까지 계속됨
4. 한 번 거텨간 위치를 다시 검사하지 않도록 이미 검사한 위치는 표시를 하여 무한 루프에 빠지지 않게 함

<알고리즘 5.6.1> 미로 탐색 알고리즘

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

<프로그램 5.6.1> 미로 탐색 프로그램

#define MAZE_SIZE 6

typedef struct {
    short r;
    short c;
} element;

// <프로그램 5.2.3> 일반적인 배열 스택 프로그램 코드를 여기에 포함

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);
    }
}
// 주 함수
int main()
{
    int r, c;
    StackType s;

    init(&s);

    here = entry;
    while(maze[here.r][here.c]!='x'){
        r = here.r;
        c = here.c;
        printf("(%d %d) ", r, c);
        maze[r][c] = '.';
        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("fail\n");
            return -1;
        }else{
            here = pop(&s);
        }
    }
    printf("\nsuccess\n");
    return 0;
}

<참고자료>
천인국 · 공용해 · 하상호 지음,『C언어로 쉽게 풀어쓴 자료구조』, 생능출판(2016)