스택(Stack)

스택이란 ?

데이터를 일시적으로 쌓은 자료구조이다.

입/출력순서는 LIFO(Last In First Out)이다 
👉 데이터가 아래부터 순차적으로 쌓이면 꺼낼때는 위부터 순차적으로 뺄 수 있다. 
👉 스택사용시 데이터의 순서가 반전된다.

---

---

용어 ?

push : 스택에 데이터를 넣는 작업
pop : 스택에서 데이터를 꺼내는 작업
Top / 꼭대기 : 스택에서 데이터가 들어오고 나가는 쪽 (위쪽)
Bottom / 바닥 : 스택에 가장 최하단 쪽

 

---

스택 기능 ?

---

코드 ?

// 스택을 구현해 본 코드

public class IntStack {
    private int[] stk; // 스택용 배열
    private int capacity; // 스택 용량
    private int ptr; // 스택 포인터
    
    // 실행 시 예외 : 스택이 비어 있음
    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){}
    }
    
    //실행 시 예외 : 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){}
    }
    
    // 생성자
    public IntStack(int capacity){
        ptr = 0 ;
        this.capacity = capacity;
        try{
            stk = new int[capacity];
        }catch (OutOfMemoryError e){
            capacity = 0;
        }
    }
    
    //스택으로 값을 push하기 위한 메서드
    public int push(int x) throws OverflowIntStackException{ 
        if(ptr >= capacity) // 스택 포인터가 스택의 용량과 같을 때 예외발생
            throw new OverflowIntStackException();
        return stk[ptr++] = x; //현재 스택 포인터에 값을 넣고 포인터를 다음 위치로 이동
    }
    
    //스택에서 값을 pop하기 위한 메서드
    public int pop() throws EmptyIntStackException{
        if(ptr <= 0)
            throw new EmptyIntStackException();
        return stk[--ptr];
    }

    // 스택 top에 위치한 값을 확인하는 메서드
    public int peek() throws EmptyIntStackException{
        if(ptr <= 0)
            throw new EmptyIntStackException();
        return stk[ptr - 1];
    }

    // 스택의 모든 요소를 삭제하는 메서드
    public void clear(){
        ptr = 0;
    }

    // 스택에서 원하는 값이 포함되어 있는지? 있다면 어느 위치에 있는지? 확인하는 메서드
    public int indexOf(int x){
        // 꼭대기 부터 찾는다.
        // 동일한 값이 스택에 있다면 pop을 할 때 꼭대기에서부터 꺼내기에
        for(int i = ptr - 1; i >= 0 ; i--){
            if(stk[i] == x)
                return i; // 찾을 시 위치 반환
        }
        return -1; // 없을 시 -1 반환
    }

    // 스택의 용량을 확인하는 메서드
    public int getCapacity(){
        return capacity;
    }

    //스택에 쌓여 있는 데이터 개수를 반환
    public int size(){
        // 배열에서는 0부터 시작 하며 쌓일 때마다 포인터가 1씩 증가한다.
        // 이해를 위해 한 가지 예로 처음에는 포인터가 0을 가르키고 있다.
        // 이때, 데이터가 하나 push되면 포인터는 1로 이동한다. 그리고 데이터도 현재 1개가 쌓였다.
        return ptr;
    }

    // 스택이 비어 있는가 ?
    public boolean isEmpty(){
        // 비교 연산이기에 boolean을 한다. 그리고 비어 있으면 포인터는 0을 가르킬 것이다.
        return ptr <= 0;
    }

    //스택이 가득 찼는가?
    public boolean isFull(){
        // 스택을 위한 배열은 (용량 -1)이 마지막 인덱스이다.
        // ptr은 항상 현재 데이터가 마지막으로 저장되어 있는 인덱스+1을 가르킨다.
        // 배열의 마지막 인덱스까지 값이 저장되었다면 ptr == capacity와 값은 값이 된다.
        // 여기서 다시 값을 넣으려고 하면 배열의 저장 범위를 넘어감으로 예외가 발생한다.
        return ptr >= capacity;
    }

    // 스택 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
    public void dump(){
        if(ptr <= 0)
            System.out.println("스택이 비어 있습니다");
        else{
            for(int i = 0 ; i < ptr ; i++)
                System.out.print(stk[i]+ " ");
        }
        System.out.println();
    }
}

---

보충설명 ?

스택 사이즈 , 용량 , 포인터 위치와 관련하여 영향을 받는 메서드(기능)는 비교연산자가 사용된 것을 확인할 수 있다.

용량이 가득 찼을 경우) if(ptr >= capacity)
비어 있을 경우) if(ptr <= 0) 

이때 , == 연산자를 사용해도 되는데 <= , >= 을 사용한 부분이 있었다. 
이 부분에 대해서는 프로그램 오류 등으로 프로그램 수행 중 의도하지 않게 값이
증가하거나 감소하여 ptr이 0보다 작거나 capacity보다 클 수 있다.
이때 위와같이 부등호를 붙여주면 스택 배열의 범위를 벗어나는 접근을 막을 수 있다.
이러한 안정성 문제를 고려하여 작성하면 안정성을 향상 시킬 수 있다.