이론 적인 것은 잘 정리된 글이 많기 때문에 생략.
java로 int 형 stack과 Object형 stack을 구현한 코드.


int 형을 저장하는 스택

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 maxLen) {
        ptr = 0;
        capacity = maxLen;
        try {
            // 스택 본채용 배열 생성
            stk = new int[capacity];
        } catch (OutOfMemoryError e) {
            // 생성할 수 없음
            capacity = 0;
        }
    }

    // 스택에 X를 푸시
    public int push(int x) throws OverflowIntStackException {
        if (ptr >= capacity)
            // 스택이 가득 찬 경우
            throw new OverflowIntStackException();

        return stk[ptr++] = x;
    }

    // 스택에서 데이터를 팝 (꼭대기에 있는 데이터를 꺼냄)
    public int pop() throws EmptyIntStackException {
        if (ptr <= 0)
            // 스택이 비어 있음
            throw new EmptyIntStackException();

        return stk[--ptr];
    }

    // 스택에서 데이트를 피크 (꼭대기에 있는 데이터 조회)
    public int peek() throws EmptyIntStackException {
        if (ptr <= 0)
            // 스택이 비어 있음
            throw new EmptyIntStackException();

        return stk[ptr - 1];
    }

    // 스택을 비움
    public void clear() {
        // 모든 작업이 ptr 값으로 이루어 지므로 배열의 요소를 변경할 필요가 없음.
        ptr = 0;
    }

    // 스택에서 X 찾아 인덱스 반환, 없다면 -1 반환
    public int indexOf(int x) {
        // 뒤(꼭대기)에서 부터 선형 탐색
        for (int i = ptr - 1; i >= 0; i--) {
            if (stk[i] == x)
                // 검색 성공
                return i;
        }
        // 검색 실패
        return -1;
    }

    // 스택의 용량 반환
    public int getCapacity() {
        return this.capacity;
    }

    // 스택에 쌓여있는 데이터 개수 반환
    public int size() {
        return ptr;
    }

    // 스택이 비어있는지 확인
    public boolean isEmpty() {
        return ptr <= 0;
    }

    // 스택이 가득 찼는지 확인
    public boolean isFull() {
        return ptr >= capacity;
    }

    public void dump() {
        if (ptr <= 0)
            System.out.println("EMPTY STACK");
        else {
            for (int i = 0; i < ptr; i++)
                System.out.print(stk[i] + " ");

            System.out.println("");
        }
    }
}

Object 형을 저장하는 스택

// 임의의 객체형을 쌓을 수 있는 테네릭 스택 클래서 Stack<E> 작성
public class GenericStack<E> {
    // 스택용 배열
    private E[] stk;
    // 스택 용량
    private int capacity;
    // 스택 포인터
    private int ptr;

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

    // 실행 시 예외 : 스택이 가득 찬 경우
    public static class OverflowGStackException extends RuntimeException {
        public OverflowGStackException(){}
    }

    // 생성자
    public GenericStack(int maxLen) {
        ptr = 0;
        capacity = maxLen;
        try {
            // 스택 본채용 배열 생성
            stk = (E[])new Object[capacity];
        } catch (OutOfMemoryError e) {
            // 생성할 수 없음
            capacity = 0;
        }
    }

    // 스택에 X를 푸시
    public E push(E x) throws OverflowGStackException {
        if (ptr >= capacity)
            // 스택이 가득 찬 경우
            throw new OverflowGStackException();

        return stk[ptr++] = x;
    }

    // 스택에서 데이터를 팝 (꼭대기에 있는 데이터를 꺼냄)
    public E pop() throws EmptyGStackException {
        if (ptr <= 0)
            // 스택이 비어 있음
            throw new EmptyGStackException();

        return stk[--ptr];
    }

    // 스택에서 데이트를 피크 (꼭대기에 있는 데이터 조회)
    public E peek() throws EmptyGStackException {
        if (ptr <= 0)
            // 스택이 비어 있음
            throw new EmptyGStackException();

        return stk[ptr - 1];
    }

    // 스택을 비움
    public void clear() {
        // 모든 작업이 ptr 값으로 이루어 지므로 배열의 요소를 변경할 필요가 없음.
        ptr = 0;
    }

    // 스택에서 X 찾아 인덱스 반환, 없다면 -1 반환
    public int indexOf(Object x) {
        // 뒤(꼭대기)에서 부터 선형 탐색
        for (int i = ptr - 1; i >= 0; i--) {
            if (stk[i].equals(x))
                // 검색 성공
                return i;
        }
        // 검색 실패
        return -1;
    }

    // 스택의 용량 반환
    public int getCapacity() {
        return this.capacity;
    }

    // 스택에 쌓여있는 데이터 개수 반환
    public int size() {
        return ptr;
    }

    // 스택이 비어있는지 확인
    public boolean isEmpty() {
        return ptr <= 0;
    }

    // 스택이 가득 찼는지 확인
    public boolean isFull() {
        return ptr >= capacity;
    }

    public void dump() {
        if (ptr <= 0)
            System.out.println("EMPTY STACK");
        else {
            for (int i = 0; i < ptr; i++)
                System.out.print(stk[i] + " ");

            System.out.println("");
        }
    }
}
728x90
반응형

'Computer Science > DataStructure' 카테고리의 다른 글

[DS] Array 배열  (0) 2022.07.17

배열 (Array)

  • 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
  • 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스 순서(논리적인 순서)와 일치

배열이 필요한 이유

  • 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
  • 같은 종류의 데이터를 순차적으로 저장

장단점

  • 장점
    • 빠른 데이터 접근
  • 단점
    • 추가/삭제가 쉽지 않음
    • 최대 길이를 미리 지정해야 함
data S T R I N G
index 0 1 2 3 4 5
728x90
반응형

'Computer Science > DataStructure' 카테고리의 다른 글

[DS] Stack 스택  (2) 2023.03.26

+ Recent posts