[자료구조] 스택(Stack)

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

스택(stack)

• 후입 선출(LIFO : Last-In First-Out)의 입출력 형태를 갖는다.
  자료의 출력 순서가 입력 순서의 역순이어야 할 때 많이 사용된다.
• 입출력이 맨 위에서만 일어나고 스택의 중간에서는 데이터 삭제가 불가능하다.

    요소(element)  : 스택에 저장되는 것

     공백 스택(empty 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 스택의 맨 위의 원소를 제거하지 않고 반환

• push : 삽입 연산. 요소가 스택의 가장 위에 쌓인다. (스택이 가득 차면 오류)
• pop : 삭제 연산. 가장 위에 쌓여있는 요소가 삭제되면서 반환된다. (스택이 비어있으면 오류)
• peek : 가장 위에 있는 요소를 읽어오는 연산 (삭제가 일어나지 X)
• is_empty : 스택이 공백 상태인지 검사
• is_full : 스택이 포화 상태인지 검사
• create : 스택 생성
• init : 스택 초기화

 

 

 

스택 구현 방식

	배열 이용	연결 리스트 이용
장점	구현이 간단하고 성능이 우수	배열에 비해 구현이 복잡
단점	스택 크기가 고정됨	스택의 크기를 가변적으로 사용할 수 있음

 

 

 

스택응용

• 괄호 검사
• 후위 표기 수식의 계산
• 미로 찾기