이론 적인 것은 잘 정리된 글이 많기 때문에 생략.
java로 int 형 stack과 Object형 stack을 구현한 코드.
int 형을 저장하는 스택
public class IntStack {
// 스택용 배열
private int[] stk;
// 스택 용량
private int capacity;
// 스택 포인터
private int ptr;
// 실행 시 예외 : 스택이 비어있는 경우
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException(){}
}
// 실행 시 예외 : 스택이 가득 찬 경우
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException(){}
}
// 생성자
public IntStack(int maxLen) {
ptr = 0;
capacity = maxLen;
try {
// 스택 본채용 배열 생성
stk = new int[capacity];
} catch (OutOfMemoryError e) {
// 생성할 수 없음
capacity = 0;
}
}
// 스택에 X를 푸시
public int push(int x) throws OverflowIntStackException {
if (ptr >= capacity)
// 스택이 가득 찬 경우
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];
}
// 스택을 비움
public void clear() {
// 모든 작업이 ptr 값으로 이루어 지므로 배열의 요소를 변경할 필요가 없음.
ptr = 0;
}
// 스택에서 X 찾아 인덱스 반환, 없다면 -1 반환
public int indexOf(int x) {
// 뒤(꼭대기)에서 부터 선형 탐색
for (int i = ptr - 1; i >= 0; i--) {
if (stk[i] == x)
// 검색 성공
return i;
}
// 검색 실패
return -1;
}
// 스택의 용량 반환
public int getCapacity() {
return this.capacity;
}
// 스택에 쌓여있는 데이터 개수 반환
public int size() {
return ptr;
}
// 스택이 비어있는지 확인
public boolean isEmpty() {
return ptr <= 0;
}
// 스택이 가득 찼는지 확인
public boolean isFull() {
return ptr >= capacity;
}
public void dump() {
if (ptr <= 0)
System.out.println("EMPTY STACK");
else {
for (int i = 0; i < ptr; i++)
System.out.print(stk[i] + " ");
System.out.println("");
}
}
}Object 형을 저장하는 스택
// 임의의 객체형을 쌓을 수 있는 테네릭 스택 클래서 Stack<E> 작성
public class GenericStack<E> {
// 스택용 배열
private E[] stk;
// 스택 용량
private int capacity;
// 스택 포인터
private int ptr;
// 실행 시 예외 : 스택이 비어있는 경우
public static class EmptyGStackException extends RuntimeException {
public EmptyGStackException(){}
}
// 실행 시 예외 : 스택이 가득 찬 경우
public static class OverflowGStackException extends RuntimeException {
public OverflowGStackException(){}
}
// 생성자
public GenericStack(int maxLen) {
ptr = 0;
capacity = maxLen;
try {
// 스택 본채용 배열 생성
stk = (E[])new Object[capacity];
} catch (OutOfMemoryError e) {
// 생성할 수 없음
capacity = 0;
}
}
// 스택에 X를 푸시
public E push(E x) throws OverflowGStackException {
if (ptr >= capacity)
// 스택이 가득 찬 경우
throw new OverflowGStackException();
return stk[ptr++] = x;
}
// 스택에서 데이터를 팝 (꼭대기에 있는 데이터를 꺼냄)
public E pop() throws EmptyGStackException {
if (ptr <= 0)
// 스택이 비어 있음
throw new EmptyGStackException();
return stk[--ptr];
}
// 스택에서 데이트를 피크 (꼭대기에 있는 데이터 조회)
public E peek() throws EmptyGStackException {
if (ptr <= 0)
// 스택이 비어 있음
throw new EmptyGStackException();
return stk[ptr - 1];
}
// 스택을 비움
public void clear() {
// 모든 작업이 ptr 값으로 이루어 지므로 배열의 요소를 변경할 필요가 없음.
ptr = 0;
}
// 스택에서 X 찾아 인덱스 반환, 없다면 -1 반환
public int indexOf(Object x) {
// 뒤(꼭대기)에서 부터 선형 탐색
for (int i = ptr - 1; i >= 0; i--) {
if (stk[i].equals(x))
// 검색 성공
return i;
}
// 검색 실패
return -1;
}
// 스택의 용량 반환
public int getCapacity() {
return this.capacity;
}
// 스택에 쌓여있는 데이터 개수 반환
public int size() {
return ptr;
}
// 스택이 비어있는지 확인
public boolean isEmpty() {
return ptr <= 0;
}
// 스택이 가득 찼는지 확인
public boolean isFull() {
return ptr >= capacity;
}
public void dump() {
if (ptr <= 0)
System.out.println("EMPTY STACK");
else {
for (int i = 0; i < ptr; i++)
System.out.print(stk[i] + " ");
System.out.println("");
}
}
}728x90
반응형
'Computer Science > DataStructure' 카테고리의 다른 글
| [DS] Array 배열 (0) | 2022.07.17 |
|---|
