스택(Stack)

데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO: Last In First Out)이다.
나중에 넣은 데이터를 가장 먼저 꺼낸다.
push : 데이터를 넣음, pop : 데이터를 꺼냄

void x() {}
void y() {}
void z() {
	x();
    y();
}
void main() {
	z();
}
//만약 위의 코드가 있다면 스택을 사용하여
//아래 처럼 흐른다.

자바 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서 스택을 사용한다.
main push	z push	x push	x pop	y push	y pop	z pop
		x		y
	z	z	z	z	z
main	main	main	main	main	main	main

---

스텍 만들기

public class IntStack {
	private int[] stk;	//스택용 배열
    private int capacity;	//스택 용량
    private int ptr;	//스택 포인터
    //실행 시 예외 : 스택이 비어 있음
    public class EmptyIntStackException extends RuntimeException {
    	public EmptyIntStackException() {}
    }
    //실행 시 예외 : 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
    	public OverflowIntStackException() {}
    }
    //생성자
    public IntStack(int maxlen) {
    	ptr = 0;
        capacity = maxlen;
        try {
        	stk = new int[capacity];	//스택 본체용 배열을 생성
        } catch(OutOfMemoryError e) {	//생성할 수 없음
        	capacity = 0;
        }
    }

 

• 스택용 배열 stk : 푸시된 데이터를 저장하는 스택용 배열
• 스택 용량 capacity : 스택의 용량(최대 데이터 수)을 나타내는 int형 필드
• 스택 포인터 ptr : 스택에 쌓여 있는 데이터 수를 나타내는 필드
• 생성자 IntStack : 스택용 배열 본체를 생성하는 등 준비 작업

//스택에 x push
public int push(int x) throws OverflowIntStackException {
	if(ptr >= capacity)
    	throw new OverflowIntStackException();
    return stk[ptr++] = x;
}
//스택에서 데이터를 팝(꼭대기에 있는 데이터를 끄냄)
public int pop() throws EmptyIntStackException {
	if(ptr <= 0)
    	throw new EmptyIntStackException();
    return stk[--ptr];
}

• 푸시 메서드 push : 데이터를 넣고 가득 차 있는 경우 예외 OverflowIntStackException을 내보냄
• 팝 메서드 pop : 스택 꼭대기에 있는 데이터를 제거하고 그 값을 반환, 비어있는 경우 EmptyStackException을 내보냄
• 피크 메서드 peek : 스택의 꼭대기에 있는 데이터를 들여다보는 메서드, 비어있는 경우 EmptyStackException을 내보냄

public int peek() throws EmptyIntStackException {
	if(ptr <= 0)
    	throw new EmptyIntStackException();
    return stk[ptr - 1];
}

• 스택의 모든 요소를 삭제 clear

public void clear() {
	ptr = 0;
}

• 검색 메서드 indexOf

//스택에서 x를 찾아 인덱스(없으면 -1) 반환
public int indexOf(int x) {
	for(int i=ptr -1; i>=0; i--) {	//꼭대기부터 선형 검색
    	if(stk[i] == x) {
        	return i;	//검색 성공
        }
        return -1;	//검색 실패
    }
}
//스택 용량을 반환
public int getCapacity() {
	return capacity;
}

• 용량을 확인하는 메서드 getCapacity
• 데이트 개수를 확인하는 메서드 size
• 스택이 비어있는지 검사하는 메서드 isEmpty
• 스택이 가득 찼는지 검사하는 메서드 isFull
• 스택 안에 있는 모든 데이터를 출력하는 메서드 dump

//스택 데이터 개수
public int size() {
	return ptr;
}
//스택 비어있어?
public boolean isEmpty() {
	return ptr <= 0;
}
//스택 가득이야?
public boolean isFull() {
	return ptr >= capacity;
}
//스택 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
public void dump() {
	if(ptr <= 0)
    	System.out.println("스택이 비어있다");
    else {
    	for(int i=0; i<ptr; i++) 
        	System.out.println(stk[i] + " ");
        System.out.println();
	}
}