Java를 이용한 Stack 실습

LeetCode의 Queue, Stack 실습 중 Stack 부문을 읽고 작성하는 포스트다.

Explore - LeetCode

자바에서는 Stack이라는 클래스로 Stack, 스택 자료구조를 제공하고 있다. 자료구조를 공부했다면 못 들어봤을 수가 없는 대표적인 Last-In-First-Out 자료구조인 스택은 이전의 Queue와 달리 같은 곳에서만 데이터를 삽입하고 삭제할 수 있다. 이를 Java로 구현한다면 다음과 같이 코드를 작성할 수 있다.

class Stack {
    private int[] stack;
    private int pointer = -1;
    
    public Stack(int size){
        stack = new int[size];
    }
    
    public boolean push(int value){
        if(isFull()) return false;
        pointer += 1;
        stack[pointer] = value;
        return true;
    }
    
    public int pop(){
        if(isEmpty()) return -1;
        int retVal = stack[pointer];
        pointer -= 1;
        return retVal;
    }
        
    public int top(){
        if(isEmpty()) return -1;
        return stack[pointer];
    }
    
    public boolean isFull(){
        return ( pointer + 1 ) >= stack.length;
    }
    
    public boolean isEmpty(){
        return pointer < 0;
    }
}

간단한 배열 자료형과 데이터를 삽입, 삭제할 위치를 가리키는 포인터 변수를 유지하고 있다. 삽입(push), 삭제(pop) 연산 이전에 스택의 포화, 공백 여부를 검사하고 있는데 이는 단순히 포인터가 배열의 크기보다 큰지 아니면 배열 인덱스 밖에 있는지 여부를 검사하는 방식으로 구현할 수 있다.

먼저 공백상태 같은 경우는 현재 구현된 스택에서 포인터가 -1부터 시작하기 때문에 포인터가 -1인지 검사하는 방법을 사용할 수 있다. 구현된 스택에서 삽입, 삭제 연산은 포인터를 이동시킨 후 포인터가 가리키는 곳에 데이터를 삽입하거나 삭제(정확히는 반환할 값을 변수에 저장) 한 후 포인터를 이동시키기며 모든 요소를 삭제하거나 끝까지 삽입했을 경우 포인터는 배열의 바깥까지 이동하게 된다.

 

데이터를 삭제하는 경우 인덱스 0에 있는 데이터를 삭제한 후 포인터를 이동(감소)시키면 -1로 이동하며 이는 배열에서 참조할 수 없는 위치기 때문에 스택이 비어있다고 판단하는 것이다.

반대로 포화 상태의 경우 포인터가 스택의 길이보다 큰 곳을 가리키고 있는지 검사하여 확인할 수 있다. 위의 예제처럼 9개의 요소를 저장할 수 있는 스택에서 마지막 요소를 삽입한다면 인덱스 7을 가리키던 포인터는 8로 증가하여 stack[8]에 데이터를 저장한다. 여기서 데이터를 더 삽입하려고 하면 포인터는 인덱스 9를 가리키게 되어 stack[9], 즉 10번째 요소에 저장하라는 말이 되기 때문에 접근할 수 없다. 그래서 만약 이동할 포인터가 스택의 바깥을 가리키게 된다면 스택이 포화 상태라고 판단하는 것이다.

 

어쨌든 삽입, 삭제 시 현재 포인터가 가리키는 곳에서 한 칸 이동한 후 데이터를 삽입, 삭제하기 때문에 현재 포인터가 어딜 가리키고 있는지 데이터를 삽입, 삭제한 후에는 어딜 가리키게 될지 이해하고 있어야 한다.

 

Java에서 제공하는 Stack 클래스는 Vector 클래스의 하위 클래스로 구현되어있다. Vector 자료구조는 배열과 유사하게 아무런 인덱스나 참조할 수 있는데 새로 추가되는 데이터를 담을 공간이 없다면 크기가 자동으로 늘어나는 특징이 있다. 이런 Vector를 5가지 메서드(empty, peek, pop, push, search)만 사용할 수 있도록 하여 Stack처럼 사용하도록 한 것이 Stack 클래스인 것이다.

 

 

이번 Stack같은 경우는 너무 유명하고 원리도 간단해서 그런지 LeetCode에서도 딱히 구현하는 실습을 진행하지 않고 있다. 대신 '바퀴를 다시 발명하지 마라'는 원리를 반영해서 이미 구현된 스택 라이브러리를 활용해 문제를 푸는데 집중하고 있다.