스택이란?
스택(stack)은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out) 구조로 이루어진다. 스택에 데이터를 넣는 작업을 push라 하고, 데이터를 꺼내는 작업을 pop이라고 한다. push와 pop은 스택의 꼭대기(top)에서 이루어지며, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.
자바에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다.
void x() { /* ... */ }
void y() { /* ... */ }
void z() {
x();
y();
}
int main() {
z();
}
위 그림은 main 메서드를 포함하여 총 4개의 메서드로 이루어져 있다.
ⓐ main 메서드가 실행되기 전의 상태
ⓑ main 메서드가 실행되어 스택에 적재된 상태
ⓒ main 메서드에서 z 메서드를 호출한다.
ⓓ x 메서드를 호출한다.
ⓔ x 메서드가 실행을 종료하고 z 메서드로 돌아온다.
ⓕ y 메서드를 호출한다.
ⓖ y 메서드가 실행을 종료하고 z 메서드로 돌아온다.
ⓗ z 메서드가 실행을 종료하고 main 메서드로 돌아온다.
ⓘ main 메서드가 실행을 종료한다.
스택 구현하기
아래 코드는 int형 데이터 타입을 저장하는 스택을 구현하는 코드이다.
public class IntStack {
private int max; // 스택 크기
private int ptr; // 스택 포인터
private int[] stk; // 스택 본체
// 스택이 비어있을 경우 실행 시 예외처리
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {}
}
// 스택이 가득찼을 경우 실행 시 예외처리
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() {}
}
// 생성자
public IntStack(int max) {
ptr = 0;
this.max = max;
try {
stk = new int[max]; // 스택 본체용 배열 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
max = 0;
}
}
// 스택에 x를 push
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(top에 위치한 데이터를 들여다 봄)
public int peek() throws EmptyIntStackException {
if(ptr<=0) {
throw new EmptyIntStackException();
}
return stk[ptr-1];
}
// 스택에서 x를 찾아 인덱스(없으면 -1)를 반환
public int indexOf(int x) {
for (int i=ptr-1; i>=0; i--) { // 정상 쪽에서 선형 검색
if(stk[i]==x) {
return i; // 검색 성공
}
}
return -1; // 검색 실패
}
// 스택을 비움
public void clear() {
ptr = 0;
}
// 스택의 용량을 반환
public int capacity() {
return max;
}
// 스택에 쌓여있는 데이터 수를 반환
public int size() {
return ptr;
}
// 스택이 비어있는지 확인
public boolean isEmpty() {
return ptr <=0;
}
// 스택이 가득찼는지 확인
public boolean isFull() {
return ptr >= max;
}
// 스택 안의 모든 데이터를 bottom -> top 순서로 출력
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();
}
}
}
스택 사용하기
위에서 구현한 IntStack 클래스를 사용하는 프로그램을 만들어보자.
import java.util.Scanner;
public class IntStackTester {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
IntStack s = new IntStack(64); // 최대 64개 데이터를 push할 수 있는 스택 생성
while (true) {
System.out.println("현재 데이터 수: " + s.size() + " / " + s.capacity());
System.out.print("(1)push (2)pop (3)peek (4)dump (5)quit: ");
int menu = sc.nextInt();
if (menu == 0) break;
int x;
switch (menu) {
case 1: // push
System.out.println("데이터: ");
x = sc.nextInt();
try {
s.push(x);
} catch (IntStack.OverflowIntStackException e) {
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2: // pop
try {
x = s.pop();
System.out.println("pop한 데이터는 " + x + "입니다.");
} catch (IntStack.EmptyIntStackException e) {
System.out.println("스택이 비어 있습니다.");
}
break;
case 3: // peek
try {
x = s.peek();
System.out.println("peek한 데이터는 " + x + "입니다.");
} catch (IntStack.EmptyIntStackException e) {
System.out.println("스택이 비어 있습니다.");
}
break;
case 4: // dump
s.dump();
break;
}
}
}
}
실행 결과
