[Algorithms]Stack_스택

Stack_스택

데이터를 일시적으로 저장하기 위한 자료구조. 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

 

1. 스택이란?

• Stack. LIFO : Last In First Out
• push : 데이터를 스택에 넣는 작업
• pop : 스택에서 데이터를 꺼내는 작업
• peek : top에 해당하는 데이터를 읽는 작업. top의 변화는 없다.
• top : push와 pop이 일어나는 장소
• bottom : 스택의 가장 아랫부분. 가장 처음 데이터가 들어간 장소
• 아래의 Data를 Java에서의 Method로 바꿔도 작동 원리는 동일하다.

 

 https://media.vlpt.us/images/sbinha/post/17a3cf61-fb95-4970-b66c-92a71b99846b/Screenshot 2020-04-20 19.07.55.png

 

2. 스택만들기

▶︎ 구현코드

package com.study.Algorithm;
// int형 스택

public class IntStackMake {
	private int max;			
	private int ptr;			
	private int[] stk;			

	// 실행 시 예외 : 스택이 비어 있음
	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() { }
	}

	// 실행 시 예외 : 스택이 가득 참
	public class OverflowIntStackException extends RuntimeException {
		public OverflowIntStackException() { }
	}

	// 생성자
	public IntStackMake(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();
		}
	}
}

▶︎ 코드 설명

1. stk : 스택 본체용 배열
    - push된 데이터를 저장하는 stack 본체의 배열. 인덱스 값이 0인 요소가 bottom, 가장 먼저 저장된 데이터.

2. max : 스택 용량
    - 스택의 용량, 스택이 쌓을 수 있는 최대 데이터 수를 나타내는 필드. 배열 stk의 크기/요소의 수 와 같다.

3. ptr : 스택 포인터
    - 스택에 쌓여 있는 데이터 수. stack pointer. 가장 마지막에 들어간 데이터의 인덱스 + 1을 한 수와 같다. 쌓인 데이터가 하나도 없다면 0, 가득찼다면 max와 같다.
    - 새로운 데이터를 삽입할 인덱스를 기억하는 용도로 사용된다.

4. 생성자 IntStackMake
    - 스택 본체용 배열을 만들기 위한 생성자. parameter로 전달받은 capacity값이 max값과 배열인 stk의 배열 크기값이 된다.

5.  Method
    1. push : 데이터를 push한다.
    2. pop : 데이터를 pop한다.
    3. peek : 
        - top의 데이터를 읽는다. 이때 데이터의 입력(push)과 출력(pop)이 없으므로 ptr는 변하지 않는다.
    4. indexOf : 
        - 스택의 본체 배열에 찾고자 하는 값(x)이 들어있는지 확인하고, 들어 있다면 어디에 있는지를 확인하여 index를 되돌려준다.
        - 찾는 값이 없다면 -1 반환.
        - 만약 동일한 값이 2곳에 존재한다면, top를 기준으로 가까운 곳의 인덱스를 반환. 그 이유는 먼저 pop되는 데이터 값이기 때문이다.
    5. clear : 스택에 쌓인 모든 데이터를 지운다.
    6. capacity : 스택의 용량을 확인한다. 스택 배열의 크기인 max값을 그대로 반환.
    7. size : 현재 쌓여있는 데이터의 수를 확인한다. ptr의 값을 반환.
    8. IsEmpty : 스택이 비어있는지 확인하고, 비었다면 T, 아니라면 F 반환.
    9. IsFull : 스택이 가득 찼는지 확인하고, 찼다면 T, 아니라면 F 반환.
    10. dump : 
        - 스택 안에 있는 모든 데이터의 값을 bottom부터 top까지 순서대로 표시한다.
        - 스택이 비었다면, 스택이 비어있습니다, 라고 알려준다.

 

스택 사용 코드

package com.study.Algorithm;
import java.util.Scanner;
// int형 스택의 사용 예

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

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

			int menu = sc.nextInt();
			if (menu == 0) break;

			int x;
			switch (menu) {
			 case 1: 							// 푸시
				System.out.print("데이터：");
				x = sc.nextInt();
				try {
					isk.push(x);
			 	} catch (IntStackMake.OverflowIntStackException e) {
					System.out.println("스택이 가득 찼습니다.");
				}
				break;

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

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

			 case 4: 							// 덤프
				isk.dump();
				break;
			}
		}
	}
}

▶︎ 결과

 

 

[자료출처: www.notion.so/f3126e5751674211aa31daf065847e85]