3. 스택

가장 단순 집어넣고 빼고

뺼 때는 맨 위부터 가능 (마지막에 들어간 것.)

스택이란

• 스택은 마지막에 추가된 요소가 가장 먼저 제거되도록 설계한 선형 데이터 구조
• 후입선출(LIFO : Last In First Out ) - 마지막에 삽입된 요소가 가장 먼저 제거
• 주요 연산으로는 push, pop, peek 등등이 있다

삽입과 삭제가 가장 핵심적인 연산이다.

스택오류 방지 : 스택의 크기를 적절히 관리, 삽입/ 제거를 수행하기 전 스택의 상태 확인

연산 모음

• inti() : 스택을 초기화한다.
• push(e) : 요소 e를 스택의 맨 위에 추가한다.
• pop() : 스택의 맨 위에 있는 요소를 꺼내 반환한다.
• is_empty() : 스택이 비었으면 TRUE를 아니면 FALSE를 반환한다.
• is_full() : 스택이 차있으면 TRUE를 아니면 FALSE를 반환한다.
• peek() : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환한다. (확인 용도)

• 스택이 포화 상태이면 push()가 수행되어도 입력될 수 없으므로 오류가 발생한다. 이를 스택 오버플로우(overflow)라고 한다.
• 스택이 공백이면 pop()이나 peek()를 호출했을 때 삭제나 참조가 불가능하다. 이럴 때 스택 언더플로우(underflow)라고 한다.

스택의 활용 분야

• 되돌리기(undo), ‘이전 페이지 이동’
• 괄호 사용 검사, 계산기 프로그램
• 운영체제에서도 스택을 사용. 함수 호출과 반환을 위해 시스템 스택을 사용.

괄호 사용 검사

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

#define MAX_SIZE 100
typedef char Element;       // 스택 요소 Element의 자료형
#include "ArrayStack.h"     // 스택의 ADT(데이터와 연산) 포함

int check_matching(char expr[])
{
    int i = 0, prev;        // prev는 previous로 이전의 항목을 나타냄

    init_stack();
    while (expr[i] != '\\0') {
        char ch = expr[i++];
        if (ch == '[' || ch == '(' || ch =='{')
            push(ch);
        else if (ch ==']' || ch == ')' || ch == '}') {
            if(is_empty())
                return 2;   //   조건 2 위반

                prev = pop();
                if ((ch==']' && prev != '[')
                || (ch == ')' && prev != '(')
                || (ch == '}' && prev != '{'))
                    return 3;   //  조건 3 위반
        }
    }
    if (!is_empty()) return 1;      //  조건 1 위반
    else return 0;      // 괄호 정상
}

int main()
{
    char expr[4][80] = {
        "{A[(i+1)]=0;}",
        "if((i==0( && (j==0)",
        "while(n<8)){n++};",
        "arr[(i+1]) = 0;,"
    };

    for (int i = 0; i<4 ; i++){
        int errCode = check_matching(expr[i]);
        if (errCode == 0) printf("%-20s -> 정상\\n", expr[i]);
        else printf("%-20s  -> 오류(조건%d 위반)\\n", expr[i], errCode);
    }
    return 0;
}

후위 표기식 프로그램

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef double Element; 
#include "ArrayStack.h"

double eval_postfix(char expr[])
{
    int i = 0;

    init_stack();
    while (expr[i] != '\\0') {        //expr = expression (표현식)
        char c = expr[i++];
        if (c >= '0' && c <= '9') {
            double num = (double)c - '0';
            push(num);
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/') {
            double val2 = pop(); 
            double val1 = pop(); 
            switch (c) {
            case '+': push(val1 + val2); break;
            case '-': push(val1 - val2); break;
            case '*': push(val1 * val2); break;
            case '/': push(val1 / val2); break;
            }
        }
    }
    return pop();
}

int main()
{
    char expr[2][80] = { "8 2 / 3- 3 2 * +", "1 2 / 4 * 1 4 / *" };

    printf("수식 : %s = %lf\\n", expr[0], eval_postfix(expr[0]));
    printf("수식 : %s = %lf\\n", expr[1], eval_postfix(expr[1]));
    return 0;
}