자료구조 - Stack 를 간단한 코드로 파악하기
개념
스택(Stack)이란? 데이터를 저장하기 위한 자료구조중 하나로 데이터를 일시적으로 저장하기 위해 고안된 개념이며, 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 방식으로 진행됩니다. 데이터의 입출력 순서를 후입선출(LIFO, Last In First Out) 이라고 불리며, 간단하게 표현하자면 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.
사용단어?
- push : 스택에 데이터를 넣는 작업
- pop : 스택에서 데이터를 꺼내는 작업
- top : 푸시와 팝이 이루어지는 가장 바깥쪽을 탑이라 합니다
- bottom : 스택의 가장 아랫부분, 푸시가 가장먼저 이루어졌던 데이터의 위치를 바텀이라고 합니다
- peek : 피크(peek)란 '몰래 엿보다'라는 뜻을 가지며 스택의 가장 상단의 top 인덱스를 보여줍니다.
위 사진과 같이 스택은 먼저 입력한 데이터가 가장 나중에 출력되는 구조이므로 이부분을 확실히 기억하고 가야합니다.
그러면 간단한 예제코드로 스택의 flow 를 알아보겠습니다.
public class IntStack {
private int max; //스택의 용량(최대치)
private int pointer; //스택 포인터(스택의 위치파악을 위한 포인터)
private int[] stk; //스택 본체
//스택이 비어있을 때 실행 시 예외처리
public class EmptyException extends RuntimeException {
public EmptyException(){}
}
//스택이 가득찼을 때 실행시 예외처리
public class OverflowException extends RuntimeException {
public OverflowException(){}
}
//생성자
public IntStack(int capacity) {
ptr = 0;
max = capacity;
try {
stk = new int[max]; //스택 본체용 배열을 생성
} catch (OutOfMemoryError e) { //생성할 수 없을 때
max = 0;
}
}먼저 스택의 구조 준비를 위한 생성자 및 예외처리 작업입니다. 예외처리는 Exception 등으로 하거나 묵시적으로 하려했으나, 그냥 표기하고 넘어가겠습니다. 생성자를 생성하면서 ptr 포인터를 초기 인덱스값인 0으로 초기화하며 매개변수로 받은 capacity로 전달받은 값을 스택 용량을 나타내는 max를 stk 배열의 요소수(배열의 크기)로 선언하여 준비합니다.
//Push method
public int push(int x) thorws OverflowException {
if(ptr >= max)
throw new OverflowException();
return stk[ptr++] = x;
}
//Pop method
public int pop() throws EmptyException {
if(ptr <= 0)
throw new EmptyException();
return stk[--ptr];
}Stack 의 주요기능인 push 와 pop의 구조입니다.
먼저 push 는 값을 추가하여 인덱스를 쌓아 올리는 구조의 작업을 합니다. ptr >= max 는 포인터가 최대치를 넘으면 안되므로 Exception을 던집니다. 그리고 스택의 본체인 stk 의 배열 인덱스가 ++되며 포인터의 위치가 변하고 이를 x로 저장합니다.
그리고 pop은 스택에서 데이터를 빼는 작업을 하며 이때 스택이 전부 비어 0이하로 될경우 에러를 발생하고 이전까지는 stk[포인터를 --] 해서 인덱스를 하나씩 빼냅니다.
Peek method
피크 메소드는 top index의 값을 보여주는 메소드로 현재 스택의 위치를 파악하기 위한 용도로 사용됩니다.
public int peek() throws EmptyException {
if(ptr <= 0)
throw new EmptyException();
return stk[ptr - 1]; //포인터에서 -1로 인덱스를 확인한다.
}
그외 메소드들..
- indexOf : 검색메소드로 top -> bottom 방향으로 진행하며 인덱스를 검사하여 일치하는 값의 인덱스번호를 리턴합니다. 같은 값의 데이터가 있어도 가장 높은 인덱스번호를 리턴하는데 이는 먼저 pop이 되는 데이터를 찾기 위해서 입니다.
- clear : 스택의 모든 요소를 삭제하는 메소드로 모든 데이터를 초기화합니다.
- capacity : 용량을 확인하는 메소드로 max의 값을 반환합니다.
- size : 현재 스택에 쌓여있는 데이터의 수(ptr 포인터의 위치)를 반환합니다.
- IsEmpty : 스택이 비었는지 확인하는 메소드로 스택이 비어 포인터의 위치가 0인지 확인합니다.
- IsFull : 스택이 가득 찼는지 확인하는 메소드로 스택의 용량 max와 포인터 ptr의 값이 일치하면 true 입니다.
//indexOf : 검색
public int indexOf(int x) {
for (int i = ptr-1; i >= 0; i--) {
if(stk[i] == x)
return i;
return -1;
}
}
//clear : 모든 요소 삭제
public void clear() {
ptr = 0;
}
//capacity : 스택의 용량 확인
public int capacity() {
return max;
}
//size : 현재 스택에 쌓인 데이터의 수
public int size() {
return ptr;
}
//isEmpty : 스택이 비어있는지 확인
public boolean isEmpty() {
return ptr <= 0;
}
//isFull : 스택이 가득 찼는지 확인
public boolean isFull() {
return ptr >= max;
}
//dump : 스택의 모든요소를 bottom -> top 순으로 출력
public void dump() {
for(int i=0; i<ptr; i++) {
System.out.print(stk[i] + " ");
}
이처럼 스택은 다양한 경우에 데이터를 임시로 보관하거나, 삭제하면서 관리하는 기능을 수행할 수 있는 자료구조입니다.
이를 지원하거나 활용할 수 있는 메소드는 다양한 경우에 (코딩테스트, 자료구조 구현)에서 사용될 수 있을거 같으며,
제가 작성한 자료는 '자료구조와 함께 배우는 알고리즘 입문 자바편' 에서 참고하여 작성되었습니다.