[자료구조론] C로 스택을 만들자

kysung95·2021년 4월 14일
CS자료구조
3

자료구조론

목록 보기
1/11
post-thumbnail

안녕하세요. 김용성입니다.
저는 컴퓨터 공학을 전공하고 있는데, 사실 1/2학년 때 컴퓨터에 흥미를 많이 느끼지 못했어요.
본격적으로 컴퓨터에 흥미를 느끼기 시작한건 작년 여름 쯤부터였는데요.
복학을 하고나니, 재수강 할 과목들이 산더미더라구요..
여튼 부끄럽지만 이번 학기에는 제가 자료구조론을 재수강하게 되었습니다..ㅎ

저는 현재 1일 1포스팅을 진행중인데요. 다음주가 시험기간이다보니, 이 시기에는 학교 중간고사 공부와 포스팅을 병행해서 진행해보는 것이 어떨까하는 생각을 쭉 하였습니다.
그래서 오늘의 포스팅은 제가 현재 학교에서 배우고 있는 자료구조론, 그 중에서도 스택에 대해 포스팅하도록 해보겠습니다.

(현재 webview 개론도 진행해야하고, react관련된 포스팅도 진행해야하는데 그렇게 하지 못한 점 양해부탁드립니다..시험이 끝나면 최대한 front-end 위주의 포스팅을 할께요.)

이번 포스팅은 c언어에 대한 어느정도 기본 지식이 있는 컴퓨터공학 전공 1,2학년 혹은 비전공자 분들에게 많은 도움이 되실 거라 생각해요.

스택

스택은 컴퓨터에서 정말 많이 사용되는 자료구조입니다.
우리가 일상 속에서 스택을 사용하는 예를 살펴보면 다음과 같습니다.

  • 식당에 쌓여있는 접시 더미
  • 핸드폰에서 현재 사용중인 앱을 종료할 경우 그 전 가장 최근에 사용했던 앱이 가장 위로 올라옴

이런 것들이 있는데요. 음 만약에 여러분들이 식당의 설거지 알바생이라고 가정했을 때, 접시를 아래서부터 빼서 설거지를 진행하라 하면, 굉장히 힘들겠죠? 가장 최근에 쌓인 접시부터 빼내어서 설거지를 진행해야 여러분들의 일이 편해질거예요. 컴퓨터에서도 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 때가 있는데요. 이런 경우에 스택을 긴요하게 사용합니다.

스택은 이처럼 가장 최근에 들어온 것을 먼저 빼내는 형식 즉 LIFO: Last-In First-Out 후입선출 형태를 띱니다. 그림으로 보여드리도록 할께요.

이해가 되시나요? 위 그림이 스택의 기본적인 형태입니다.
우리는 코드 상에서 저 삽입을 push라고 부를 것이고, 삭제를 pop이라고 부르도록 할겁니다. 또한 스택 상단을 top이라고 부르고 스택 하단을 bottom이라고 부르도록 할께요.

추상 자료형 스택

스택을 c언어 코드로 구현하기 이전에 먼저 추상화하여 몇가지 메소드들을 정의해보도록 하겠습니다.

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 OVERFLOW_ERROR;
else 스택의 맨 위에 item 추가;
pop(s)
if(is_empty(s)) return UNDERFLOW_ERROR;
else 스택의 맨 위의 원소를 제거하여 반환;
peek(s)
if(is_empty(s)) return UNDERFLOW_ERROR;
else 스택의 맨 위의 원소를 제거없이 반환만;

어느정도 이해가 되시죠? 스택을 구현할 때에는 제가 위에 정의한 메소드들에 대해서만 잘 이해하고 있으면 됩니다.

스택을 생성하고(create), 요소를 추가할 때(push) 스택의 포화여부를 확인(is_full)하고, 스택에서 요소를 삭제하여 반환할 때(pop) 혹은 반환만 하고 싶을 때(peek)는 스택의 공백여부(is_empty)를 확인하는 것.
이것이 기본적으로 스택에서 사용할 메소드들이라고 생각하시면 됩니다.

스택을 구현해보자

이제 앞서서 만들었던 추상화된 것들을 코드로 구현하도록 하겠습니다.
우선 여러가지 형태가 있을 수 있기 때문에 저는 다음과 같이 몇가지를 정의하고 시작하겠습니다.

  • 스택에 저장되는 자료형은 student(학번,이름,주소)를 가진 요소
  • 스택 상단 변수는 top이라는 이름을 부여(가장 먼저들어온 요소는 stack[0] 최근에 들어온 요소는 stack[top]에 저장)
  • 스택의 최대 사이즈는 100으로 지정

아 그리고 중요한 점! 스택에 아무 요소가 없을 때에는 스택의 상단요소가 0이 아닌 -1으로 초기화되어 있어야 합니다. 왜냐하면 stack[0]의 공간에도 데이터를 저장하여야 하기 때문이죠! 이점은 스택을 만들 때 꼭 숙지하고 있어야 합니다!!

이제 구현 코드를 작성해보도록 하겠습니다.

stack 코드 (전역)

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

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct{ // 학생 구조체 생성
    int student_number;
    char student_name[MAX_STRING];
    char student_address[MAX_STRING];
}student;

student stack[MAX_STACK_SIZE]; // 스택 배열을 전역변수로 선언 
int top=-1; // 스택의 상단 -1로 초기화

int is_empty(){ 
    return top==-1;  // top=-1일 경우 스택이 비어있다고 TRUE를 return
}

int is_full(){
    return (top>=MAX_STACK_SIZE-1); // c언어에서는 배열의 시작이 0부터이므로 top=size-1일 경우 스택이 가득차있다고 TRUE를 return
}

void push(student object){ 
    if(is_full()){
        fprintf(stderr,"OVERFLOW\n");
        return;
    }
    else stack[++top]=object; // top값을 증가 시킨 뒤에 student 객체 추가 
}

student pop(){
    if(is_empty()){
        fprintf(stderr,"UNDERFLOW\n");
        exit(1);
    }
    else return stack[top--]; // top에 있던 객체를 반환한 후 top값 감소
}

student peek(){
    if(is_empty()){
        fprintf(stderr,"UNDERFLOW\n");
        exit(1);
    }
    else return stack[top];  // top에 있는 객체 반환
}

int main(void){
    student kys={
            201511796,"KYS","Seoul"
    };
    student object;
    push(kys); // kys라는 이름을 가진 student 객체 삽입
    object=pop(); // 스택에서 반환되는 객체를 s에 저장

    printf("student number:%d\n",object.student_number);
    printf("student name:%s\n",object.student_name);
    printf("student address:%s\n",object.student_address);

    return 0;
}

student number: 201511796
student name: KYS
student address: Seoul

크게 어려운 부분은 없으실거예요.
그렇지만 해당 코드는 현대적이지 못합니다. 스택 배열이 전역변수로 선언되어있기에 해당 프로그램에서는 스택을 하나밖에 다루지 못하기 때문이죠.
요즘같이 객체 지향 프로그램이 각광받는 시대에 이는 전혀 좋은 방식이 아니라고 볼 수 있습니다.
물론 여러개의 이름이 다른 메소드를 정의하거나 혹은 변수를 우겨넣음으로써 여러개의 스택을 다룰 수 있겠지만, 그건 전혀 효율적이지 못하죠?
이럴 때는 포인터를 사용하여 주소값을 매개변수로 넣어주는 방식으로 해결할 수 있습니다.

아래의 코드를 살펴볼까요?

stack 코드 (매개변수 사용)

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

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct{
   int student_number;
   char student_name[MAX_STRING];
   char student_address[MAX_STRING];
} student;

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


void init_stack(Stack *s){ // top 변수가 이제 더이상 전역변수가 아니므로 스택 초기화 함수를 따로 만들었습니다.
    s->top=-1;
    return;
}

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,student object){
    if(is_full(&s)){
        fprintf(stderr,"OVERFLOW\n");
        return;
    }
    else s->data[++s->top]=object;
}

student pop(Stack *s){
    if(is_empty(&s)){
        fprintf(stderr,"UNDERFLOW\n");
        exit(1);
    }
    else return s->data[s->top--];
}

student peek(Stack *s){
    if(is_empty(&s)){
        fprintf(stderr,"UNDERFLOW\n");
        exit(1);
    }
    else return s->data[s->top];
}

int main(void){
    Stack s;
    init_stack(&s);
    student kys={
            201511796,"KYS","Seoul"
    };
    student object;
    
    push(&s,kys);
    object=pop(&s);

    printf("student number:%d\n",object.student_number);
    printf("student name:%s\n",object.student_name);
    printf("student address:%s\n",object.student_address);

    return 0;
}

위의 코드로 수행할 경우 하나의 프로그램 안에서 여러개의 스택을 다룰 수가 있어 앞선 코드보다 훨씬 더 효율적인 작업을 할 수 있습니다.

동적 배열 stack 코드

여기서 한발 더 나아가서
스택이 요소가 얼마나 담길지 모르는 가변요소 상태라면 동적메모리 할당을 사용해서 구현하는 것이 가장 좋겠죠?
이제 동적 배열 스택을 한번 구현해보고자 해요.
우리는 이러한 동적 배열 스택을 구현하기 위해서 capacity라는 변수를 추가적으로 사용하고자 합니다. capacity라는 변수는 현재 stack의 용량을 int 형으로 담고 있게끔 할겁니다.
또한 malloc과 realloc를 사용하여 할당과 재할당을 필요할 때 사용할 것이니 이에 대해서도 알아보시면 좋을 것 같아요!

코드를 살펴보겠습니다. 

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


#define MAX_STRING 100

typedef struct{
   int student_number;
   char student_name[MAX_STRING];
   char student_address[MAX_STRING];
} student;

typedef struct{
    student *data;
    int capacity;  // 배열 용량 변수
    int top;
}Stack;

void init_stack(Stack *s){
    s->top=-1;
    s->capacity=1;
    s->data=(student *)malloc(sizeof(student)*s->capacity);
}

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

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

void push(Stack *s,student object){
    if(is_full(s)){
        s->capacity *=2;
        s->data=(student *)realloc(s->data,sizeof(student)*s->capacity);
    }
    s->data[++s->top]=object;
}

student pop(Stack *s){
    if(is_empty(s)){
        fprintf(stderr,"UNDERFLOW\n");
        exit(1);
    }
    else return s->data[s->top--];
}

student peek(Stack *s){
    if(is_empty(s)){
        fprintf(stderr,"UNDERFLOW\n");
        exit(1);
    }
    else return s->data[s->top];
}

int main(void){
    Stack s;
    init_stack(&s);
    student kys={
            201511796,"KYS","Seoul"
    };
    student object;

    push(&s,kys);
    object=pop(&s);

    printf("student number:%d\n",object.student_number);
    printf("student name:%s\n",object.student_name);
    printf("student address:%s\n",object.student_address);

    return 0;
}

저는 stack의 용량이 꽉 찼을 시, 용량을 2배로 증가시켜주는 식의 코드를 작성하였습니다.
push함수와 is_full함수 말고는 크게 달라진 건 없습니다.

is_full 함수 먼저 살펴보겠습니다.

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

동적 메모리 할당으로 코드를 구현하기 이전에는 MAX_STACK_SIZE라는 define 상수를 사용하여 top의 위치를 비교해주었는데, 이제는 capacity 변수를 사용하여 top의 위치를 비교해줍니다.

이번엔 push 함수를 살펴볼까요?

void push(Stack *s,student object){
    if(is_full(s)){
        s->capacity *=2;
        s->data=(student *)realloc(s->data,sizeof(student)*s->capacity);
    }
    s->data[++s->top]=object;
}

is_full에 대한 결과가 True일 경우에 capacity 크기를 2배로 늘려주고, 그에 s->data의 크기 또한 reallocation 해주었습니다.

어렵지 않죠?

스택 응용 알고리즘 문제

이렇게 기본적인 Stack을 C언어를 통해 구현해보았습니다.
이번에는 이것을 응용하여 여러 알고리즘 문제에 적용해보도록 하겠습니다.

괄호 검사 문제

프로그램에서는 여러가지 종류와 괄호들이 사용되는데, 괄호들은 항상 쌍이 되게끔 사용되어야 한다. 프로그램에서 사용되는 괄호는 대괄호 [,] , 중괄호 {,} , 소괄호 (,) , 등이 있다. 이들이 올바르게 사용되었는지 수식을 입력받아 판단해주는 코드를 작성해보자. 괄호의 검사 조건은 다음의 3가지이다.

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

이 문제는 상당히 유명한 문제로 스택을 통해 푸는 대표적인 문제 중 하나입니다.
스택을 사용하여 왼쪽 괄호-(,{,[ 등을 스택에 담아두다가 오른쪽 괄호들이 나오면 스택에서 가장 최근의 왼쪽 괄호를 꺼내어 비교하면서 괄호들의 오류를 검사하는 방식을 사용하면 됩니다.
아래의 그림을 살펴보겠습니다.

성공 사례

실패 사례

해당 스택에 요소가 남아있다는 것은 괄호의 짝이 맞지 않다는 것이기에 실패가 되겠죠?
어느정도 이해가 되셨으리라 생각합니다.

그럼 이제 코드를 작성하기에 앞서 괄호검사 알고리즘 의사코드를 작성해보도록 하겠습니다.

괄호검사 알고리즘 의사코드

expr 변수는 입력한 식을 담는 문자열 변수입니다.

check_match(expr):

while (입력 expr의 끝이 아니면)
ch <- expr 다음 글자
switch(ch)
    case '(':case'{':case'[':
        ch를 스택에 삽입
        break
    case ')':case'}':case']':
        if(스택이 비어있다면)
            then 오류
            else 스택에서 비교할 괄호를 꺼낸다.
               if(ch와 pop된 객체가 같은 짝이 아니면)
                    then 오류 보고
   break
if(스택이 비어 있지 않다면)
   then 오류 보고

이런 식의 의사코드를 작성할 수 있죠?? 그렇다면 이제 소스 코드를 작성해보겠습니다.

괄호검사 알고리즘 소스코드 

int check_matching(const char *in){
    Stack s;
    init_stack(&s);
    element ch;
    int len=strlen(in);

    for(int i=0;i<len;i++){
        ch=in[i];
        switch(ch){
        case '(':case '{':case '[':
            push(&s,ch);
            break;
        case ')':case '}':case ']':
            if(is_empty(&s)) return 0; // open 괄호가 없는 경우
            else if(ch==')' && pop(&s)!='(' || ch=='}' && pop(&s)!='{'||ch==']' && pop(&s)!='['){
                return 0; // open 괄호와 close 괄호의 짝이 맞지않는 경우
            }
            break;
        }

    }
    if(!is_empty(&s)) return 0; // open괄호가 남아있는 경우
    return 1;
}

저는 이렇게 구현해보았습니다.
입력된 문자열만큼 for문을 돌리며 switch문으로 적절히 조건을 분기해보았어요.
그리 어렵지 않다는 것 아실 수 있을거예요.

잘 작동하는지 main함수로 실행시켜보도록 하겠습니다.!

int main(void){
    char *p="{A[(i+1)]=0;}";
    if(check_matching(p)==1)
        printf("success!\n");
    else
        printf("fail!\n");
    return 0;
}

출력 값: success!

보다시피 잘 작동하는 것을 확인하실 수 있습니다. 참고로 당연한 이야기지만 element는 typedef char 형으로 선언하였습니다!

후위 표기 수식 계산법

이번에는 스택을 이용하여 후위표기수식계산법을 구현해보도록 하겠습니다.

후위표기수식계산법이란?
8x5 -> 85x (연산자가 피연산자의 뒤에 배치됨)

후위표기법으로 계산할 식이 주어지면 우리는 연산자와 피연산자로 나누어서 생각을 해야합니다.
피연산자들을 스택에 담아 둔 뒤에 연산자들이 나오면 2개의 요소를 pop해서 계산하는 식으로 생각하면 쉽게 코드를 작성할 수 있습니다.

이런식으로 구현하면 될 것 같네요!
의사코드는 생략하고 바로 소스코드를 작성해보겠습니다!
기본적으로 문자열을 받기 때문에 연산 시에 정수형으로 형변환을 해주어야해요. 이는 char-'0' 이라는 ASCII 코드를 활용한 방법으로 변환해주도록 하겠습니다.

후위표기식 계산법 알고리즘 소스코드 

int post_fix_eval(char exp[]){

    Stack s;
    int op1,op2,value,len=strlen(exp);
    element ch;

    init_stack(&s);
    for(int 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);
}

이런식으로 코드를 작성하면 된답니다! 다만 주의해야 하는 것은 op1과 op2를 헷갈려서는 안됩니다. 먼저 나오게 되는 값을 op2로 두느냐 op1으로 두느냐에 따라 계산 결과값이 다르게 나올 수 있습니다. 이는 그 아래 switch문에서 push해주는 식의 순서에 따라서 맞춰주면 됩니다!

중위 표기 수식 -> 후위 표기 수식

이제 마지막으로 중위표기수식을 후위표기수식으로 바꾸어보도록 하겠습니다.

생각해야 할 것이 은근 많은 알고리즘이예요.

이러한 사항들을 코드에 적용시켜야 합니다.

  • 왼쪽-> 오른쪽으로 스캔하며 피연산자를 만나게 되면 출력값에 대기시킴.
  • 연산자들의 우선순위 파악(*,/가 +,-보다 높은 우선순위)
  • 우선순위를 지정해주어도 우선순위가 같은 연산의 경우 순서를 잘 지켜주어야함.
  • 괄호는? 왼쪽 괄호는 무조건 스택에 담고 그 뒤 오른쪽 괄호가 나온다면 왼쪽괄호가 출력될 때까지 pop을 통해 연산자 출력.

코드로 구현을 해보겠습니다.

연산자 간의 우선순위를 나누어주는 함수와 중위 표기 수식 -> 후위 표기수식 함수 이렇게 두개의 함수로 나누어서 구현을 하면 편리합니다.

중위표기수식->후위표기수식 알고리즘 소스코드 

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

void infix_to_postfix(const char *exp){
    Stack s;
    int i=0;
    char ch,top_op;
    int len=strlen(exp);
    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));
}

출력값

infix=> (2+3)4+9
postfix=> 23+49+

이런 식으로 코드를 구현할 수 있습니다.

마무리

오늘 포스팅이 상당히 길어졌네요.
스택의 기본개념부터 활용방법까지 한 포스팅에 담다보니 꽤 내용이 길어진 것 같습니다.
이러한 자료구조론 부분이 정말 개발자들에게는 기본 중에 기본으로 여겨지기 때문에 다소 지루하고 유치한 내용일 수 있습니다. 그렇지만 이제 막 코딩에 입문해서 data logic을 배우시는 분들에게는 도움이 될만한 포스팅이라고 생각합니다.
저도 사실 그렇게 기본에 충실한 사람이 아니기 때문에 내용을 정리하면서 많은 발전을 한 것 같아요.

아무쪼록 긴 글 읽어주셔서 감사합니다.
내일도 유익한 내용을 가지고와서 포스팅 진행하도록 하겠습니다!!

profile
kysung95
김용성입니다.
다음 포스트

[자료구조론] C로 큐를 만들자

0개의 댓글