[Data Structure] 5. 스택

이 카테고리에 정리된 내용은 강의시간에 필기한 내용이 주를 이룹니다. 교수님께서 강의 하신 내용들 중에 핵심들과 부가적인 내용들을 요약하여 게시했습니다. 강의시간에 생능출판사의 C언어로 쉽게 풀어쓴 자료구조 책을 사용했기 때문에 정리하는 순서도 이 책의 순서에 따라 하기로 했습니다. 순전히 정리용이기 때문에 시험기간이나 복습용으로는 적절하지만 순수한 학습용으로는 적절하지 않을 수 있습니다.

목록보기

 

5.1 스택 추상 데이터 타입

– 스택(stack) : LIFO(Last In First Out) 구조를 가지고 있는 선형 리스트

– 스택의 용도 : Subroutine Stack(함수호출) – Program Status Word(프로그램 상태 주소) / Interrupt Stack(일시중지) – Interrupt Service Routine(인터럽트 처리 루틴) / Operator Stack(연산자 스택) – infix -> postfix

– 스택 연산의 예 : create(스택생성) / push(삽입) / pop( 삭제) / peek(삭제하지 않고 반환) / is_empty(비어있는지 검사) / is_full(가득 찼는지 검사)

– Program Counter : 다음 수행될 명령어의 주소값을 가짐.

– 연결리스트 스택 : Peepable stack(중간에 빼낼 수 있는 스택).

 

5.5 후위수식의 계산

– infix notation : a+b의 형태. 연산자들 사이에 우선순위가 있고, 괄호를 써야 함.

– prefix notation : +ab의 형태.

– postfix notation : ab+의 형태. 수식을 읽으면서 바로 계산 가능

– unary operator : 피연산자가 한 개 뿐인 것. (ex : -b)

– infix -> postfix : 수식 ((a+((b*c)%d))+e) 일 때, 연산자를 해당 괄호의 바깥으로 빼줌.

과정 :

(b*c) -> bc*

(bc* %d) -> bc*d%

(a+(bc*d%)) -> abc*d%+

((abc*d%+) + e) -> abc*d%+e+

 

* multiple stack : 하나의 공간에 여러 개의 스택을 운용

– repacking algorithm : 공간을 할당하는 방법.

1. 영(0)분배 : Knuth’s 처음 모든 스택의 크기를 0으로 지정. overflow시 할당. 인접노드들의 빈번한 이동 발생. 오버플로우 해결을 위한 최소 공간 할당(1 노드)

2. 균등분배 : 처음 모든 스택들에게 동일한 크기로 공간 할당. 스택에 따라 공간이 낭비되거나 오버플로우가 자주 발행할 수 있음.

3. 차등분배 : 스택들의 이용도를 측정하여 그 비율로 분배. 가장 효율적인 알고리즘이나 스택의 이용도를 정확하게 추정하기 곤란함.

참고 : ( Jan Garwick’s : 균등분배 & 차등분배)

 

 

목록보기