스택(Stack)

[Stack(스택)]

→ 데이터를 일시적으로 보관하는(==쌓아놓는) 자료구조

 

특징

1. LIFO (후입선출) → 마지막에 넣은 데이터를 가장 먼저 꺼냄
2. PUSH(넣기), POP(꺼내기)
3. PUSH와 POP이 이루어지는 꼭대기를 top이라고 하고, 스택의 가장 아랫부분을 bottom이라고 한다.

예시

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

해당 사진은 자바 프로그램에서 메서드가 호출될 때 순서에 따라 스택이 사용되고 있음을 알 수 있다.

 

 

1. main() 먼저 실행되므로 main() 먼저 push
2. main() 안에서 z()를 호출하므로 z() push,
3. z() 안에서 x(), y() 순대로 호출하므로 x() push했다가 pop, y() push했다가 pop
4. x, y가 모두 호출되고 끝나면 z()도 pop,
5. 마지막으로 main()까지 pop하면 모든 메서드 호출 과정이 완료된다.

→ 호출한 메서드의 역순으로 차례대로 쌓여 있어 메서드 호출이 계층 구조로 이루어져 있음을 알 수 있다.

---

[스택 구현하기]

public class IntStack {

	private int[] stk; // 스택용 배열
	private int capacity; // 스택의 최대 용량
	private int ptr; // 스택 포인터 (스택에 쌓여있는 데이터 수)
	// 가득차면 capacity의 값과 같다.

	// 스택이 비어있을 경우 예외 발생
	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() {}
	}
	// 스택이 가득 찼을 경우 예외 발생
	public class OverflowIntStackException extends RuntimeException {
		public OverflowIntStackException() {};
	}

	// 스택을 안전하게 초기화하기 위한 생성자
	// 생성자가 없을 시 일일이 모든 요소를 초기화해주어야 하기 때문에 사용
	public IntStack(int maxlen) {
		// 생성자니까 이름은 클래스 이름과 같음
		ptr = 0; // 스택에 쌓여있는 데이터 수를 0으로 초기화
		capacity = maxlen; // 최대 길이를 매개변수로 입력받음
		try { // 예외 발생 시 예외처리
			stk = new int[capacity]; // 최대 크기 입력받아서 배열 생성
		} catch (OutOfMemoryError e) { // 예외 발생 시 
			capacity = 0; // 용량 0으로 처리
		}
	}
}

---

1. OutOfMemoryError가 무엇인가?
   메모리가 부족할 때 발생하는 에러. 너무 큰 배열을 만드려고 하거나, 메모리를 과도하게 사용했을 경우 발생. 너무 큰 배열을 만들면 힙 메모리 공간이 부족해져서 해당 에러가 발생한다.

    2. 에러 발생 시 capacity = 0으로 설정하는 이유
         배열 생성에 실패했다면 스택 자체가 정상 동작할 수 없음. 이때 capacity를 0으로 설정해두면 pop/push 등으로 인해 발생하는 비정상 작동을 미리 막을 수 있다.
         ⇒ 즉, 오류 상태임을 알리는 방어 로직!