[Date Structure] 스택

1. 스택

• Stack : 자료의 입출력이 후입선출(LIFO)의 형태로 일어나는 자료구조
• 스택 상단(Stack top) : 스택에서 입출력이 이루어지는 부분
• 스택 하단(stack bottom) : 반대쪽인 바닥 부분
• 요소(element, 항목) : 스택에 저장되는 것
• 공백(empty) 상태 : 스택에 요소가 하나도 없는 경우
• 포화(full) 상태 : 상태가 꽉 차서 더 이상 요소를 넣을 수 없는 상태

추상 자료형

데이터 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

연산 
  - init() : 스택을 초기화한다.
  - is_empty() : 스택이 비어 있으면 TRUE를 반환하고 아니면 FALSE를 반환한다.
  - is_full() : 스택이 가득 차 있으면 TRUE를 반환하고 아니면 FALSE를 반환한다.
  - size() : 스택 내의 모든 요소들의 개수를 반환한다.
  - push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다.
  - pop() : 스택 맨 위에 있는 요소를 삭제하고 반환한다.
  - peek() : 스택 맨 위에 있는 요소를 삭제하지 않고 반환한다.

2. 배열을 이용한 스택의 구현

• 상수 MAX_STACK_SIZE : 스택에 저장할 수 있는 최대 요소의 개수
• 변수 top : 가장 최근에 입력된 항목의 위치

공백상태 : top = -1

포화상태 : top = MAX_STACK_SIZE - 1

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SZIE 100

// int를 저장하는 스택
typedef int Element;
Element data[MAX_STACK_SZIE];
int top;

// 구조체를 저장하는 스택
typedef struct Student {
   int id;
   char name[32];
   char dept[32];
} Student;
typedef Student Element;
Element data[MAX_STACK_SZIE]

void error(char str[])
{
    printf("%c", str);
    exit(1);
}

void init_stack() {top = -1;}

int is_empty() {return top = -1;}

int is_full() {return top = MAX_STACK_SZIE - 1;}

int size() {return top + 1;}

void push(Element e)
{
    if (is_full())
        error("포화 상태 에러");
    data[++top] = e;
}

Element pop()
{
    if (is_empty())
        error("공백 상태 에러");
    return data[top--];
}

Element peek()
{
    if (is_empty())
        error("스택 공백 에러");
    return data[top];
}

3. 연결 리스트를 이용한 스택의 구현

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

typedef int Element;
typedef struct LinkedNode {
    Element data;
    struct LinkedNode *link;
} Node;
Node* top = NULL;

void error(char* str)
{
    fprintf(stderr, "%s\n", str);
    exit(1);
}

void init_stack() {top = NULL;}

int is_empty() {return top == NULL;}

int size()
{
    Node* p;
    int count = 0;
    for (p = top; p -> link == NULL; p = p -> link) count++;
    return count;
}

void push(Element e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p -> data = e;
    p -> link = top;
    top = p;
}

Element pop()
{
    Node* p;
    Element e;
    if(is_empty())
        error("공백 상태 에러");
    p = top;
    top = p -> link;
    e = p -> data;
    free(p);
    return e;
}

Element peek()
{
    if (is_empty())
        error("공백 상태 에러");
    return top -> data;
}

5. 괄호 검사

C언어 소스 코드에서 사용되는 대괄호 [], 중괄호 {}, 소괄호 ()는 다음 조건을 만족해야 한다.

괄호 검사 알고리즘

• 문자를 저장하는 스택을 준비한다. 처음에는 공색 상태가 되어야 한다.
• 입력 문자열을 하나씩 읽어 왼쪽 괄호를 맍나면 스택에 삽입한다.
• 오른쪽 괄호를 만나면 pop() 연산으로 가장 최근에 삽입된 괄호를 꺼낸다. 이때 스택이 비어 있으면 조건2에 위배된다.
• 꺼낸 괄호가 오른쪽 괄호와 짝이 맞지 않으면 조건3에 위배된다.
• 끝까지 처리했는데 스택에 괄호가 남아 있으면 조건1에 위배된다.

6. 후위 표기 수식의 계산

• 전위 표기법 : 연산자를 피연산자 앞에 표기한다.
• 중위 표기법 : 연산자를 피연산자 사이에 표기한다.
• 후위 표기법 : 연산자를 피연산자 뒤에 표기한다.

컴파일러는 중위 표기 수식을 후위 표기 수식으로 바꾸고, 변환된 후위 표기 수식을 계산한다.

• 괄호를 사용하지 않고도 계산 순서를 알 수 있다.
• 연산자의 우선순위를 고려할 필요가 없다.
• 수식을 읽으면서 바로 계산할 수 있다.

후위 표기 수식의 계산 알고리즘

1. 전체 수식을 왼쪽에서 오른쪽으로 스캔한다.
2. 피연산자가 나오면, 스택에 저장한다.
3. 연산자가 나오면, 스택에서 피연산자 두 개를 꺼내 연산을 수행하고 그 결과를 스택에 저장한다.
4. 이 과정을 반복한다.

7. 중위 표기 수식의 후위 표기 변환

계산기 프로그램을 구현하려면 사람이 입력하는 중위 표기 수식을 후위 표기식으로 변경해야 한다.

후위 표기 변환 알고리즘

1. 입력된 중위 표기 수식을 순서대로 하나씩 스캔한다.
2. 피연산자를 만나면, 바로 출력한다.
3. 연산자를 만나면, 스택에 저장한다.