스택이란?
데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다.
데이터의 입력과 출력 순서는 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 후입선출(LIFO, Last In First Out)의 방식이다.
- 스택에서 데이터를 넣는 작업 : 푸시 Push
- 스택에서 데이터를 꺼내는 작업 : 팝 Pop
- 푸시와 팝이 이루어지는 위치 : 꼭대기 Top
- 스택의 가장 아랫부분 : 바닥 Bottom
스택의 작동
스택은 바닥이 막힌 원통에 공을 집어넣고 꺼내는 것과 같다. 넣는 작업을 푸시(Push) 꺼내는 작업을 팝(Pop)이라고 한다. 그림에서는 먼저 8번 공을 원통 안에 넣고, 그 다음 3번 공을 넣었다. 스택은 다시 공을 꺼낼 때 가장 마지막에 넣은 3번공부터 꺼낼 수 있는 구조이다.
때문에 스택에서는 가장 마지막에 들어오는 데이터를 추적할 필요가 있다. 맨 마지막에 들어오는 데이터를 꼭대기, Top, Peek 등으로 표현한다.
Java 내부 스택
자바에서는 메서드를 호출하고 실행할 때 프로그램 내부적으로 스택을 사용한다.
예를 들어, 이런식으로 메소드 호출을 한다면
public class Test {
static void methodA() {
}
static void methodB() {
}
static void methodC() {
methodA();
methodB();
}
public static void main(String[] args) {
methodC();
}
}
이런 구조로 메서드가 호출, 실행된다.
스택 구현하기 1 : 기본
class IntStack {
int[] stk; //스택 본체용 배열
int max; //스택용량
int ptr; //스택포인터
}
1-1. 스택 본체용 배열 (stk)
: 이곳에는 푸시된 데이터를 저장한다. 바닥이 막힌 원통에 해당한다.
1-2. 스택 용량 (max)
스택의 용량. 즉 스택에 쌓을 수 있는 최대 데이터 수를 나타낸다.
이 값은 결국 stk 배열의 길이(length)와 같다.
1-3. 스택포인터 (ptr)
스택에 쌓여있는 데이터 수를 나타낸다. 이 값은 스택포인터(Stack Pointer)라고 한다. 새로운 데이터를 삽입하거나 삭제할 인덱스를 가리키는 용도이다.
- 비어있는 스택인 경우 : ptr = 0
- 가득 찬 스택인 경우 ptr = max
1-4. 생성자 (intStack)
생성자는 스택 본체용 배열을 생성, 초기화하는 준비 작업을 수행한다. 처음 생성 시 스택은 비어있어야 하고 스택포인터는 0이어야 한다. 전달받은 값을 max에 대입해서 스택용량을 결정하고 길이가 max인 stk배열을 만든다.
public IntStack(int size) {
ptr = 0; //스택포인트 초기화
max = size; //받아온 파라미터 size로 용량(max) 초기화
stk = new int[max]; //길이가 max인 배열 stk
}
스택 구현하기 2 : 푸시 메서드
데이터가 쌓일 원통을 만들었다면, 데이터를 집어넣는 메서드를 구현해야한다.
public int push(int x) throws OverflowIntStackException {
if (ptr >= max) { //스택이 가득 찼을 경우 예외처리
throw new OverflowIntStackException();
}
return stk[ptr++] = x; //푸시한 값을 반환
}
스택 구현하기 3 : 팝 메서드
스택의 꼭대기(Top, ptr)에 있는 데이터를 팝하고 그 값을 반환하는 메서드이다. 스택이 비어있어 팝할 수 없다면 예외처리한다.
public int pop() throws EmptyIntStackException {
if (ptr <= 0){ //스택이 비어 있을 경우
throw new EmptyIntStackException();
}
return stk[--ptr];
}
스택 구현하기 4 : 피크 메서드
스택 꼭대기에 있는 데이터를 '몰래 엿보는' 메서드이다. 스택에서 Top이 가리키는 데이터를 읽는 작업을 하며, 데이터의 입출력이 이루어지지 않으므로 스택포인터(ptr) 값의 변화는 없다.
public int peek() throws EmptyIntStackException {
if (ptr <= 0){ //스택이 비어 있을 경우
throw new EmptyIntStackException();
}
return stk[ptr - 1]; //스택 꼭대기 데이터
}
| 분류 | 차이점 |
| PUSH | top(ptr) 값이 증가 |
| POP | top(ptr) 값이 감소 |
| PEEK | top(ptr) 값의 변화 없음 |
스택 구현하기 5 : 검색메서드
스택 배열 stk에 검색할 값이 포함되어 있는지, 있다면 배열의 몇 번째 인덱스에 들어있는 지 알려주는 메서드이다. 꼭대기에서부터 바닥쪽으로 선형검색을 수행한다. 즉, stk[length-1] 부터 stk[0]까지 스캔하면서 검색할 값이 있는 지 찾아낸다. 만약 값이 있다면 찾아낸 요소의 인덱스를 반환하고 없다면 -1을 반환한다.
단, 같은 값이 여러 개 존재한다면 꼭대기 쪽의 인덱스를 반환한다. 꼭대기 쪽에서 스캔하는 이유는 "먼저 팝이 되는 데이터"를 찾기 위해서 이기 때문이다.
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) { //꼭대기(Top)부터 선형검색
if (stk[i] == x) {
return i; //검색성공
}
}
return -1; //검색실패
}
스택 구현하기 6 : 스택의 모든 요소를 삭제하는 메서드
스택에 쌓여 있는 모든 데이터를 삭제하는 메서드이다. 스택포인터 값을 0으로 변경하면 된다.
public void clear() {
ptr = 0;
}
스택 구현하기 7 : 용량 확인 메서드
생성자에서 스택 본체 배열의 용량을 max로 설정해주었다. 따라서 max를 리턴해주면 된다.
public int capacity() {
return max;
}
스택 구현하기 8 : 데이터 수를 확인하는 메서드
스택에 쌓여있는 데이터 수는 ptr과 같으므로 ptr을 리턴해주면 된다.
public int size() {
return ptr;
}
스택 구현하기 9 : 스택이 비어있는 지 확인하는 메서드
public boolean isEmpty() {
return ptr <= 0;
}
스택 구현하기 10 : 스택이 가득 차있는지 확인하는 메서드
public boolean isFull() {
return ptr >= max;
}
댓글