스택 Stack
Top이라고 하는 한쪽 끝에서 모든 삽입(Push)과 삭제(Pop)가 일어나는 순서 리스트
스택 $S=(a_0, ...., a_{n-1})$: $a_0$는 bottom, $a_{n-1}$은 top 원소
$a_i$는 원소 $a_{i-1} (0<i<n)$의 위에 있음
후입선출(LIFO, Last-In-First-Out)리스트
스택의 한 예: 시스템 스택
프로그램 실행 시 함수 호출을 처리
함수 호출시 활성 레코드(activation record) 또는 스택 프레임(stack frame) 구조 생성
이전의 스택 프레임에 대한 포인터
복귀 주소
지역 변수
매개 변수
함수가 자기자신을 호출하는 순환 호출도 마찬가지로 처리
순환 호출시마다 새로운 스택 프레임 생성
최악의 경우 가용 메모리 전부 소모
시스템 스택
주 함수(main function)가 함수 func1을 호출하는 예
스택 구현
일차원 배열 stack 사용
i 번째 원소 stack[i-1]에 저장
변수 top은 스택의 최상위 원소를 가리킴
The Stack Abstract Data Type
class Stack <T> {
private T[] stack; // array for stack elements
private int top; // array position of top element
private int capacity; // capacity of stack array
Stack(int stackCapacity) throws Exception {
capacity = stackCapacity;
if(capacity < 1) throw new Exception ("Stack capacity must be > 0");
stack = (T []) new Object [capacity];
top = -1;
}
boolean IsEmpty(){
return (top == -1);
}
// Return top element of stack
T Top() throws Exception {
if(IsEmpty()) throw new Exception("Stack is empty");
return stack[top];
}
/** * Insert item into the top of the stack */
void Push(T item) throws Exception {
if (top == capacity -1) {
throw new Exception("Stack is full")
}
stack[++top] = item;
}
void Pop() throws Exception {
if (IsEmpty()) {
throw new Exception("Stack is empty. Cannot delete.");
}
top--;
};