스택이란?
스택이란.
데이터를 일시적으로 쌓아놓는 자료구조를 뜻한다.
데이터 입출력 순서는 후입선출(LIFO: Last In First Out)이다.
데이터를 넣는 작업을 'Push'라고 하고, 꺼내는 작업을 'Pop'이라고 한다.
Push와 Pop이 이루어지는 꼭대기를 'TOP'이라고 하며, 가장 바닥은 'Bottom'으로 칭한다.
위 이미지는 스택의 과정을 이미지로 표현한 이미지이다.
자바 프로그램도 메서드를 호출하고 실행할 때 프로그램 내부에서 스택을 사용한다.
스택만들기
스택을 구현하는 프로그램을 작성해본다. Java에선 Stack클래스가 존재하여, 그것을 사용하면 되지만
자료구조 탐색을 위해 스택을 직접 구현해보려고 한다.
public class IntStack {
private int[] stk; // 스택용 배열
private int capacity; // 용량
private int ptr; // 스택 포인터
// 생성자
public IntStack(int maxlen) {
ptr = 0;
capacity = maxlen;
try {
stk = new int[capacity]; // 스택용 배열 생성
} catch(OutOfMemoryError e) { // 생성할 수 없을 때 예외 처리
capacity = 0;
}
}
// pop을 할때 스택이 비어있을때 예외 발생
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {}
}
// push할때 스택이 가득차 있으면 예외 발생
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() {}
}
}위 코드로 스택을 한번 구현해보았다. 한번 살펴보자
- stk : 푸시된 데이터를 저장하는 스택용 배열이다.
- capacity : 스택의 용량을 나타내는 필드로 stk의 길이도 capacity로 결정한다.
- ptr : 스택에 쌓여있는 데이터의 수를 나타내는 필드로 스택 포인터라고 한다.
스택이 비어있으면 0, 스택이 가득차면 capacity의 값과 동일하다. - 생성자 IntStack : 스택용 배열을 생성하고, 용량을 설정한다. 초기에는 스택이 비어있으므로
스택포인터(ptr)을 0으로 초기화한다. 따라서 배열의 바닥(Bottom)은 인덱스 0이 된다.
외의 예외처리 클래스는 push와 pop을 할때 실행될 수 없는경우에 대한 예외발생을 담당한다.
그렇지만 현재 코드에서는 스택에 Push와 Pop을 수행하는 메서드가 없다. 한번 만들어보자.
Push(추가)
스택에 데이터를 추가하기 위한 작업을 Push라고 한다.
현재 우리 코드에는 스택용 배열에 데이터를 추가할 메서드가 없으니 Push 메서드를 작성해보자.
public int push(int x) throws OverflowIntStackException {
if(ptr >= capacity) { // 스택포인터(저장된 데이터의 갯수)가 용량보다 크거나 같으면 스택이 가득찬 상황
throw new OverflowIntStackException(); // 호출한 곳에 예외를 던진다.
}
return stk[ptr++] = x; // 문제가 없다면 데이터를 추가하고 스택포인터를 증가시킨다.
}예외 처리에 대한 부분만 없다면 1줄로 이루어진 아주 간단한 push 메서드이다.
이번에는 pop을 수행하는 메서드를 작성해보자
Pop(꺼내기)
스택의 꼭대기(Top)에 존재하는 데이터를 제거하면서 그 값을 반환하는 메서드다.
쉽게 말해 스택의 꼭대기에 존재하는 데이터를 꺼내는 작업이다.
데이터를 스택에서 꺼내면 스택에서 Pop한 데이터는 스택 내에서 제거된다.
public int pop() throws EmptyIntStackException {
if(ptr <= 0) { // 스택포인터가 0보다 작거나 같다는 의미는 스택이 비어있다는 의미
throw new EmptyIntStackException(); // 예외를 발생시킨다.
}
return stk[--ptr]; // 문제가 없으면 현재 'Top' 데이터를 반환한다.
}pop 메서드도 마찬가지로 예외 발생에 대한 부분 말고는 1줄로 이루어진 간단한 코드로 작성했다.
pop 메서드를 실행했을때 스택이 비어있지 않다면 데이터를 반환하고 스택포인터를 감소시킨다.
Peek(조회)
이번엔 스택의 꼭대기에 무슨데이터가 존재하는지 조회하는 메서드를 작성해보려 한다.
스택이 비어있는 경우에는 데이터가 존재하지 않기 때문에 예외를 발생시킨다.
public int peek() throws EmptyIntStackException {
if(ptr <= 0) { // 스택이 비어있을때
throw new EmptyIntStackException(); // 예외 발생
}
return stk[ptr - 1]; // 있을땐 'Top'에 존재하는 데이터를 반환한다.
}peek은 말 그대로 스택내 'Top'에 존재하는 데이터를 조회하기 때문에,
스택 포인터의 값을 증감시키지 않고 데이터를 반환만 한다.
Clear(일괄 삭제)
clear 메서드를 작성하여 스택에 모든 데이터를 일괄로 삭제해보자
Pop메서드는 데이터를 꺼냄과 동시에 스택에서 데이터를 삭제하기 때문에 삭제와 출력의 기능을
동시에 수행한다고 생각한다.
clear 메서드는 이와 다르게 스택 내 모든 데이터를 일괄로 삭제하려한다.
public void clear() {
ptr = 0; // 스택포인터를 0으로 만든다는 의미는 스택내 데이터가 없음을 의미한다.
}스택에 데이터를 Push, Pop하는 모든 작업은 스택포인터를 바탕으로 이루어진다.
따라서 스택포인터의 값을 0으로 하면 일괄 삭제와 동일하다.
스택을 이용한 간단한 프로그램 만들기
이전에 만든 스택 클래스를 활용하여 사용하는 간단한 프로그램을 한번 작성해보려 한다.
프로그램은 스택에 push, pop, peek, dump를 수행하는 프로그램을 작성할 것이다.
(dump는 스택내 모든 데이터를 bottom -> top 까지 모두 출력할 것이다.)
Class IntStackTester {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
IntStack s = new IntStack(64); // 최대 64개 데이터를 저장할 수 있는 스택
while(true) {
System.out.println();
// 현재 스택에 저장된 갯수/스택의 저장용량 출력
System.out.printf("현재 데이터 개수: %d / %d\n", s.size(), s.getCapacity());
System.out.print("(1) 푸시 (2) 팝 (3) 피크 (4) 덤프 (0) 종료");
int menu = sc.nextInt();
if(menu == 0) { // 종료선택시 반복 종료하고 프로그램 종료
break;
}
int x;
switch(menu) {
case 1:
System.out.print("데이터 : ");
x = sc.nextInt();
try {
s.push(x);
} catch(IntStack.OverflowIntStackException e) {
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2:
try {
x = s.pop();
} catch(IntStack.EmptyIntStackException e) {
System.out.println("스택이 비어있습니다.");
}
break;
case 3:
try {
x = s.peek;
System.out.println("피크한 데이터는 " + x + "입니다.);
} catch(IntStack.EmptyIntStackException e) {
System.out.println("스택이 비어있습니다.");
}
break;
case 4:
s.dump();
break;
}
}
}
}위와 같이 사용자에게 메뉴를 보여주고 선택한 메뉴에 따라 스택에 있는 데이터를 추가 및 출력등을
할 수 있도록 만들었다. 하지만 4번을 보니 위에서 만들지 않은 dump라는 메서드가 있다.
IntStack 클래스에 추가해주자
public void dump() {
if(ptr <= 0) {
System.out.println("스택이 비어있습니다.");
} else {
for(int i = 0; i < ptr; i++) {
System.out.print(str[i] + " ");
}
System.out.println();
}
}스택이 비어있을때에 대한 처리도 하고, 스택에 들어있는 모든 데이터를 출력할 수 있는 dump 메서드를 추가했다. 이제 다시 프로그램을 실행시키면 정상적인 동작을 할것이다.
