[자료구조] 4장 스택

4-1 스택

1. 스택이란

: 쌓아놓은 더미. 

  → 후입 선출!(LIFO: Last In First Out): 가장 최근에 들어온 데이터가 가장 먼저 나감

2. 스택의 구조

: 스택의 상단(top), 스택의 하단: 불필요, 요소, 항목, 공백 상태, 포화 상태, 삽입, 삭제

3. 스택 추상 자료형(ADT)

데이터: 후입선출의 접근 방법을 유지하는 요소들의 모음
연산(7):
     ⊙ init(): 스택을 초기화.
     ⊙ is_empty(): 스택이 비어있으면 TRUE, 아니면 FALSE를 반환.
     ⊙ is_full(): 스택이 가득 차 있으면 TRUE, 아니면 FALSE를 반환.
     ⊙ size(): 스택 내의 모든요소들의 개수를 반환.
     ⊙ push(x): 주어진 요소 x를 스택의 맨 위에 추가.
     ⊙ pop(): 스택 맨 위에 있는 요소를 삭제하고 반환.
     ⊙ peek(): 스택 맨 위에 있는 요소를 삭제 안하고 반환.

4. 스택의 용도

• 함수 호출(복귀 주소를 스택에 저장)
• Undo 기능
• 괄호 검사
• 계산기
• 미로탐색(dfs: 스택 사용)

4-2 스택의 구현

1. 배열을 이용해 구현

  - 구현

#define MAX_STACK_SIZE		256
int data[MAX_STACK_SIZE];
int top;

  - 연산

    (1) 초기화 연산

void init_stack()
{
    top = -1;
}

    (2) 크기 반환 연산

int size()
{
    return top + 1;
}

    (3) 스택이 비어있는지 확인

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

    (4) 스택이 가득 찼나 확인

int is_fulll()
{
    return (top == MAX_STACK_SIZE - 1);
}

    (5) 삽입 연산

void push(int e)
{
    if(is_full())
        perror("스택 포화 에러");
    data[++top] = e;
}

    (6) 삭제 연산

int pop()
{
    if(is_empty())
        perror("스택 공백 에러");
    return data[top--];
}

    (7) peek 연산

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

    (8) 스택 출력 연산

void print_stack(char msg[])
{
    int i;
    printf("%s[%2d]= ", msg, size());
    for (i=0 ; i<size ; i++)
        print("%2d ", data[i]);
    print("\n");
}

  - 구조체를 저장하는 스택의 예!(학생 정보 스택)

    (1) 학생 정보 스택

typedef struct Student
{
    int id;
    char name[32];
    char dept[32];
} Student;

typedef Student Element;

    (2) 출력 함수 수정

void print_stack(char msg[])
{
    int i;
    printf("%s[%2d]= ", msg, size());
    for(i=0 ; i<size() ; i++)
        printF("\n\t%-15d %-10s %-20s",
            data[i].id, data[i].name, data[i].dept);
    printf("\n");
}

    (3) Student 구조체 입력 받기 

Student get_student(int id, char* name, char* dept)
{
    Student s;
    s.id =id;
    strcpy(s.name, name);
    strcpy(s.dept, dept);
    return s;
}

void main()
{
    init_stack();
    push( get_student(2021920026, "손흥민", "국어국문학과"));
}

2. 연결리스트를 이용해 구현

  - 구현

typedef int Element;
typedef struct LinkNode
{
    Element data;
    struct LinkNode* link;
} Node;

배열과 연결리스트를 이요한 스택의 비교

  - 연산

    (1) 삽입 연산

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

    (2) 삭제 연산

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

    (3) 전체 노드 방문 연산(전체 크기 반환 연산) 

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

4-3 스택의 응용

1. 괄호 검사 프로그램

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함.
• 왼쪽 괄호는 오른쪽 골호보다 먼저 나와야 함.
• 괄호 사이에는 포함 관계만 존재.

 

2. 후위 표기 수식 계산 프로그램

: 쌓아놓은

 

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

: 쌓아놓은