자료구조 - 스택(Stack) , 배열로 스택만들어 보기

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.

 

스택이란?

 

스택(stack)은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out) 입니다. (가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.)

스택에 데이터를 넣는 작업을 푸시(push)라 하고 ,스택에 데이터를 꺼내는 작업을 팝(pop)이라고 합니다.

푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 합니다.

 

 

스택만들기

 

스택을 구현하는 프로그램을 만들어 보겠습니다.

 

스택 본체용 배열: stk

푸시된 데이터를 저장하는 스택 본체의 배열입니다. 인덱스 0인 요소가 스택의 바닥(bottom)입니다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]입니다.

 

스택용량: max

스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타내는 필드입니다. 이 값은 stk의 요솟수와 같습니다.

 

스택 포인터: ptr

스택에 쌓여 있는 데이터 수를 나타내는 필드입니다. 이 값은 스택 포인터(stack pointer)라고 합니다.

 

 

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

    // 실행 시 예외: 스택이 비어 있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() {}
    }

    // 실행 시 예외: 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() {}
    }

    // 생성자
    public IntStack(int capacity) {
        ptr = 0;
        max = capacity;
        try {
            stk = new int[max];
        } catch(OutOfMemoryError e) {       // 생성할 수 없을 때
            max = 0;
        }
    }
}

 

생성자 IntStack

생성자는 스택 본체용 배열을 생성하는 등 준비 작업을 수행합니다. 생성 시 스택은 비어있으므로 스택 포이ㄴ터 ptr값은 0으로 합니다.

매개변수 capacity 는 전달 받은 값을 스택 용량을 나타내는 max 복사하고 요솟수가 max인 배열 stk의 본체를 생성합니다.

 

 

푸시 메서드 push

스택에 데이터를 푸시하는 메서드입니다.

스택이 가득 차서 푸시할 수 없는 경우 예외 OverflowIntStackException을 던집니다.

 

 

    // 스택에 x 넣기
    public int push(int x) throws OverflowIntStackException {
        if(ptr >= max) {
            throw new OverflowIntStackException();
        }
        return stk[ptr++] = x;
    }

 

전달받은 데이터 x를 배열 요소 stk[ptr]에 저장하고, 스택 포인터를 증가시킵니다.

 

스택 포인터 ptr 값은 반드시 0 이상 max 이하가 됩니다. 따라서 스택이 가득 찼는지에 대한 검사는 관계 연산자( >=  )를 사용하여 수행할 수 있습니다.

 

팝 메서드 POP

 

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

스택이 비어 있는 경우 팝을 할 수 없는 경우 EmptyIntStackException을 던집니다.

 

    // 스택에 값 빼기 ( 꼭대기에 있는 데이터 꺼냄 )
    public int pop() throws EmptyIntStackException {
        if ( ptr <= 0 ) {
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }

 

피크 메서드 peek

 

스택의 꼭대기에 있는 데이터를 엿보는 메서드입니다.

 

    // peak ( 꼭대기에 있는 값 확인 )
    public int peek() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[ptr - 1];
    }

 

스택이 비어 있지 않으면 꼭대기의 요소 stk[ptr - 1] 의 값을 반환합니다.

 

 

검색 메서드 indexOf

 

스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지 조사하는 메서드입니다.

검색은 꼭대기 쪽에서 바닥쪽으로 선형 검색을 수행합니다.

검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환합니다.

 

 

스택의 모든 요소를 삭제하는 메서드 clear

 

clear 메서드는 스택에 쌓여 있는 모든 데이터를 삭제하는 메서드입니다.

 

 

용량을 확인하는 메서드 capacity

 

capacity 메서드는 스택의 용량을 반환하는 메서드입니다. max 값을 그대로 반환합니다.

 

 

데이터 수를 확인하는 메서드 size

 

size 메서드는 현재 스택에 쌓여있는 데이터 수를 반환하는 메서드입니다.

 

 

스택이 비어 있는지 검색하는 메서드 IsEmpty

 

IsEmpty 메서드는 스택이 비어 있는지 검사하는 메서드입니다. 스택이 비어 있으면 그렇지 않으면 false를 반환합니다.

 

 

스택이 가득 찼는지 검사하는 메서드 IsFull

 

IsFull 메서드는 스택이 가득 찼는지 검사하는 메서드입니다. 스택이 가득 찼으면 그렇지 않으면 false를 반환합니다.

 

 

스택 안에 있는 모든 데이터를 표시하는 메서드 dump

 

스택이 쌓여 있는 모든 데이터를 바닥에서 꼭대기 순으로 표시하는 메서드입니다.

스택이 비어있으면 '스택이 비어 있습니다.' 라고 표시합니다.

 

    // 스택에서 x 찾는 인덱스를 반환
    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]);
            }
            System.out.println();
        }
    }

 

 

직접 만들어본 스택 클래스는 밑에 와 같습니다.

 

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

    // 실행 시 예외: 스택이 비어 있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() {}
    }

    // 실행 시 예외: 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() {}
    }

    // 생성자
    public IntStack(int capacity) {
        ptr = 0;
        max = capacity;
        try {
            stk = new int[max];
        } catch(OutOfMemoryError e) {       // 생성할 수 없을 때
            max = 0;
        }
    }

    // 스택에 x 넣기
    public int push(int x) throws OverflowIntStackException {
        if(ptr >= max) {
            throw new OverflowIntStackException();
        }
        return stk[ptr++] = x;
    }

    // 스택에 값 빼기 ( 꼭대기에 있는 데이터 꺼냄 )
    public int pop() throws EmptyIntStackException {
        if ( ptr <= 0 ) {
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }

    // peak ( 꼭대기에 있는 값 확인 )
    public int peek() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[ptr - 1];
    }


    // 스택에서 x 찾는 인덱스를 반환
    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]);
            }
            System.out.println();
        }
    }

}

 

이제 만들어 본 클래스를 사용해보겠습니다.

 

import java.util.Scanner;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        IntStack stack = new IntStack(10);

        while(true) {
            System.out.println("현재 데이터수 : " + stack.size() + " / " + stack.capacity());
            System.out.println("(1) 푸시   (2) 팝   (3)피크   (4) 덤프   (0) 종료");

            int menu = sc.nextInt();
            if(menu == 0) break;

            int x;

            switch (menu) {
                case 1:         // 푸시
                    System.out.println("넣을 데이터 : ");
                    x = sc.nextInt();
                    try {
                        stack.push(x);
                    } catch(IntStack.OverflowIntStackException error) {
                        System.out.println("스택이 가득 찼습니다.");
                    }
                    break;

                case 2:
                    try {
                        x = stack.pop();
                        System.out.println("제일 위에 있던 값은 " + x + " 입니다.");
                    } catch(IntStack.EmptyIntStackException error) {
                        System.out.println("스택이 비어 있습니다.");
                    }
                    break;

                case 3:
                    try {
                        x = stack.peek();
                        System.out.println("제일 위에 있는 값은 : " + x + " 입니다.");
                    } catch(IntStack.EmptyIntStackException error) {
                        System.out.println("스택이 비어 있습니다.");
                    }
                    break;

                case 4:
                    stack.dump();
                    break;
            }
        }
    }
}