기본 자료구조 - 스택[stack]

스택

데이터를 일시적으로 저장하기 위해 사용하는 자료구조

후입선출(LIFO, Last In First Out) - 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

 

■ 스택 자료구조

스택에 데이터를 넣는 작업을 푸시(push)

스택에서 데이터를 꺼내는 작업을 팝(pop)

1) 스택 용량 : max
스택에 쌓을 수 있는 최대 데이터 수를 나타내는 필드

2) 스택 포인터 : ptr
스택에 쌓여있는 데이터 수

3) 스택 생성자
스택 본체용 배열 생성 

4) push 메서드
스택에 데이터를 푸시, 스택이 가득 찬 경우 OverflowInStackException을 던진다.

5) pop 메서드
스택의 top에서 데이터를 제거하고 그 값을 반환, 스택이 비어 있을 경우 EmptyInStackException을 던진다.

6) peek 메서드
스택 꼭대기의 요소[ptr-1]의 값을 반환, 데이터의 입력과 출입이 없으므로 스택 포인터는 변화하지 않는다.

7) indexOf 메서드
스택의 본체 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사
검색은 top에서 bottom쪽으로 선형 검색을 수행

8) clear 메서드
스택에 쌓여있는 모든 데이터를 삭제하는 메서드
※ 스택에 대한 푸시와 팝 등 모든 작업은 스택 포인터를 바탕으로 이루어짐

9) capacity 메서드
스택의 용량을 반환

10) size 메서드
스택에 쌓여 있는 데이터의 수(ptr의 값)을 반환

11) IsEmpty 메서드
스택이 비어 있는지 검사하는 메서드

12) IsFull 메서드
스택이 가득 차 있는지 검사하는 메서드

13) dump 메서드
스택에 쌓여 있는 모든 데이터를 bottom에서 top순으로 출력

 

import java.sql.SQLOutput;
import java.util.Arrays;

public class InStack {
    private int max;    //스택 용량
    private int ptr;    //스택 포인터
    private int[] stk;  //스택의 본체

    //실행 시 예외 ; 스택이 비어있는 경우
    public class EmptyInStackException extends RuntimeException {
        public EmptyInStackException(){}
    }

    //실행 시 예외 ; 스택이 가득 차있는 경우
    public class OverflowInStackException extends RuntimeException {
        public OverflowInStackException(){}
    }

    public InStack(int capacity) {
        ptr = 0;
        max = capacity;
        try{
            stk = new int[max];
        }catch (OutOfMemoryError e){
            max = 0;
        }
    }

    public int push(int x) throws OverflowInStackException{
        if(ptr > max)
            throw new OverflowInStackException();
        return stk[ptr++] = x;
    }

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

    public int peek() throws EmptyInStackException {
        if(ptr <= 0){
            throw new EmptyInStackException();
        }
        return stk[ptr-1];
    }

    public int indexOf(int x){
        for(int i = ptr-1; i>=0; i--){
            if(stk[i] == x)
                return i;   //검색 성공
        }
        return -1;  //검색 실패
    }

    public void clear(){
        ptr = 0;
    }

    public int capacity(){
        return max;
    }

    public int size(){
        return ptr;
    }

    public boolean isEmpty(){
        return ptr <= 0;
    }

    public boolean isFull(){
        return ptr >= max;
    }

    public void dump(){
        if(ptr <= 0){
            System.out.println("스택이 비어 있습니다.");
        }else{
            for(int i=0; i<ptr; i++){
                System.out.println(stk[i] + " ");
            }
        }
    }

    public static void main(String[] args) {
        InStack stack = new InStack(8);
        stack.push(5);
        stack.push(8);
        stack.push(10);
        //TEST
        System.out.println("pop : " + stack.pop());
        System.out.println("peek : " + stack.peek());

        stack.clear();
        stack.push(14);
        stack.push(7);
        stack.push(11);
        stack.push(10);
        stack.push(4);
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("stack 용량 : " + stack.capacity());
        System.out.println("stack의 size : " + stack.size());
        System.out.println("stack의 isEmpty : " + stack.isEmpty());
        System.out.println("stack의 isFull : " + stack.isFull());
        stack.dump();
    }
}