자료구조&기본 알고리즘 입문(자바)- 스택

○ 스택
스택(stack)은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 이렵과 출력순서는
후입선출(LIFO, Last In First Out)이다. (가장 나중에 넣은 데이터를 가장 먼저 꺼낸다).
스택에 데이터를 넣는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고
한다. 테이블에 겹겹이 쌓은 접시처럼 데이터를 넣는 작업도 꺼내는 작업도 위쪽부터 수행하는데, 
이렇게 푸시와 팝을 하는 위치를 꼭대기(top)이라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. 

Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다. 
다음은 메서드의 호출과 실행 과정을 나타낸 것이다. 이 프로그램은 main 메서드르 포함하여 
총 4개의 메서드로 이루어져 있다. 

void(x){/*...*/}

void(y){/*...*/}

void z(){
  x();
  y();
}

int main(){
   z();
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
// 실행 단계
1. main 메서드가 실행되기 전 
2. main메서드 실행(main 메서드 푸시)
3. z 메서드 호출(z 메서드 푸시)
4. x 메서드 호출(x메서드 푸시)
5.x 메서드가 실행을 종료하고 z 메서드로 돌아온다 (x 메서드를 팝)
6. y 메서드를 호출 (y 메서드를 푸시)
7. y 메서드가 실행을 종료하고 z 메서드로 돌아온다 (y 메서드를 팝)
8. z 메서드가 실행을 종료하고 main 메서드로 돌아온다 (z 메서드를 팝)
9. main 메서드가 실행을 종료한다 (main 메서드를 팝)

○ 스택 만들기
스택을 구현하는 프로그램으로, 스택에 저장하는 값은 int 형. 클래스 IntStack을 필드/생성자/메서드 순으로 보면 다음과 같다. 

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

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

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

 

// int형 스택

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의 본체를 생성한다. 따라서 스택 본체의 개별ㅇ ㅛ소는 바닥부터 stk[0],

stk[1]..stk[max-1]이 된다. 

-푸쉬 메서드 push
스택에 데이터를 푸시하는 메서드다. 스택이 가득차서 푸시할 수 없는 경우 예외 OverflowIntStackExcpetion을 
던진다. 

	// 스택에 x를 푸시
	public int push(int x) throws OverflowIntStackException {
		if (ptr >= max)									// 스택이 가득 참
			throw new OverflowIntStackException();
		return stk[ptr++] = x;
	}

예외 처리르 뺴면 실질적으로 1행만으로 된 메서드이고, 전달받은 데이터 x를 배열요소 stk[ptr]에 저장하고,
스택 포인터를 증가(increment)시킨다. 메서드의 반환값은 푸시한 값이다. 
클래스 IntStack의 생성자와 메서드를 사용하여 스택 작업을 수행하면 스택 포인터 ptr값은 반드시 0이상 max 이하가 된다. 
따라서 스택이 가득 찼는지에 대한ㄱ ㅓㅁ사는 관계 연산자 >= 가 아니라 등가 연산자 ==를 사용하여 다음과 같이 수행할 수 있다. 

if (ptr == max)

그러나 프로그래밍 실수와 같은 원인으로 인하여 ptr 값이 잘못 입력되면 max를 초과할 수도 있따. 하지만 위와 같이
부등호로 판단하면 스택 본체 배열의 상한과 하한을 벗어나서 접근하는 것을 막을 수 있다. 간단한 코드 수정이지만 
이런 노력으로 프로그램의 안정성을 높일 수 있다 

- 팝 메서드 pop
스택의 꼭대기에서 데이터를 팝(제거)하고 그 값을 반환하는 메서드. 스택이 비어 있어 팝을 할 수 없는 경우
예외 EMptyINtStackException을 던진다

// 스택에서 데이터를 팝(정상에 있는 데이터를 꺼냄)
	public int pop() throws EmptyIntStackException {
		if (ptr <= 0)									// 스택이 비어 있음
			throw new EmptyIntStackException();
		return stk[--ptr];
	}

먼저 스택 포인터 ptr의 값을 감소시키고 그떄 stk[ptr]에 저장되어 있는 값을 반환한다. 

 

- 피크 메서드 peek

스택의 꼭대기에 있는 데이터를 몰래 엿보는 메서드이다. 스택이 비어 있는 경우

예외 EmptyIntStackException을 던진다. 

	// 스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄) 
	public int peek() throws EmptyIntStackException {
		if (ptr <= 0)									// 스택이 비어 있음
			throw new EmptyIntStackException();
		return stk[ptr - 1];
	}

 

- 검색 메서드 indexOf

스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 
조사하는 메서드. 검색은 꼭대기 쪽에서 바닥 쪽으로 선형 검색을 수행한다. 즉 배열 인덱스가 큰 쪽에서 작은 쪽으로
스캔한다. 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다. 

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

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

-용량을 확인하는 메서드 capacity
capacity 메서드는 스택의 용량(max의 값)을 반환하는 메서드. max 값을 그대로 반환한다.

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

size 메서드는 현재 스택에 쌓여 있는 데이터 수(ptr의 값)를 반환하는 메서드다. 

-스택이 비어 있는지 검사하는 메서드 IsEMpty
IsEmpty 메서드는 스택이 비어 있는지 검사하는 메서드이다. 스택이 비어 있으면 true, 그렇지 않으면 false를 반환한다 

-스택이 가득 았는지 검사하는 메서드 IsFull
IsFull 메서드는 스택이 가득 찼는지 검사하는 메서드다. 스택이 가득 찼으면 true, 그렇지 않으면 false를 반환한다. 

package chap04;
// int형 스택

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

	// 스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄) 
	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.print(stk[i] + " ");
			System.out.println();
		}
	}
}

-스택 안에 있는 모든 데이터를 표시하는 메서드 dump
스택에 쌓여 있는 모든 데이터를 바닥에서 꼭대기 순으로 표시하는 메서드다. 
스택이 비어 있으면 '스택이 비어 있습니다'라고 표시한다 

○ 스택을 사용하는 프로그램2

import java.util.Scanner;
// int형 스택의 사용 예

class IntStackTester {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		IntStack s = new IntStack(64);	// 최대 64개를 푸시할 수 있는 스택

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

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

-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893