[알고리즘] 스택

스택의 정의

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입출력 순서는 LIFO 이다.

java코드로 스택 구현

public class IntStack {
	//스택의 필드
	private int max; //최대 용량
	private int ptr; //스택에 쌓인 데이터의 개수, index로도 사용
	private int[] stk; //배열본체를 가리키는 변수
	
	//비어있을때를 위한 예외
	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() {}
	}
	//가득찼을때를 위한 예외
	public class OverflowIntStackException extends RuntimeException {
		public OverflowIntStackException() {}
	}
	
	//스택을 만드는 생성자
	public IntStack(int capacity) {
		ptr = 0;
		max = capacity;
		try {
			stk = new int[max];
		} catch(Exception e) {
			max = 0;
		}
	}
	
	//스택에 데이터를 넣음. 넣고나서 ptr은 +1, 넣은 값 반환
	public int push(int x) throws OverflowIntStackException {
		if(ptr>=max) {
			throw new OverflowIntStackException();
		}
		return stk[ptr++] = x;
	}
	
	//스택에서 제일 위에있는 데이터를 꺼냄
	public int pop() throws EmptyIntStackException {
		if(ptr<=0) {
			throw new EmptyIntStackException();
		}
		return stk[--ptr];
	}
	
	//스택에서 현재 쌓여있는 데이터중 가장 위쪽을 훔쳐본다.
	public int peek() throws EmptyIntStackException {
		if(ptr<=0) {
			throw new EmptyIntStackException();
		}
		return stk[ptr - 1];
	}
	
	//x와 같은 값이 스택에 있는지 찾음. 꼭대기부터 바닥 순서로 순차검색
	public int indexOf(int x) {
		for(int i=ptr-1; i>=0; i--) {
			if(stk[i]==x) return i;
		}
		return -1;
	}
	
	//스택을 비움.
	public void clear() {
		ptr = 0;
	}
	
	//스택의 용량(max의값)을 반환
	public int capacity() {
		return max;
	}
	
	//스택에 쌓여있는 데이터의 수(ptr의 값) 반환
	public int size() {
		return ptr;
	}
	
	//스택이 비워져있으면 (ptr이 0 이하이면) true
	public boolean isEmpty() {
		return ptr<=0;
	}
	
	//스택이 가득차있으면 (ptr이 max 이상이면)
	public boolean isFull() {
		return ptr>=max;
	}
	
	//스택의 모든 데이터를 바닥부터 꼭대기 순서로 출력
	public void dump() {
		if(ptr<=0) {
			System.out.println("스택이 비었습니다.");
		} else {
			for(int i=0; i<ptr; i++) {
				System.out.print(stk[i]+" ");
			}
			System.out.println(); 
		}
	}
}