[Data Structures] 스택 (Stack)

1. 스택이란

• 선형 자료구조의 일종
• 한쪽은 막히고 한쪽은 뚫려있는 초코볼 통에 비유할 수 있다
• 후입선출 = Last In, First Out! (LIFO)

2. 스택 ADT와 헤더 파일 정의

#ifndef __AB_STACK_H__
#define __AB_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
 
typedef int Data;
typedef struct _arrayStack
{
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;
typedef ArrayStack Stack;
 
void StackInit(Stack * pstack);
    //스택의 초기화를 진행
    //스택 생성 후 제일 먼저 호출되어야 할 함수
int SIsEmpty(Stack * pstack);
    //스택이 빈 경우 TRUE(1), 그렇지 않은 경우 FALSE(0) 반환
void SPush(Stack * pstack, Data data);
    //스택에 데이터 저장, 매개변수 data로 전달된 값을 저장
Data SPop(Stack * pstack);
    //마지막에 저장된 요소를 삭제
    //삭제된 데이터는 반환
    //본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다
Data SPeek(Stack * pstack);
    //마지막에 저장된 요소를 반환하되 삭제하지는 않는다
    //본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야
 
#endif

 

3. 스택의 배열 기반 구현

출처: https://velog.io/@mmindoong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D

• 인덱스 0의 배열 요소가 '스택의 바닥'으로 정의된다
• 마지막에 저장된 데이터의 위치를 기억해야 한다 - topIndex
• 스택 구현 코드 예시

//"ArrayBaseStack.h"
#ifndef __AB_STACK_H__
#define __AB_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
 
typedef int Data;
typedef struct _arrayStack
{
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;
typedef ArrayStack Stack;
 
void StackInit(Stack * pstack);
    //스택의 초기화를 진행
    //스택 생성 후 제일 먼저 호출되어야 할 함수
int SIsEmpty(Stack * pstack);
    //스택이 빈 경우 TRUE(1), 그렇지 않은 경우 FALSE(0) 반환
void SPush(Stack * pstack, Data data);
    //스택에 데이터 저장, 매개변수 data로 전달된 값을 저장
Data SPop(Stack * pstack);
    //마지막에 저장된 요소를 삭제
    //삭제된 데이터는 반환
    //본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다
Data SPeek(Stack * pstack);
    //마지막에 저장된 요소를 반환하되 삭제하지는 않는다
    //본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야
 
#endif
 
 
 
//"ArrayBaseStack.c"
void StackInit(Stack * pstack)
{
    pstack->topIndex = -1;     //-1은 빈 상태를 가리킴
}
 
void SIsEmpty(Stack * pstack)
{
    if(pstack->topIndex == -1)
        return TRUE;
    else
        return FALSE;
}
 
void SPush(Stack * pstack, Data data)
{
    pstack->topIndex += 1;
    pstack->stackArr[pstack->topIndex] = data;
}
 
Data SPop(Stack * pstack)
{
    int rIdx; 
 
    if (SIsEmpty(pstack))
    {
        printf("stack memory error!");
        exit(-1);
    }
    
    rIdx = pstack->topIndex;
    pstack->topIndex -= 1;
    return pstack->stackArr[rIdx];
    
}
 
Data SPeek(Stack * pstack)
{
    if(SIsEmpty(pstack))
    {
        printf("stack memory error!");
        exit(-1);
    }
    
    return pstack->stackArr[pstack->topIndex];
}
 
 
//"ArrayBaseStackMain.c"
#include <stdio.h>
#include "ArrayBaseStack.h"
 
int main(void)
{
    //Stack 생성 및 초기화
    Stack stack;
    StackInit(&stack);
 
    //데이터 넣기
    SPush(&stack, 1); SPush(&stack, 2);
 
    //데이터 꺼내기
    while(!SIsEmpty(&stack))
        printf("%d ", SPop(&Stack));
 
    return 0;
}

 

• 후위 표기법을 이용한 계산기 코드 구현

//"InfixToPostfix.c"
void GetOpPrec(char op)    //연산자의 연산 우선순위 정보를 반환
{
    swith(op)
    {
    case '*':
    case '/':
        return 5;     //가장 높은 연산의 우선순위
    case '+':
    case '-':
        return 3;
    case '(':
        return 1;    //가장 낮은 연산의 우선순위
    }
    
    return -1;         //등록되지 않은 연산자임을 알림
}
 
int WhoPrecOp(char op1, char op2)    //GetOpPrec 함수의 호출결과를 바탕으로 두 연산자의 우선순위를 비교하여 결과 반환하는 함수
{
    int op1Prec = GetOpPrec(op1);
    int op2Prec = GetOpPrec(op2);
    
    if(op1Prec > op2Prec)
        return 1;
    else if(op1Prec < op2Prec)
        return -1;
    else
        return 0;    // op1과 op2의 우선순위가 같다면
}
 
void ConvToRPNExp(char exp[])    //중위표기법을 후위표기법으로 변경하는 함수
{
    Stack stack;         //stack 쟁반 만들기
    StackInit(&stack);
    
    int i, idx = 0
    char tok;
    int expLen = strlen(exp);
    char * convExp = (char*)malloc(expLen+1);     //변환된 수식을 담을 공간 마련
    memset(convExp, 0, sizeof(char)*expLen+1);     //할당된 배열을 0으로 초기화
 
    for(i=0; i<expLen; i++)
    {
        tok = exp[i];
        if(isdigit(tok))    //tok에 저장된 문자가 숫자인지 확인
        {
            convExp[idx++] = tok; //숫자이면 배열 convExp에 그냥 저장
        } 
        else    //숫자가 아닌 연산자라면
        {
            switch(tok)
            {
            case '(':
                SPush(&stack, tok); //여는 소괄호라면 스택에 쌓는다
                break;
            case ')':
                while(1)
                {
                    popOp = SPop(&stack);
                    if (popOp == '(')
                        break;
                    convExp[idx++] = popOp;
                }
                break;
            case '+': case '-':
            case '*': case '/':
                while(!SIsEmpty(&stack) && WhoPrecOp(SPeek(&stack), tok) >= 0)
                    convExp[idx++] = SPop(&stack);
                SPush(&stack, tok);
                break;
            }    
        }
    }
 
    while(!SIsEmpty(&stack))            //스택에 남아있는 모든 연산자를
        conExp[idx++] = SPop(&stack);    //배열 convExp로 이동한다
    strcpy(exp, convExp);                //변환된 수식을 exp에 복사하고,
    free(convExp);                        //convExp는 소멸시킨다
}
 
 
//후위 표기법으로 표현된 수식을 계산하는 프로그램 구현
//1. 피연산자는 무조건 스택으로 옮긴다
//2. 연산자를 만나면 스택에서 두개의 피연산자를 꺼내서 계산을 한다
//3. 계산결과는 다시 스택에 넣는다
int EvalRPNExp(char exp[])
{
    Stack stack;
    int expLen = strlen(exp);
    int i;
    char tok, op1, op2;
 
    StackInit(&stack);
    for (i=0; i<expLen; i++)
    {
        tok = exp[i];
        if(isdigit(tok))
        {
            SPush(&stack, tok-'0') //정수라면 숫자로 변환 후 스택에 push
        }
        else
        {
            op2 = SPop(&stack);
            op1 = SPop(&stack);
            swith(tok)
            {
            case '+':
                SPuch(&stack, op1+op2);
                break;
            case '-':
                SPush(&stack, op1-op2);
                break;
            case '*':
                SPush(&stack, op1*op2);
                break;
            case '/':
                SPush(&stack, op1/op2);
                break;
            }
        }
    }
    return SPop(&stack);    
}