스택 알고리즘 구현

스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.(LIFO last in first out)

스택에 데이터를 넣는 작업을 푸시라 하고 스택에서 데이터를 꺼내는 작업을 팝이라고 한다.

데이터를 스택에 푸시하고 팝하는 과정을 나타냄

1. 스택 알고리즘 구현

push() 데이터 넣는 메서드

pop() 데이터 빼는 메서드

peek() 맨 꼭대기 요소 보는 메서드

dump() 모든 요소 보는 메서드

package myTest1;
 
import java.util.Scanner;
 
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[ptr++] = x;
    }
    
    // 스택의 꼭대기에 있는 데이터를 제거(팝) 하고 그 값을 반환하는 메서드
    public int pop() throws EmptyIntStackException{
        if(ptr <= 0){
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }
    
    // 스택의 꼭대기에 있는 데이터를 몰래 엿보는 메서드(peek 메서드 )
    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.print(stk[i] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntStack stack = new IntStack(64);    // 최대 64개를 푸시할 수 있는 스택
        
        while(true){
            System.out.println("현재 데이터 수 : " + stack.size() + " / " + stack.capacity()); 
            System.out.print("(1) 푸시 (2) 팝 (3) 피크 (4) 덤프 (5) 종료 : ");
            int menu = scanner.nextInt();
            if(menu == 0) break;
            
            int x;
            switch(menu){
            
            case 1:
                System.out.print("데이터 : ");
                x = scanner.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;
            }
        }
    }
}

결과

소스코드 첨부

myTest1.zip