[알고리즘-PS] Java 에서 스택을 구현하는 방법

이 글은 Stack의 실질적 사용보다는 자바에서 스택을 구현하는 것에 목적을 두었습니다. 만약 자바에서 어떻게 스택이 사용되는지 궁금하다면 변수가 메모리에 담기는 과정 스택 프레임 또는 JRE와 JVM이 어떻게 실행될까?의 글을 가볍게 읽고 와 주시는 것을 추천드립니다.

스택 Stack

기술 스택 (목적을 달성하기 위해서 습득하기 위한 기술을 단계적으로 쌓아 올리는 것) 등에 쓰이는 말인 스택은 무언가를 쌓아 올린다 라는 표현으로 이해해도 무방하다.

 

스택은 데이터를 일시적으로 저장하기 위해 탄생한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

 

이를 전문 용어로 후입선출 (LIFO, Last In First Out) 이라고 한다.

푸시 (PUSH)

스택에 데이터를 넣는 작업을 뜻 한다.

팝 (POP)

스택에 데이터를 꺼내는 작업을 뜻 한다.

Top와 Bottom

Top는 스택에서 푸시와 팝을 수행하는 가장 꼭대기를 뜻 하며, Bottom은 스택의 가장 아랫부분 바닥을 뜻한다.

Int 데이터를 저장하는 Stack 만들기

 

간단하게 Int형 데이터를 저장하는 스택을 만들어보자.

 

 

간단하게 클래스 하나를 생성하여 세 가지의 private 필드를 만들어 주자.

• int ptr : 스택의 위치를 가리킬 포인터
• int max : 스택의 최대 용량
• int[] stack : 스택의 몸통 역할을 수행할 배열

 

생성자 만들기

 

매개변수로 스택의 용량을 받아 스택을 생성하는 생성자를 만들어 보자

 

 

생성자를 만들었다면 생성자에 capacity 라는 매개변수가 max에 들어가 스택의 최대 용량을 만들어준다. 또한 ptr을 0으로 초기화 시겨 스택 포인터의 위치를 스택의 Bottom에 위치하게 한다.

 

 

예외 처리

 

혹시나 스택의 포인터가 잘 못된 곳을 가르키고 있다거나 스택이 꽉 차서 더 이상 저장이 되지 않을 때를 위해서 예외를 다뤄준다.

 

 

Push와 POP

 

Push와 Pop을 위해 stack[] 배열의 ptr인덱스를 이용하여 값을 누적 혹은 누삭 시키는 메서드를 다음과 같이 만들어 준다.

 

 

전체 소스 코드

 

package chapter02_Stack;

public class Stack01_IntStack {
    public static void main(String[] args) {

    }
}

class IntStack{
    private int max;
    private int ptr;
    private int[] stack;

    // constructor
    public IntStack (int capacity){
        ptr = 0;
        max = capacity;
        try {
            stack = new int[max];
        } catch (OutOfMemoryError e) {
            max = 0;
        }
    }

    // push
    public int push(int x) throws OverflowStackException{
        if (ptr <= max){
            throw new OverflowStackException();
        }
        return stack[ptr++] = x;
    }

    // pop
    public int pop() throws EmptyStackException{
        if(ptr <= 0){
            throw new EmptyStackException();
        }
        return stack[--ptr];
    }

    // indexOf
    public int indexOf(int x) {
        for (int i = ptr-1; i >= 0 ; i--) {
            if(stack[i] == x){
                return i;
            }
        }
        return -1;
    }

    // Exception
    public class EmptyStackException extends RuntimeException {
        public EmptyStackException(){}

    }
    public class OverflowStackException extends RuntimeException {
        public OverflowStackException(){}
    }
}