배열을 활용한 Stack 구현

Stack

스택(Stack)은 데이터를 일시적으로 저장하기 위한 선형 자료구조로, "후입선출"(Last In, First Out; LIFO) 원칙을 따른다. 이 원칙은 가장 마지막에 추가된 요소가 가장 먼저 제거된다는 것을 의미한다.
스택을 일상생활의 예로 설명하면, 식당에서 사용된 접시를 쌓아 두었다가 사용할 때 가장 위에 있는 접시부터 꺼내는 것과 비슷하다.

 

 

 

스택의 주요 연산

• Push : 스택에 요소를 추가하는 연산. 스택의 맨 위에 새로운 요소를 놓는다.
• Pop : 스택에서 요소를 제거하는 연산. 스택의 맨 위에 있는 요소를 꺼내며, 그 요소는 스택에서 삭제된다.
• Peek 또는 Top : 스택의 맨 위에 있는 요소를 반환하지만, 제거하지는 않는다. 스택의 최상위 요소를 확인할 때 사용한다.
• IsEmpty : 스택이 비어 있는지 확인한다. 비어 있다면 true를, 그렇지 않다면 false를 반환한다.
• Size : 스택에 저장된 요소의 개수를 반환한다.

 

---

 

package structure;

import java.util.Iterator;

/**
 * 배열을 활용한 클래스를 설계하자. 
 * 물론, 이미 자바 표준 API 개발자 들이 잘 만들어 준 클래스들이 존재하지만,
 *  직접 기능을 확장해서 만들어 보자.
 */

public class TencoIntArray {

	int[] intArr; // 배열 선언
	int count; // 배열 안에 들어간 요소의 갯수 관리
	public final int ARRAY_SIZE; // 상수 선언 , 초기화 해 주어야 오류 없음.
	public static final int ERROR_NUM = -999999999;

	public TencoIntArray() {

		count = 0;
		ARRAY_SIZE = 10;
		intArr = new int[ARRAY_SIZE];

	}

	// 생성자 오버로딩
	public TencoIntArray(int size) {
		count = 0;
		ARRAY_SIZE = size;
		intArr = new int[ARRAY_SIZE];
		// ex) size = 100 -> 100칸 배열
	}

	// 기능 설계
	// 배열 요소의 제일 뒤에 값을 추가하는 기능을 가짐
	public void addElement(int inputData) {
		// 방어적 코드 작성 ( 인덱스 길이를 벗어날 경우)
		if (count >= ARRAY_SIZE) {
			System.out.println(" 메모리 공간이 가득찼습니다. ");
			return; // 더 이상 코드 진행이 실행되지않도록 실행의 제어권 반납!
		}

		// intArr[count++] = inputData; // 가능
		intArr[count] = inputData;
		count++; // 증감연산자 사용

	}

	// 지정한 인덱스 번호에 맞는 요소를 출력하는 기능
	public int getElement(int position) { 
		// 배열의 크기는 10 개 , 현재 안에 들어가있는 요소의 갯수는 3개
		// [0] [1] [2]
		
		// 방어적 코드 작성  3 > 3 - 1
		if (position < 0 || position > count - 1) {
			System.out.println(" 검색 위치 오류 ! 현재 리스트의 갯수는 " + count + "개 입니다.");
			return ERROR_NUM;
		} // 아니라면?!
		return intArr[position]; // 사용자가 요청했던 인덱스번호 꺼내주기

	}

	// 요소를 전체출력하는 기능
	public void printAll() {
		// 방어적 코드 작성
		if (count == 0) {
			System.out.println(" 출력할 내용이 없습니다! ");
			return;
		}
		// 요소 하나씩 담고 수행하고 담고 수행하고 반복
		// for (int i : intArr) {
		// System.out.println(intArr[i]);
		// }

		for (int i = 0; i < intArr.length; i++) {
			System.out.println(intArr[i]);
		}
	}

	// 요소를 전체삭제하는 기능
	public void removeAll() {
		for (int i = 0; i < intArr.length; i++) {
			intArr[i] = 0;
		}
		count = 0; // !! 현재 요소의 갯수 상태가 몇 개인지 항상 관리하고 처리해줘야 한다.
	}

	// 배열의 크기가 아닌 현재 요소의 갯수를 반환하는 기능
	public int getCountSize() {
		return count;
	}

	// 현재 요소가 하나도 없는 상태이다.
	public boolean isEmpty() { // boolean일 때, get메서드를 is로 사용한다.
		if (count == 0) {
			return true;
		} else {
			return false;
		}

	}

	// 지정된 인덱스 위치에 값을 추가 하는 기능
	public void insertElement(int position, int inputData) { // (위치 값, 저장 하고자 하는 데이터값)

		// 방어적 코드 작성 1
		if (count >= ARRAY_SIZE) {
			System.out.println("메모리 공간이 가득찼습니다.");
			return; // 실행의 제어권 반납
		}
		
		// 방어적 코드 작성 2
		if (position < 0 || ARRAY_SIZE < position) {
			// int 범위를 벗어난 상태!
			System.out.println(" 지정한 인덱스 번호가 잘못되었습니다! ");
			return;
		}
		// 요청값 : position -> 3
		// [11,12,13,14,15] -> 13 [position -> 3] 14
		for (int i = count - 1; i >= position; i--) {
			// 현재 갯수의 -1 부터 시작하게 i 가 설정됨
			intArr[i + 1] = intArr[i];
			// intArr [5] = 15
			// intArr [4] = 14

		}

		intArr[position] = inputData;
		count++;

	}

	// 지정한 인덱스 번호에 요소를 삭제하기!
	public void removeElement(int position) {
		
		// position : 2
		System.out.println(" Log 2 : " + count);
		// 방어적 코드!
		if (isEmpty()) {
			System.out.println("삭제할 요소가 없습니다!");
		}
		// 인덱스 범위를 잘못 지정했을때 방어적 코드!
		if (position < 0 || position >= count) { // || < 또는
			System.out.println(" 잘못된 요청입니다! ");
		}

		//   0          1         2
		// [100] [200] [300]
		
		for (int i = position; i < count - 1; i++) {
			System.out.println(" Log 3 : " + i);
			// 0
			// 0 + 1
			intArr[i] = intArr[i + 1];
		}
		count--;
	}

}

 

package structure;

public class MyArrayStack {

	int top; // 스택의 최상위 요소를 가리킨다.
	TencoIntArray arrayStack;
	
	public MyArrayStack() {
		top = 0; // 스택 포인터 초기화 (top의 기본 위치)
		arrayStack = new TencoIntArray(); // 칸이 10개인 배열이 생성 됨.
	}
	
	public MyArrayStack(int size) {
		top = 0;
		arrayStack = new TencoIntArray(size);
	}
	
	// 스택의 크기 (요소 갯수) 를 반환
	public int getSize() {
		return top;
	}
	
	// 스택이 비어 있는지 확인하는 메서드
	public boolean isEmpty() {
		return top == 0; // 비어 있으면 true가 반환
	} 
	
	// 스택의 요소가 가득 찼는지 확인 하는 메서드
	public boolean isFull() {
		return top == arrayStack.ARRAY_SIZE; // arrayStack의 최대 사이즈
	}
	
	// 스택의 모든 요소를 출력하는 기능
	public void printAll() {
		arrayStack.printAll();
	}
	
	// 스택에 데이터를 추가하는 기능
	public void push(int data) {
		// 방어적 코드 작성 (메모리가 더 이상 없을 때 발생하는 오버플로우)
		if(isFull()) {
			System.out.println("메모리가 가득 찼습니다.");
			return;
		}
		
		arrayStack.addElement(data);
		top++;
	}
	
	// 스택에서 데이터를 제거하고 반환하는 메서드
	public void pop() {
		if(top == 0) {
			System.out.println("stack is empty");
		}
		System.out.println("Log 1 : " + (top - 1));
		arrayStack.removeElement(top - 1);
		top--;
	}
	
	// 스택의 최상위 요소를 반환하지만, 제거는 하지 않는 기능
	public int peek() {
		if(top == 0) {
			return TencoIntArray.ERROR_NUM;
		}
		
		return arrayStack.getElement(top -1);
	}
	
	// 코드 테스트
	public static void main(String[] args) {
		
		MyArrayStack stack = new MyArrayStack();
		stack.push(100);
		stack.push(200);
		stack.push(300);
		
		// 전체 출력
		//stack.printAll();
		stack.pop(); // 버그 발생 → pop의 제거된 요소를 반환할 수 있도록 코드를 수정하라.
		System.out.println("------------------------");
		//stack.printAll();
		System.out.println(stack.peek());
		System.out.println("------------------------");
		stack.printAll();
		
	} // end of main
	
}