[자료구조] 스택

LIFO: Last-in First-out

먼저 연산하고 싶은 것을 나중에 삽입

---

스택 ADT(추상데이터타입)

create(size)	크기 size인 공백 스택 생성
size(s)	스택의 크기 리턴
is_full(s)	스택의 원소수가 size와 같으면 TRUE
is_empty(s)	스택의 원소수가 0이면 TRUE
push(s, item)	스택에 데이터 추가
pop(s)	스택에서 데이터 삭제
peek(s)	스택의 맨 위 원소를 제거하지 않고 반환

---

정적 배열을 이용한 스택의 구현 (Static Stack)

-스택 크기가 고정되어 실행 중 변경 불가능

-1차원 배열 stack[]

-가장 최근에 입력된 자료의 인덱스 top

-가장 먼저 들어온 요소 stack[0], 가장 최근에 들어온 요소 stack[top]

-스택이 공백상태이면 top은 -1

 

realloc() : 모자를 때 추가할 수 있음

 

C 전역변수 배열로 구현

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

int size(){
    return(top + 1);
}

void push(element item){
    if (is_full()){
        printf("%s","스택 포화 에러\n");
        return;
    }
    else{
        stack[++top] = item;
    }
}

element pop(){
    if(is_empty()){
        printf("%s","스택 공백 에러\n");
        exit(1); //에러로 인한 강제 종료
    }
    else{
        return stack[top--];
    }
}

 

C 구조체 매개변수 배열로 구현

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

int size(StackType* s){
    return(s->top + 1);
}

void push(StackType* s, element item){
    if(id_full(s)){
        printf("%s", "스택 포화 에러\n");
        return;
    }
    else{
        s->data[++(s->top)] = item;
    }
}

element pop(StackType* s){
    if(is_empty(s)){
        printf("%s", "스택 공백 에러\n");
        exit(1);
    }
    else{
        return s->data[(s->top)--];
    }
}

---

동적 배열 스택 (Dynamic Stack)

-포인터를 이용하여 연결리스트로 구현

-스택 크기를 필요에 따라 가변적으로 조정 가능

-포인터를 저장할 추가 메모리 필요 

 

C 

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

void delete(StackType* s){
    free(s);
}

void push(StackType* s, element item){
    if(is_full(s)){
        s->capacity *= 2; //크기를 2배로 늘리고
        s->data = (element*)realloc(s->data, s->capacity*izeof(element));
        //더 큰 공간을 할당하고 기존 데이터는 그대로 카피
    }
    s->data[++(s->top)] = item; 
}

---

Applications using stack

recursion(나중에 호출한 함수를 먼저 실행), Undo-redo, String reversal

 

Balanced parenthesis stack(괄호검사)

조건

1) 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다

2) 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다

3) 괄호 사이에는 포함 관계만 존재한다

 

가장 최근에 만난 괄호를 먼저 검사해야 하니 스택 사용

-열림이 나오면 스택에 넣어, 닫힘이 나오면 pop으로 짝을 맞춰봐

-다 끝나고 뭐 남으면 오류

-닫힘이 먼저 나오면 오류

-비교했는데 짝이 안 맞으면 오류

int check_matching(const char* in){
    StackType s;
    char ch, open_ch;
    int n = strlen(in); //문자열 길이
    
    init_stack(&s);
    
    for(int i = 0; i < n; i++){
        sh = in[i];
        swich(ch){
            case'(';
            case'[';
            case'{';
                push(&s, sh); //열림은 일단 스택에 넣어
                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; //for문 끝났는데 뭐 남아있으면 오류
    return 1; //아니면 성공
}

---

 

Expression evaluation stack : postfix computation (후위 표기식의 계산)

postfix

1) operand(피연산자)는 항상 해당 operator(연산자) 앞에 등장한다

2) 실행 순서는 등장 순서를 따른다

eg) 82/3-32*+	스택
8	8
2	8	2
/	4
3	4	3
-	1
3	1	3
2	1	3	2
*	1	6
+	7

 

int eval (char exp[]){
    int op1, op2, value;
    int len = strlen(exp);
    char ch;
    StackType s;
    
    init_stack(&s);
    
    for(int i = 0; i < len; i++){
        ch = exp[i];
        if(ch !='+' && ch !='-' && ch !='*' && ch !='/'){ //operand가 들어오면
            value = ch -'0'; //char를 int로 바꿔서
            push(&s, value); //스택에 넣어
        }
        else{ //operator가 들어오면
            //operand 2개 빼서
            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);
}

---

Infix to postfix conversion (중위표기식을 후위 표기식으로 변환)

Shunting Yard algorithm by Edgar Dijkstra

int prec(char op){ //priorty
    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);
    StackType 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(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: //operand
                printf("%c",ch);
                break;
        }
    }
    while(!is_empty(&s)) //남은 거 다 출력
        printf("%c",pop(&s));
}

---

Backtracking(미로찾기)

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

element here = {1,0}, entry = {1,0};

char maze[MAX_SIZE][MAX_SIZE] ={ //1은 벽, 0은 길로 미로 만들기
    {'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; //0보다 작으면 좌표가 아님 오류
    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)){ //x를 찾기 전에 스택이 비어버림(갈 수 있는 경로가 없음)
            printf("실패\n");
            return;
        }
        else here = pop(&s);
    }
    
    printf("성공\n"); //x를 찾아 while에서 나오면 성고
    return 0;
}