Week02_Stack

1. 스택이란?

 

1) 개념

- 선형구조

- 사전적 의미 : 물건이 쌓여 있는 더미

 

2) 구조

- top : 스택의 가장 윗부분

- bottom : 스택의 가장 아랫부분

- element : 스택에 저장되는 것

- 입출력은 맨 위에서만 일어나고 중간에서는 데이터를 삭제할 수 없음

 

3) 특징

- 후입선출 : LIFO(Last-In First-Out)

→ 가장 최근에 들어온 입력이 가장 먼저 나가게 됨

      ex) ① PUSH 연산 : 새로운 자료를 스택에 추가하는 과정

           ② POP 연산 : 스택에 저장된 자료를 가져오는 과정

                    → 자료 제거 및 가져오기 연산이 동시에 수행

 

 

2. 추상 자료형 스택

 

- 스택(s)

① 객체 : 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 스택의 맨 위의 원소를 제거하지 않고 반환

 

 

3. 스택 구현

 

- 전역 변수로 구현하는 방법

 

#define MAX_STACK_SIZE 100 // 스택의 최대 크기 typedef int element; // 데이터의 자료형 element stack[MAX_STACK_SIZE]; // 1차원 배열 int top = -1;

→ 배열, top 변수를 함수의 매개변수로 전달할 필요 없음

→ 단점 : 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기 어려움

 

- 스택의 요소 : 구조체로 정의

 

typedef struct { int student_no; char name[MAX_STRING]; char address[MAX_STRING]; } element;

 

- 동적 메모리 할당으로 스택 생성

 

int main(void) { StackType *s; s = (StackType *)malloc(sizeof(StackType)); ... }

 

 

4. 스택의 응용 – 괄호 검사 문제

 

1) 문제

- 프로그램에서 사용되는 괄호가 올바르게 사용되었는지를 스택을 사용하여 검사하는 프로그램

 

2) 검사 조건

- 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같음

- 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함

- 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안됨

 

3) 괄호 검사 알고리즘

 

check_matching(expr): while(입력 expr의 끝이 아니면)       ch <- expr의 다음 글자       switch(ch)       case ‘(’ : case ‘[’ : case ‘(’ :             ch를 스택에 삽입             break;       case ‘}’ : case ‘]’ : case ‘)’ :             if (스택이 비어 있으면)                   then 오류             else 스택에서 open_ch를 꺼내기       if (ch와 open_ch가 ᄍᆞᆨ이 아니면)             then 오류 보고             break; if(스택이 비어있지 않으면)       then 오류