스택 (Stack)

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편 review 

 

- 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이며, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out) 이다. 스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝 (pop) 이라 하한다.

출처: https://bakjh6280.com/2018/10/10/what-is-stack/

 

push & pop을 하는 위치를 꼭대기(top) 이라하며, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.

 

- int stack code

기능 :

1. 스택의 모든 요소를 삭제 clear

2. 스택의 용량 확인 capacity

3. 스택의 데이터 수를 확인 size

4. 스택이 비어있는지 검사하는 isEmpty

5. 스택이 가득찼는지 검사하는 isFull

package stack;

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;
        }
    }

    // stack에 데이터를 쌓음
    public int push(int x) throws OverflowIntStackException {
        if (ptr == max )
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }

    // stack에 데이터를 꺼내옴
    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];
    }

    // 스택에서 x를 찾아 인덱스 (없으면 -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] + " ");
            }
            System.out.println();
        }
    }
}

 

- intstack main

package stack;

import java.util.Scanner;

public class IntStackTester {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        IntStack stack = new IntStack(64);

        while (true) {
            System.out.println("현재 데이터수: " + stack.size() + " /" + stack.capacity());
            System.out.println("(1)푸시  (2)팝  (3)피크  (4)덤프  (5)찾기  (6)비우기  (7)크기확인  (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 e) {
                        System.out.println("스택이 가득 찼습니다.");
                    }
                    break;

                case 2:
                    try {
                        x = stack.pop();
                        System.out.println("팝한 데이터는 " + x + "입니다.");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("스택이 비어있습니다.");
                    }
                    break;

                case 3:
                    try {
                        x = stack.peek();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("스택이 비어 있습니다.");
                    }
                    break;

                case 4:
                    stack.dump();
                    break;

                case 5:
                    System.out.println("찾으시려는 값을 입력해주세요: ");
                    int num = sc.nextInt();
                    int result = stack.indexOf(num);
                    if (result == -1)
                        System.out.println("찾으시는 값은 없습니다.");
                    else
                        System.out.println("찾으시는 값은 (" + result +")위치에 있습니다.");

                case 6:
                    stack.clear();

                case 7:
                    System.out.println("스택 크기는 : " + stack.size());
            }
        }
    }
}