8. 스택(4-2)

 스택의 개요 

 입력과 출력(insertion/deletion) 작업이 리스트(list)의 한 쪽 끝에서만 이루어지는 선형 리스트의 한 형태 

 노드의 입구와 출구가 하나로 입·출력이 한쪽으로 제한된 구조 

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

 스택(Stack)의 구조 

 스택 (Stack)의 동작-1 

 스택 (Stack)의 동작-2 

 스택에서 사용되는 용어 

 TOP 포인터(SP : stack pointer)  

 스택에 대한 PUSH와 POP이 이루어질 위치 

 BOTTOM  

 Top의 반대쪽으로 노드의 입출력이 허용되지 않는 위치 

 삽입(insertion) : PUSH (push down)      

 스택에서 새로운 노드의 입력(TOP = TOP + 1) 

 삭제(deletion) : POP(pop up) 

 스택에서 노드의 삭제(TOP = TOP - 1) 

 오버플로우(overflow) 

 스택이 가득차 있을 때(TOP = n),  

새로운 노드의 삽입이 일어나서 스택에 더이상 삽입을 할 수 없는 경우 

즉, TOP > n인 경우를 말한다. 

 언더플로우(underflow) 

 스택이 비어 있을 때(TOP = 0), 새로운 노드의 삭제가 일어나서,   

더이상 삭제를 할 수 없는 경우.  즉, TOP < 0인 경우 

 스택의 이용 

 부프로그램(sub progrqam)의 복귀주소(return address) 보관 

 산술식의 해석을 통한 기계명령 코드의 생성 순서 결정(infix→postfix) 

 재귀적 호출(recursive call) 또는 되부름(recursion) 알고리즘의 구현 

 그래프(graph)의 깊이우선탐색(depth first search) 알고리즘의 구현 

 정렬(sorting)의 퀵 정렬(quick sorting) 알고리즘의 구현 

 스택에서 사용되는 연산 

 Insertion(item, stack, TOP) 

 Deletion(item, stack, TOP) 

 Top(stack) 

 IsEmpty(stack) 

 스택이 비어있는지의 여부를 확인한다. 

 bottom < T ≤ TOP 

여기서,  T는 스택 범위의 주소이다. 

 스택의 삽입과 삭제 

 [알고리즘 1] 스택의 삽입 

if  TOP=n  then  overflow Exit 

TOP ← TOP + 1 

stack[TOP ] ← insert_data 

 

 [알고리즘 2] 스택의 삭제 

if TOP=0 then  underflow  Exit 

delete_data ← Stack[ TOP ] 

TOP ← TOP - 1 

2. 스택에서 오버플로 발생 시 해결방법 

 다중 스택(multi-stack)을 이용하는 방법 

 리패킹(repacking)을 이용하는 방법 

 다중 스택(multi-stack)을 이용하는 방법 

 스택 2개를 연결하여 유용 공간을 사용하는 방법으로,  

 TOP1 = TOP2일 때에는 역시 오버플로우가 발생된다.  

 이때 BOTTOM은 고정되어 있다. 

 리패킹(repacking)을 이용하는 방법 

 다중 스택을 이용하여도 오버플로우가 발생하였을 때, n개의 스택을  

    사용하여 TOP과 BOTTOM의 이동을 자유롭게 하여 오버플로우를 줄일 수 있는 방법 

 저장 공간의 기본 주소 : L0 에서부터 L∞까지 

 각각의 스택을 1, 2, 3, …, n의 번호로 구별한다. 

 스택이 빈 상태 : t[i] = b[i] 

 스택이 오버플로우인 상태 : t[i] = b[i+1]로 비교  확인