[알고리즘 독학] 스택(Stack)

스택

데이터를 일시적으로 저장하기 위한 자료구조

가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.

 

스택만들기

스택 본체용 배열 : stk

 

스택 용량 : max

 

스택 포인터 : ptr

 

생성자 IntStack

 

푸시 메서드 push

-스택이 가득차서 푸시 할 수 없는 경우 예외 OverflowIntStackException을 던집니다.

 

팝 메서드 pop

-스택이 비어 있어 팝을 할 수 없는 경우 EmptyIntStackException을 던집니다.

 

피크 메서드 peak

-꼭대기에 있는 데이터를 “몰래 엿보는” 메서드

-스택이 비어 있는 경우 예외 EmptyIntStackException을을 던집니다.

 

검색 메서드 indexOf

-검색을 성공면 찾아낸 요소의 인덱스를 반환하고 실패하면 -1을 반환합니다.

 

스택의 모든 요소를 삭제하는 메서드 : clear

 

용량을 확인하는 메서드 : capacity

 

데이터 수를 확인하는 메서드 : size

 

스택이 비어 있는 검사하는 메서드 : IsEmpty

 

스택이 가득 찼는지 검사하는 메서드 : IsFull

 

스택 안에 있는 모든 데이터를 표시하는 메서드 : dump

 

 

 

public class IntStack {
	private int max;	//스택 용량
	private int ptr;	//스택 포인터
	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 (OutOfMemoryError e) {
			max = 0;
		}
	}
	
	//스택에 x를 푸시
	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 peak() throws EmptyIntStackException {
		if(ptr <= 0 )
			throw new EmptyIntStackException();
		return stk[ptr - 1];
	}
	
	
	//스택에서 x를 찾아 인덱스(없으면 -1)를 반환
	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;
	}
	
	//스택의 용량을 반환한다.
	public int capacity() {
		return max;
	}
	
	//스택에 쌓여있는 데이터의 수를 반환
	public int size() {
		return ptr;
	}
	
	
	//스택이 비어있는가?
	public boolean isEmpty() {
		return ptr<= 0;
	}
	
	//스택이 가득 찼는가?
	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.println(stk[i] + " ");
			System.out.println();
		}
	}
	
	
}