04.스택

4.1 스택이란?

• 스택에 A,B,C,D를 순서대로 입력했다가 하나로 삭제하면 맨 위에 놓여진 D가 삭제된다.
• 이러한 입출력 형태를 후입선출(LIFO:Last-In First-Out)이라고 한다.
• 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.
• 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라고 하고 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 한다.
• 스택에서 저장되는것을 요소(element)라고 부른다.
• 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다.
• 텍스트 에디터에서 "되돌리기(undo)"기능을 구현할 떄 스택을 사용할 수 있다.왜냐하면 수행된 명령어들 중에서 가장 최근에 수행된 것부터 되돌리기를 하여야 하기 때문이다.

예제:시스템 스택을 이용한 함수 호출

• 시스템 스택에서 함수가 호출될 떄마다 활성 레코드(activation record)가 만들어지며 여기에 복귀주소가 저장된다.
• 활성 레코드에는 프로그램 카운터 뿐만 아니라 함수 호출시 매개변수와 함수 안에서 선언된 지역 변수들이 같이 생성된다.
• 함수 호출이 일어나면 항상 시스템 스택에 동일한 방법으로 저장되므로,함수가 자기 자신을 호출하여도 동일한 방법으로 활성 레코드가 만들어졌다가 없어지게 된다.

추상 자료형 스택

• 추상 자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의되며 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다.

    //ADT<STACK>
    객체:0개이상의 원소를 가지는 유한 선형 리스트
    연산:
        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 ERROR_STACKFULL;
            else 스택의 맨 위에 item을 추가한다.
        pop(s) ::=              //삭제연산
            if(is_empty(s))
                return ERROR_STACKEMPTY;
            else 스택의 맨위의 원소를 제거해서 반환한다.
        peek(s) ::=
            if(is_empty(s))
                return ERROR_STACKEMPTY;
            else 스택의 맨 위의 원소를 제거하지 않고 반한한다.

quiz(p.106)

1. 스택과 같은 입출력 형태를 후입선출(LIFO)라고한다.

2. 스택을 사용하여서 a,b,c,d,e를 입력하여서 b,c,e,d,a와 같은 출력을 얻으려면 입력과 출력의 순서를 어떻게 하여야 하는가?

   입력:a,d,e,c,b
   출력:b,c,e,d,a

4.2 스택의 구현

• 스택의 저장되는 요소의 타입은 항상 element라고 가정한다.
• 만약 정수 스택이 필요하면 element타입을 정수로 정의하면 된다.
• 일반적인 경우에는 element타입이 구조체가 될것이다.
• 구조체안에는 무엇이든지 넣을 수 있기 때문이다.

• 스택의 is_empty연산

is_empty(S):
    if top==-1
        then return True
        else return False

• 스택의 is_full연산

is_full(S):
    if top<=(MAX_STACK_SIZE-1)
        then return True
        else return False

• 스택의 push연산

push(S,x):
    if is_full(S)
        then error "overflow"
        else top<-top+1
            stack[top]<-x

• 스택의 pop연산

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

전역변수로 구현하는 방법

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

int main(void){
    push(1);
    push(2);
    printf("%d",pop());
    printf("%d",pop());
    return 0;
}

스택의 요소를 구조체로 하기

#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 main(void){
    element ie={
        2019001,
        "HONG",
        "Seoul"
    };

    element oe;

    push(ie);
    oe=pop();

    printf("학번:%d\n",oe.student_no);
    printf("이름:%s\n",oe.name);
    printf("주소:%s\n",oe.address);
}

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

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

element stack[MAX_STACK_SIZE];
int top=-1;

int main(void){
    StackType s;        //스택이  정적으로 생성된다.

    init_stack(&s);     //함수를 호출할 때 스택의 주소를 전달한다.
    push(&s,1);
    push(&s,2);
    printf("%d",pop(%s));
    printf("%d",pop(%s));
}

스택을 동적 메모리 할당으로 생성하는 방법

#define MAX_STACK_SIZE 100
typedef int element;
typedef struct{
    element *data;
    int capcity;
    int top;
} StackType;

element stack[MAX_STACK_SIZE];
int top=-1;

int main(void){
    StackType *s;
    s=(StackType *)malloc(sizeof(StackType));        //스택이  동적으로 생성된다.

    init_stack(s);     //함수를 호출할 때 스택을 전달한다.
    push(s,1);
    push(s,2);
    printf("%d",pop(s));
    printf("%d",pop(s));
    free(s);
}

quiz(p.116)

1. 스택에서 top의 초기값은 무엇인가? 답:-1
2. 스택에서 top이 가리키는 것은 무엇인가? 답:데이터의 입출력이 이루어지는 부분
3. top이 8이면 현재 스택에 저장된 데이터의 층수는 몇 개인가? 답:9층

4.5 스택의 응용:후위 표기 수식의 게산

• 수식을 표기하는 방법에는 중위(infix),후위(postfix),전위(prefix)의 3가지 방법이 있다.
• 연산자가 피연산자 사이에 있으면 주우이이고 연산자가 피연산자 뒤에 있으면 후위이다.
• 연산자가 피연산자 앞에있으면 전위라고 한다.
• 인간은 주로 중위표기법을 사용하지만 컴파일러는 주로 후위 표기법을 사용한다.
• 프로그래머가 수식을 중위표기법으로 작성하면 컴파일러는 이것을 후위표기법으로 변환한 후에 스택을 이용하여 계산한다.
• 중위표기방법에서는 먼저 계산하여야 할 부분을 나타내기 위하여 괄호를 사용하여야 하는데 비하여 후위 표기 방식에서는 괄호가 필요없어 컴파일러에서 후위 표기방법을 선호한다.
• 후위 표기 수식 계산 알고리즘을 정리해보면 다음과 같다.

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

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

infix_to_postfix(exp):

스택 s를 생성하고 초기화
while (exp에 처리할 문자가 남아있으면)
    ch<-다음에 처리할 문자
    switch(ch)
    case 연산자:
        while(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를 출력

quiz(p.135)

1. 스택을 사용하여서 다음과 같은 중위 수식을 후위 수식으로 변경하고 수식의 값을 계산하는 과정을 그림으로 보여라.

   중위:5*(10+2)%2
   후위:5 10 2 + * 2 %