스택이란?
◽ 데이터를 일시적으로 저장하기 위해 사용하는 자료구조
◽ 데이터의 입력과 출력 순서는 후입선출(LIFO)
스택 구현하기
본체 만들기
class IntStack {
int max; // 스택 용량
int ptr; // 스택 포인터
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;
}
}
◽ 스택 용량 (max) : 스택에 쌓을 수 있는 최대 데이터 수
◽ 스택 포인터 (ptr) : 스택에 쌓여 있는 데이터 수
푸시 메서드 push
// 스택에 x를 푸시
public int push(int x) throws OverflowIntStackException {
if (ptr >= max)
throw new OverflowIntStackException();
return stk[ptr++] = x;
}
◽ 스택에 데이터를 푸시하는 메서드
◽ 스택이 가득 차서 푸시할 수 없는 경우에는 예외처리를 한다.
팝 메서드 pop
// 스택에서 데이터를 팝 (정상에 있는 데이터를 꺼냄)
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
◽ 스택의 꼭대기에서 데이터를 제거하고 그 값을 반환한다.
◽ 스택이 비어 있어 팝을 할 수 없는 경우 예외처리를 한다.
피크 메서드 peek
// 스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄)
public int peek() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}
◽ 가장 꼭대기에 있는 데이터가 무엇인지 반환만 해준다.
검색 메서드 indexOf
// 스택에서 x를 찾아 인덱스(없으면 -1)를 반환
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) // 정상 쪽에서 선형 검색
if (stk[i] == x)
return i; // 검색 성공
return -1; // 검색 실패
}
◽ 스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드이다.
◽ 배열 인덱스가 큰 쪽에서 작은 쪽으로 스캔하며, 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다.
스택의 모든 요소를 삭제하는 메서드 clear
// 스택을 비움
public void clear() {
ptr = 0;
}
용량을 확인하는 메서드 capacity
// 스택의 용량을 반환
public int capacity() {
return max;
}
데이터 수를 확인하는 메서드 size
// 스택에 쌓여 있는 데이터 수를 반환
public int size() {
return ptr;
}
스택이 비어 있는지 검사하는 메서드 isEmpty
// 스택이 비어 있는가?
public boolean isEmpty() {
return ptr <= 0;
}
스택이 가득 찼는지 검사하는 메서드 isFull
// 스택이 가득 찼는가?
public boolean isFull() {
return ptr >= max;
}
스택 안에 있는 모든 데이터를 표시하는 메서드 dump
// 스택 안에 있는 데이터를 바닥에서 꼭대기 순서로 출력
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();
}
}
'Data Structure' 카테고리의 다른 글
배열로 집합 만들기 (0) | 2021.12.13 |
---|---|
재귀 알고리즘 (0) | 2021.11.30 |
큐 (0) | 2021.11.29 |
검색 (0) | 2021.11.24 |
배열 (0) | 2021.11.22 |