[자바] 후입선출(LIFO, Last In First Out)의 자료구조 - 스택(Stack)

스택

Stack(겹겹이 쌓다.)

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 후입 선출(LIFO, Last In First Out)로 잘 알려져 있습니다.

스택은 배열 또는 링크드 리스트로 구현할 수 있습니다.

두가지의 차이점은 배열은 스택의 용량이 정해져 있지만, 링크드 리스트는 용량이 정해져 있지 않습니다.

이번 포스팅에서는 배열로 구현을 하지만, 기회가 있다면 링크드 리스트를 이용하여 배열을 구현해보도록 하겠습니다.

 

 

IntStack 생성자

package stack;

public class IntStack {
	
	private int max; // 스택 용량
	private int ptr; // 스택 포인터
	private int[] stk; // 스택 본체
	
	// 실행시 예외 : 스택이 비어있음
	public class EmptyIntStacException extends RuntimeException{
		public EmptyIntStacException() {}
	}
	
	// 실행시 예외 : 스택이 가득 차있음
	public class OverflowIntStacException extends RuntimeException{
		public OverflowIntStacException() {}
	}
	
	public IntStack(int capacity) {
		ptr = 0; // 생성시 포인트는 0
		max = capacity; // 스택 용량 설정
		try {
			stk = new int[capacity]; // 스택 생성
		} catch (OutOfMemoryError e) {
			max = 0;
		}
		
	}
}

스택의 용량(max)은 스택에 데이터를 푸시할 때, 스택이 가득 찼는지 검사하는 요소로 사용되고, 스택의 포인터(ptr)는 스택에서 데이터를 팝할 때, 스택의 최상위 요소를 가져오기 위해 사용됩니다.

 

스택 푸시(push)

public int push(int x) {
		if(ptr >= max) { // 스택이 가득 찼을 때 예외 처리
			throw new OverflowIntStacException();
		}else {
			return stk[ptr++] = x; // 데이터를 저장하고, 포인터를 증가
		}
	}

푸시할 때, 데이터에 저장 후에 포인터를 증가 시키기 때문에 스택이 가득 찼을 때 위와 같이 검사를 수행할 수 있습니다.

 

스택 팝(pop)

public int pop(int x) {
		if(ptr <= 0) { // 스택이 비어 있을 때 예외 처리
			throw new EmptyIntStacException();
		}else {
			return stk[--ptr];	// 포인터를 감소시키고, 데이터 반환		
		}
	}

 

스택 피크(peek)

피크 메서드는 스택의 꼭대기에 있는 최상위 요소를 살펴보는 메서드입니다. 스택은 항상 후입 선출의 자료구조이기 때문에 이러한 메서드가 필요합니다. 스택이 비어있는 경우는 EmptyIntStackException()을 던집니다.

public int peek(int x) {
		if(ptr <= 0){
			throw new EmptyIntStacException();
		}else {
			return stk[ptr - 1];	// 포인터가 변화하지 않고, 데이터 반환		
		}
	}

팝 메서드와 거의 동일하지만, 데이터 리턴 시에 포인터를 변화시키지 않습니다.

 

요소 검색(indexOf)

스택 본체에 데이터가 포함되어 있는지 검사하는 메서드입니다.

스택의 꼭대기부터 바닥 까지 선형적으로 검색을 수행합니다. 검색에 성공하면 해당 인덱스를 반환하고 실패하면 -1을 반환합니다. 꼭대기부터 바닥 쪽으로 검색하는 이유는 후입 선출(LIFO)에 의거하여 데이터를 찾기 위해서입니다.

public int indexOf(int x) {
		for(int i = ptr - 1; i >= 0; i++) { // 꼭대기부터 바닥쪽으로 검색
			if(stk[i] == x) {
				return i;
			}
		}
		return -1;
	}

 

그 외의 스택의 모든 요소를 제거하는 clear(), 용량을 확인하는 capacity(), 스택의 사이즈를 확인하는 size(), 스택이 비어있는지 검사하는 empty(), 가득 찼는지 검사하는 isFull() 등의 메서드가 존재하며, 자신의 취향에 맞게 여러 가지 메서드를 만들면 됩니다. 다만 후입 선출(LIFO)의 규칙만 지키신다면...

 

package stack;

public class IntStack {

	private int max; // 스택 용량
	private int ptr; // 스택 포인터
	private int[] stk; // 스택 본체

	// 실행시 예외 : 스택이 비어있음
	public class EmptyIntStacException extends RuntimeException {
		public EmptyIntStacException() {
		}
	}

	// 실행시 예외 : 스택이 가득 차있음
	public class OverflowIntStacException extends RuntimeException {
		public OverflowIntStacException() {
		}
	}

	public IntStack(int capacity) {
		ptr = 0; // 생성시 포인트는 0
		max = capacity; // 스택 용량 설정
		try {
			stk = new int[capacity]; // 스택 생성
		} catch (OutOfMemoryError e) {
			max = 0;
		}

	}

	public int push(int x) {
		if(ptr >= max) { // 스택이 가득 찼을 때 예외 처리
			throw new OverflowIntStacException();
		}else {
			return stk[ptr++] = x; // 데이터를 저장하고, 포인터를 증가
		}
	}
	
	public int pop(int x) {
		if(ptr <= 0) { // 스택이 비어 있을 때 예외 처리
			throw new EmptyIntStacException();
		}else {
			return stk[--ptr];	// 포인터를 감소시키고, 데이터 반환		
		}
	}
	
	public int peek(int x) {
		if(ptr <= 0){
			throw new EmptyIntStacException();
		}else {
			return stk[ptr - 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;
	}
}