11.09.(수) Java-15: 스택

스택

스택은 배열의 한 종류로, 출력방식에서의 차이가 있을 뿐이다.

스택은 임시로 데이터를 저장하는 기능을 가지며, 나중에 입력된 데이터를 먼저 출력할 수 있는 기능을 가진다.

이런 특성을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다.

출력하고난 뒤에 데이터는 스택에서 제거된다.

 

스택 메소드

• push : 스택에 데이터 담기
• pop : 스택의 맨 위에 있는 데이터 꺼내기
• peek : 스택의 맨 위에 있는 데이터 반환하기
• dump : 스택의 정보 알아내기
• search : 입력한 데이터가 위치한 index값 구하기
• empty : 스택내의 모든 데이터 지우기

위 메소드를 이용해서 스택이 어떻게 생겼는지 알아보자.

메소드를 구성하는 구현클래스와 실행클래스 두개로 나누어 코드를 짰다.

package sw.search;

public class IntStack {
	private int capacity;	// 배열의 크기
	private int[] stk;	// 데이터를 담을 배열
	private int ptr = 0;	// 스택의 포인터 : 멤버영역일때 초기값 자동설정됨
	
	// 생성자 메소드
	public IntStack(int capacity) {
		this.stk = new int[capacity];	// 전달받은 매개변수를 stk배열의 크기로 설정
		this.capacity = capacity;
	}
	
	// push 메소드
	public int push(int inData) throws OverflowIntStackException {
		// 오버플로우(데이터가 넘칠때) 예외처리
		if(this.capacity==this.ptr) {	// 배열의 크기 = 최대 index 일때
			throw new OverflowIntStackException(); 
		}
		return stk[ptr++] = inData;	// ptr위치에 data를 담고, ptr은 1증가 시킨다
	}
	
	// pop 메소드
	public int pop() throws EmptyIntStackException{
		if(this.ptr==0) {
			throw new EmptyIntStackException();
		}
		return stk[--ptr];	// 가장 마지막으로 저장된 값 (제일 위에 있는 값)을 꺼낸다
	}
	
	// peek 메소드
	public int peek() throws EmptyIntStackException{
		if(this.ptr==0) {
			throw new EmptyIntStackException();
		}
		return stk[ptr-1];	// 원래 ptr값은 유지
	}
	
	// dump 메소드
	public void dump() throws EmptyIntStackException{
		if(this.ptr==0) {
			throw new EmptyIntStackException();
		}
		for(int i=0; i<ptr; i++) {
			System.out.println("stk[" + i + "] = " + stk[i]);
		}
	}
	
	// search 메소드
	public int indexOf(int searchData) {
		for(int i=ptr-1; i>=0; i--) {
			if(stk[i]==searchData) {
				return i;
			}
		}
		return -1;
	}
	
	// empty 메소드
	public void makeEmpty() {
		ptr = 0;	// 포인터 처음 위치로 돌려주면 초기화가 된다
	}
	
	// info 용량 메소드
	public int capacity() {
		return this.capacity;
	}
	
	// info 데이터 수 메소드
	public int size() {
		return ptr;
	}
	
	// info empty여부
	public boolean isEmpty() {
		if(ptr==0) {
			return true;
		}else {
			return false;
		}
	}
	
	// 오버플로우 발생 시 처리할 예외내부클래스 생성
	public class OverflowIntStackException extends RuntimeException{
		public OverflowIntStackException() {}
	}
	
	// 스택이 비었을 처리할 예외내부클래스 생성
		public class EmptyIntStackException extends RuntimeException{
			public EmptyIntStackException() {}
	}
}

package sw.search;

import java.util.Scanner;

public class IntStackMain {
	public static Scanner sc = new Scanner(System.in);
	
	public static void startStack() {
		IntStack stack = new IntStack(5);	// 스택 객체를 생성하고, 스택의 크기를 설정할 수 있음
		
		do {
			// 메뉴 작성하기
			System.out.print("(1) PUSH  (2) POP  (3) PEEK  (4) DUMP  (5) SEARCH  (6) EMPTY  (7) INFO  (0) 종료 -> ");
			int menu = sc.nextInt();
			
			if(menu==0) {
				System.out.println("종료했습니다.");
				break;
			}	// 종료
			
			switch(menu) {
			case 1:
				// push : 데이터를 스택에 담기
				System.out.print("데이터 입력 : ");
				int inData = sc.nextInt();
				try {
					stack.push(inData);
				}catch(IntStack.OverflowIntStackException e) {
					System.out.println("스택이 가득 찼습니다.");
				}
				break;
			case 2:
				// pop : 스택에서 제일 마지막으로 저장된 값 꺼내기
				try {
					int popData = stack.pop();
					System.out.println(popData + " 꺼냄.");
				}catch(IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비었습니다.");
				}
				break;
			case 3:
				// peek : 스택에서 제일 마지막으로 저장된 값 구하기
				try {
					int topData = stack.peek();
					System.out.println("마지막으로 담긴 데이터 : " + topData);
				}catch(IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비었습니다.");
				}
				break;
			case 4:
				// dump : 스택의 정보 알아내기
				try {
					stack.dump();
				}catch(IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비었습니다.");
				}
				break;
			case 5:
				// search : 입력한 데이터가 위치한 index값 구하기
				System.out.print("검색값 : ");
				int searchData = sc.nextInt();
				int idx = stack.indexOf(searchData);
				if(idx>=0) {	// 스택에 데이터가 있을 때
					System.out.println(searchData + "은(는) " + idx + "번 index위치에 있습니다.");
				}else {		// 스택에 데이터가 없을 때
					System.out.println(searchData + "은(는) 없습니다.");
				}
				break;
			case 6:
				// empty : 스택 내의 모든 데이터를 지우기
				stack.makeEmpty();
				break;
			case 7:
				// info : 용량, 데이터 수, 데이터 정보, empty 여부
				System.out.println("저장 가능한 데이터 수 : " + stack.capacity());	// 용량
				System.out.println("현재 데이터 수 : " + stack.size());
				try {
					stack.dump();
				}catch(StackInt.EmptyIntStackException e) {}
				System.out.println("스택이 " + (stack.isEmpty() ? "비어있습니다.":"비어있지 않습니다."));
				
				break;
			default:
				// 메뉴를 잘못 선택했습니다.
				System.out.println("메뉴를 잘못 입력하였습니다. 0~8 사이의 값을 입력하세요.");
			}
		}while(true);
	}
	
	public static void main(String[] args) {
		startStack();
	}
}