[자료 구조] 4. 배열을 활용해 Stack 구현하기

[자료 구조] 4. 배열을 활용해 Stack 구현하기

 

 

1. Stack이란?

(1) Stack의 정의: 스택(Stack)은 데이터를 일시적으로 저장하기 위한 선형(linear) 자료 구조로,

마지막에 들어간 자료가 처음으로 나오는 형태이다. (=LIFO 원칙. 후입선출)

---

 

(2) Stack의 주요 연산

-Push: 스택의 맨 위에 요소를 추가한다.

-Pop: 스택의 맨 위의 요소를 꺼내, 삭제한다.

-Peek/Top: 맨 위의 요소를 반환하지만, 제거하지 않는다.

-IsEmpty: 스택이 비었는지 확인하고, 비어있다면 true/비어있지 않다면 false를 반환한다.

-Size: 스택에 저장된 요소의 개수를 반환한다.

 

---

(3) 배열을 활용해 Stack을 구현해보자.

 

(1) TencoIntArray 수정 버전

(2) MyArrayStack

(1) 멤버 변수
-int top: 스택의 최상위 요소(=가장 마지막에 들어온 요소)를 가리킨다.
-TencoIntArray arrayStack: TencoIntArray를 포함관계로 가져온다.


(2) 사용자 정의 생성자
1. 첫번째 사용자 정의 생성자
-top=0 : 스택 포인터를 초기화
-arrayStack = new TencoIntArray : 배열 칸 10개를 생성한다.

2. 두번째 사용자 정의 생성자
*int size(배열 칸 수)를 파라미터값으로 받음.

-top=0 : 스택 포인터를 초기화
-arrayStack = new TencoIntArray(size) : 입력받은 값과 같은 배열 칸 수를 지니는 스택 생성


(3) getSize() 메서드: top(스택 포인터, 최상위 요소 가리킴)을 반환

(4) isEmpty() 메서드: return top == 0;
-top(최상위 요소 가리키는 포인터)가 비어있다면 true / 비어있지 않다면 false 반환

(5) isFull() 메서드 : return top == arrayStack.ARRAY_SIZE;
*ARRAY_SIZE: 배열의 칸 수를 가리키는 상수. 10(정수형)을 지닌다.
-스택의 최상위 요소가 배열 칸 수와 같은가?
=> 스택이 가득 찼는가? (true/false 반환)

(6) printAll() 메서드: arrayStack.printAll();
*printAll(): 배열이 비어있지 않다면, 배열의 길이만큼 배열의 요소를 반복 출력하는 메서드.
-arrayStack의 모든 요소들을 출력하는 메서드.

(7) push() 메서드:
-만약 top==0이라면, "Stack is Empty" 출력
-만약 top!=0이라면, arrayStack.removeElement(top-1); top--; 실행
*removeElement: 포인터에 해당되는 배열이 비어있지 않고,

(8) pop() 메서드:

(9) peek() 메서드:

package Structure;

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

	int[] intArr;
	int count; // 배열 안에 들어간 요소의 갯수
	public final int ARRAY_SIZE;
	public static final int ERROR_NUM = -99999;

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

	// 기능 설계
	// 배열 요소의 제일 뒤의 값을 추가하는 기능을 가진다.
	public void addElement(int inputData) {
		// 방어적 코드 필요
		if (count >= ARRAY_SIZE) {
			System.out.println("메모리 공간이 가득 찼습니다.");
			return; // 실행의 제어권 반납
		}
		intArr[count] = inputData;
		count++;
	}

	// 배열에 요소를 추가하는 기능
	// 배열에 지정된 인덱스 위치의 값을 추가하는 기능

	public void insertElement(int position, int inputData) {
		// 방어적 코드 작성 1
		if (count >= ARRAY_SIZE) {
			System.out.println("메모리 공간이 가득 찼습니다.");
			return;
		}
		// 방어적 코드 2
		//                     10           0
		if (position < 0 || position > ARRAY_SIZE) {
			System.out.println("지정한 인덱스 번호가 잘못 되었습니다.");
			return;
		}
		// 요청 값: position -> 3
		// 현재 [11,12,13,14,15]
		for (int i = (count - 1); i >= position; i--) {
			intArr[i + 1] = intArr[i]; // 하나씩
			// intArr[5] = 15; 수행1
			// intArr[4] = 14; 수행2
		}
		intArr[position]=inputData;
		count++;
	}
	// 지정한 인덱스 번호에 요소를 꺼내주기
	public int getElements(int position) {
		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) {
		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++;
	}
	
	// 배열의 크기가 아닌 현재 요소의 갯수를 반환하는 것
	public int getCountSize() {
		return count;
	}
	
	// 현재 요소가 하나도 없는 상태이다.
	public boolean isEmpty(){
		if(count==0) {
			return true;
		} else {
			return false;
		}
	}

	// 지정한 인덱스 번호에 요소를 삭제하는 기능
	public void removeElement(int position) {
		
		if(isEmpty()) {
			System.out.println("삭제할 요소가 없습니다.");
		} 
		// position: <--- 2
		// 인덱스 범위를 잘못 지정했다면 방어적 코드
		System.out.println("LOG 2 : "+ count);
		if((position<0) || (position>=count)) {
			System.out.println("잘못된 요청입니다.");
		}
		//   0     1     2
		// [100] [200] [300]
		//           2          3   ---> 횟수로는 한 번 반복
		for(int i=position; i<count; i++) {
			System.out.println("LOG 3 : "+i);
		//         2          3
			intArr[i]=intArr[i+1];
			// [100] [200] [0] [0]
		}
		// 3
		count--;
	}
	// 지정한 인덱스 번호에 맞는 요소를 출력하는 기능

}

package Structure;

public class MyArrayStack {

	int top; // 스택의 최상위 요소를 가리킴.
	TencoIntArray arrayStack;

	public MyArrayStack() {
		top = 0; // 스택 포인터 초기화
		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;
		// 최상위 요소가 비었다면 트루, 비지 않았다면 false
	}

	// 스택의 요소가 가득 찼는지 확인하는 메서드를 만들어보자.
	public boolean isFull() {
		return top == arrayStack.ARRAY_SIZE;
	}
	
	// 스택의 모든 요소를 출력하는 기능
	public void printAll() {
		arrayStack.printAll();
	}
	
	// 스택에 데이터를 추가하는 기능 : 맨 뒤에 데이터 추가
	public void push(int data) {
		// 방어적 코드 작성
		if(isFull()) {
			System.out.println("메모리가 가득 가득");
			return;
		} 
		arrayStack.addElement(data);
		top++; 
	}
	
	// 스택에서 데이터를 제거하고 반환하는 메서드
	public int pop() {
		if(top==0) {
			System.out.println("Stack is empty.");
		}
		int temp = peek();
		System.out.println("LOG 1 : "+(top - 1));
		arrayStack.removeElement(top - 1);
		top--;
		return temp;
	}
	
	// 스택의 최상위 요소를 반환하지만, 제거는 하지 않음
	public int peek() {
		if(top == 0) {
			return TencoIntArray.ERROR_NUM;
		}
		return arrayStack.getElements(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

} // end of class