04-1 스택(Stack)
이번엔 데이터를 일시적으로 보관하는 자료구조인 스택에 대해 아라보자
스택이란?
데이터를 일시적으로 쌓아놓는 자료구조로,데이터의 입력과 출력 순서는 후입선출. 즉 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 방식
사용 사례
- 음료수 진열대 (먼저 들어간게 나중에 나옴)
- 인터넷 브라우저 창(뒤로가기,앞으로 가기)
🎂 스택 만들기
public class InStack {
private int[] stk;
private int ptr;
private int capacity;
//예외 : 빈 스택
public class EmptyInStackException extends RuntimeException {
public EmptyInStackException() {
}
}
//예외 : 가득 찬 스택
public class OverflowInStackException extends RuntimeException {
public OverflowInStackException() {
}
}
//생성자
public InStack(int maxlen) {
ptr = 0;
capacity = maxlen;
try {
stk = new int[capacity]; // 스택 본체용 배열 생성
} catch (OutOfMemoryError error) { // 생성할 수 없음
capacity = 0;
}
}스택용 배열 stk
- 푸쉬된 데이터를 저장하는 스택용 배열
- 가장 먼저 푸쉬된 데이터를 저장하는 곳은 stk[0]이다.
스택용량 capacity
- 스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타내는 int형 필드.
스택 포인터 ptr
- 스택에 쌓여있는 데이터 수를 나타내는 필드
- 스택이 비어있으면 ptr값은 0이 된다.
- 가득 차 있으면 capacity값과 같다.
- 가장 나중에 푸쉬된 꼭대기 데이터는 stk[ptr-1]이다
생성자 InStack
- 스택용 배열 본체를 생성하는 등 준비 작업을 한다.
- 생성할 때 스택은 비어있다.(ptr=0)
- 매개변수 maxlen으로 전달 받은 값을 스택 용량을 나타내는 capacity에 대입 -> 요솟수가 capaticy인 배열 본체 생성
⛔️ 푸쉬/팝 (예외 처리)
// 스택에 x를 푸쉬
public int push(int x) throws OverflowInStackException {
if (ptr >= capacity) {
throw new OverflowInStackException();
}
return stk[ptr++] = x;
}
// 스택에서 맨위 데이터를 팝(꺼내다)
public int pop() throws EmptyInStackException {
if (ptr <= 0) {
throw new EmptyInStackException();
}
return stk[--ptr];
}푸쉬 메서드
- 스택에 데이터를 푸쉬하는 메서드
- 스택이 가득 차서 더 이상 푸쉬 불가시 예외 OverflowInStackException 내보냄
- 실행 된다면,전달받은 데이터 x를 stk[ptr]에 저장하고 스택 포인터 1증가
팝 메서드
- 꼭대기 데이터를 팝(제거)하고 그 값을 리턴하는 메서드
- 스택이 비어 있어서 팝(제거) 불가시 예외 EmptyInStackException 내보냄
- 실행 된다면, 먼저 스택 포인터 ptr값을 1 감소 시키고 그때 stk[ptr]에 저장되어 있는 값을 반환
👀 peek / clear / indexOf / getCapacity
//스택에서 데이터를 피크(꼭대기에 있는 데이터를 봄)
public int peek() throws EmptyInStackException {
if (ptr <= 0) {
throw new EmptyInStackException();
}
return stk[ptr - 1];
}
//스택을 비움
public void clear() {
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 capacity;
}peerk(피크) 메서드
- 스택의 꼭대이게 있는 데이터를 들여다보는 메서드
- 비어있을시 예외 처리
clear 메서드
- 스택에 쌓여 있는 모든 데이터를 한번에 삭제
indexOf 검색 메서드
- 스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지 조사
getCapacity 용량 확인 메서드
- 스택의 용량을 반환하는 메서드. capaticy값 그대로 반환
📠 size / isEmpty / isFull / dump
//스택에 쌓여있는 데이터의 개수 반환
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("스택이 비어있습니다.");
} else {
for (int i = 0; i < ptr; i++) {
System.out.println(stk[i] + " ");
}
System.out.println();
}
}데이터의 개수를 확인하는 size 메서드
- 현재 스택에 쌓여 있는 데이터 개수(ptr)를 반환하는 메서드
스택이 비어 있는지 검사하는 메서드 isEmpty
- 스택이 비어 있으면 true,그렇지 않으면 false
스택이 가득 찼는지 검사하는ㄴ 메서드 isFull
- 스택이 가득 았으면 true, 그렇지 않으면 false
스택 안에 있는 모든 데이터를 출력하는 메서드 dump
- 스택에 쌓인 모든 데이터를 바닥부터 꼭대기 순으로 출력하는 메서드
🎮 스택을 사용하는 프로그램
public class IntStackTester {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
InStack s = new InStack(64);
while (true) {
System.out.println();
System.out.printf("현재 데이터의 개수: %d / %d\n", s.size(), s.getCapacity());
System.out.println("(1)푸시 (2)팝 (3)피크 (4)덤프 (5)데이터 찾기 (6)모든 데이터 삭제 (7)데이터 정렬 (0)종료");
int menu = sc.nextInt();
if (menu == 0) {
break;
}
int x;
switch (menu) {
case 1:
System.out.println("데이터 : ");
x = sc.nextInt();
try {
s.push(x);
} catch (InStack.OverflowInStackException e) {
System.out.println("데이터가 가득 찼습니다.");
}
break;
case 2:
try {
s.pop();
} catch (InStack.EmptyInStackException e) {
System.out.println("데이터가 비어 있습니다.");
}
break;
case 3:
try {
s.peek();
} catch (InStack.EmptyInStackException e) {
System.out.println("데이터가 비어 있습니다.");
}
break;
case 4:
s.dump();
break;
case 5:
System.out.println("검색할 데이터 : ");
x = sc.nextInt();
int n = s.indexOf(x);
if (n >= 0) {
System.out.println("그 데이터는 꼭대기에서+[" + (s.size() - n) + "째에 있습니다.");
} else {
System.out.println("그 데이터는 없습니다.");
}
break;
case 6:
System.out.println("데이터를 지웁니다.");
s.clear();
break;
case 7: // 데이터 출력
System.out.println("용량 : " + s.getCapacity());
System.out.println("데이터 수 : " + s.size());
System.out.println("비어" + ((s.isEmpty()) ? "있습니다" : "있지 않습니다."));
System.out.println("가득" + ((s.isFull()) ? "차 있습니다" : "차 있지 않습니다."));
break;
}
}
}
}
🗓 2022/11/22(화) 느낀점
스택/큐라고 해서 뭔가 엄청 거창하고 빡세보였는데 생각보다 이해도 잘되고 별 큰 일이 없었다 사용 예시를 보면서 공부하면 더 좋을 듯한다.
퇴사 후 첫날인데 더 부지런히 움직일 수 있도록 스스로 채찍질 해야겠다
걍 하자 저스트 뚜잇