[알고리즘]스택

본 글은 Bohyoh Shibata의 "자료구조와 함께 배우는 알고리즘 입문(자바편)"을 참고하여 작성하였습니다.

스택

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

주요용어정리

max: 스택 용량
ptr: 스택 포인터(스택에 쌓여 있는 데이터 수)
stk: 푸시된 데이터를 저장하는 스택 본체의 배열(스택 본체를 참조하는 배열 변수)
생성자 IntStack: 스택 본체용 배열을 생성
메서드 push: 스택에 데이터를 넣는 메서드. 스택이 가득 차서 푸시할 수 없는 경우 예외 OverflowIntStackException을 던짐
메서드 pop: 스택에서 데이터를 꺼내고(제거하고) 꺼낸 값을 반환하는 메서드. 스택이 비어서 팝할 수 없는 경우 예외 EmptyIntStackException을 던짐
메서드 peek: 스택의 꼭대기를 반환하는 메서드. 스택이 비어있는 경우, EmptyIntStackException을 던짐
메서드 indexOf: 스택 본체의 배열 stk에 입력값과 같은 값의 데이터가 포함된 경우, 해당 인덱스를 조사하는 메서드. 꼭대기 쪽에서 바닥 쪽으로 선형 검색 수행
메서드 clear: 스택에 쌓여있는 모든 데이터 삭제
메서드 capacity: 스택의 용량을 반환
메서드 size: 스택의 현재 쌓여있는 데이터 수(ptr)를 반환
메서드 isEmpty: 스택이 비어있는지 반환, 비어있으면 true, 비어있지 않으면 false 반환
메서드 isFull: 스택이 가득 찼는지 반환, 가득 차있으면 true, 가득 차지 않으면 false 반환
메서드 dump: 스택의 바닥부터 꼭대기까지 출력

코드

/IntStack.java

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;
        }
    }
    
    public int push(int x) throws OverflowIntStackException {
    	if (ptr >= max) {
        	throw new OverflowIntStackException();
        }
        return stk[prt++] = x;
    }
    
    public int pop() throws EmptyIntStackException {
    	if (ptr <= 0) {
        	throw new EmptyIntStackException();
        }
        return stk[--prt];
    }
    
    public int peek() throws EmptyIntStackException {
    	if (ptr <= 0) {
        	throw new EmptyIntStackException();
        }
        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("스택이 비었습니다.");
    	for (int i = 1; i < ptr; i++) {
       	    System.out.print(stk[i] + " ");
        }
        System.out.println("");
    }
}

/IntStackTester.java

import java.util.Scanner;

class IntStackTester {
	public static void main(String[] args) {
    	Scanner stdIn = new Scanner;
        IntStack s = new int[64]; // capacity가 64인 스택 생성
        
        while (true) {
            System.out.println("현재 데이터 수: " + s.size() + " / " + s.capacity();
            System.out.print("(1)push (2)pop (3)peek (4)dump (0)terminate : ");
            int menu = stdIn.nextInt();
            if (menu == 0) break;
            
            int x;
            switch (menu) {
            	case 1:
                    System.out.print("데이터: ");
                    x = stdIn.nextInt();
                    try {
                        s.push(x);
                    } catch (IntStack.OverflowIntStackException e) {
                        System.out.println("스택이 꽉 찼습니다.");
                    }
                    break;
                    
                case 2:
                    try {
                        x = s.pop();
                        System.out.println("팝한 데이터는 " + x + "입니다.";
                    } catch (IntStack.EmptyIntStackException e) {
                    	System.out.println("스택이 비었습니다.");
                    }
                    break;
               
                case 3:
                    try {
                    	x = s.peek();
                        System.out.println("피크한 데이터는 " + x + "입니다.";
                    } catch (IntStack.EmptyIntStackException e) {
                    	System.out.println("스택이 비었습니다.");
                    }
                    break;
                    
                case 4:
                    s.dump();
                    break;
            }
        }
    }
}