스택 (stack)

1. 개념정리

1) 한쪽에서만 데이터 삽입과 삭제가 가능한 구조

2) LIFO(Last In First Out, 마지막 삽입 데이터가 먼저 삭제됨)

3) java.util 패키지에 Stack 클래스가 있다.

 

2. 구현 코드

class ArrayStack{ // int[]로 구현하는 스택
    protected final int defCap = 10;  // 스택의 용량
    protected int[] stack;            // 스택의 요소를 담을 배열
    protected int topIndex = -1;      // 스택의 가장 마지막 인덱스

    public ArrayStack() {             // 기본 생성자
        stack = new int[defCap];
    }
    
    public ArrayStack(int maxSize) {  // 스택의 크기를 지정한 생성자
        stack = new int[maxSize];
    }

    public boolean isEmpty(){ // 스택이 비어있다면 true 반환
        if (topIndex == -1) return true;
        else return false;
    }

    public boolean isFull(){ // 스택이 가득 차있다면 true 반환
        if (topIndex == (stack.length -1)) return true;
        else return false;
    }
    
    public int size() { // 스택의 크기 반환
        return topIndex+1;
    }
    
    public int capacity(){ // 스택의 용량 반환
        return stack.length;
    }

    public void push(int element){ // 스택에 요소 추가
        if (!isFull()) stack[++topIndex] = element;
        else System.out.println("full stack: " + element + " push 실패");
    }

    public void pop(){ // 스택에서 요소 제거
        if (!isEmpty()) topIndex--;
        else System.out.println("empty stack: pop 실패");
    }

    public int top(){ // 스택의 마지막 요소 확인
        int topOfStack = 0;
        if (!isEmpty()) topOfStack = stack[topIndex];
        else System.out.print("empty stack: top 실패 -> ");
        return topOfStack;
    }
}

 

3. 예제 코드

// 1) 생성
ArrayStack s1 = new ArrayStack();  // 용량이 10인 스택 생성
ArrayStack s2 = new ArrayStack(5); // 용량이 5인 스택 생성

// 2) 추가
for(int i=0 ; i<s1.capacity() ; i++) // s1 꽉 채우기
    s1.push(i);
System.out.println(s1.size()); // 10. s1 = [0,1,2,3,4,5,6,7,8,9]
s1.push(11);                   // full stack: 11 push 실패
s2.push(100);                  // 성공. s2 = [100]

// 3) 삭제 & 확인
s1.pop();                      // s1 = [0,1,2,3,4,5,6,7,8]
System.out.println(s1.top());  // 8
System.out.println(s1.size()); // 9

System.out.println(s2.top());  // 100
System.out.println(s2.size()); // 1
s2.pop();                      // s2 = []
System.out.println(s2.top());  // empty stack: top 실패 -> 0