스택(stack)-스택이란,개념,특징,구현

 

 

목차

 

스택(stack)

데이터를 순서대로 저장하지만 사용할때는 가장 나중에 넣은 데이터를 먼저 꺼내도록 하는 자료구조를 스택(stack)이라고 한다.

 

스택의 특징

스택은 아래와 같이 데이터를 저장하고 사용한다.

• 가장 나중에 넣은 데이터가 가장 먼저 나가게 되는 후입선출(LIFO, Last In First Out) 형태이다.
• top에서 자료의 삽입과 자료의 삭제가 이루어진다.
• 중간 데이터를 삭제할 수 없다.

그림으로 표현하면 이러한 형태이다.

 

• 스택에 데이터를 삽입하는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다.
• 푸시와 팝을 하는 위치를 꼭대기(top) 이라고 하고, 스택의 가장 아래부분을 바닥(bottom)이라고 한다.

 

스택 만들기

스택 본체

데이터를 저장하는 배열,  스택의 용량, 스택 포인터가 필요하다.

public class IntStack {
    int max; //스택의 최대 용량
    int ptr; //스택 포인터
    int[] stk; //데이터를 저장하는 스택 본체
}

 

1. max : 스택의 최대 용량

스택이 가득 차면 더 이상 데이터를 넣을 수 없다. 스택이 가득 차서 푸시할 수 없을 경우 예외를 던져야 한다.

2. ptr : 스택 포인터

스택에 쌓여 있는 데이터 수이자 데이터를 푸시할 위치를 알 수 있는 필드이다.

3. stk : 데이터를 저장하는 배열

푸시된 데이터를 저장하는 스택 본체의 배열이다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]이다.

 

public class IntStack {
    int max; //스택의 최대 용량
    int ptr; //스택 포인터
    int[] stk; //데이터를 저장하는 스택 본체

    //생성자. capacity 크기의 배열을 생성.
    public IntStack(int capacity){
        ptr = 0;
        max = capacity;
        try{
            stk = new int[max];
        }catch(OutOfMemoryError e){
            max = 0;
        }
    }
    //스택이 비어있을 때 exception
    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){}
    }

    //스택이 가득 찼을 때 exception
    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){}
    }

}

 

생성자 IntStack

스택 포인터 ptr 값을 0으로 하고, capacity 만큼의 배열을 생성한다. max는 배열의 크기와 같다. 스택 본체는 stk[0] 부터 시작해서 마지막에는 stk[max-1] 이 된다.

 

 

푸시 메서드 - 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];
    }

스택의 꼭대기에서 데이터를 팝(제거)하고 그 값을 반환하는 메서드.

 

검색 메서드 - indexOf

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

스택 본체의 배열 stk에 x와 같은 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어있는지를 조사하는 메서드. 검색은 꼭대기 쪽에서 바닥 쪽으로 선형 검색을 수행한다. 즉, 배열 인덱스가 큰 쪽에서 작은 쪽으로 스캔한다. 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다.

 

---

참고

방송통신대학교 자료구조 수업

자료구조와 함께 배우는 알고리즘 입문