[자료구조] 스택 Stack

0. 스택 Stack 이란 ?

 

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조

데이터의 입력과 출력 순서는 후입선출 (LIFO : Last In First Out)

ex ) 자바 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서 스택 사용

 

푸시 (push) : 스택에 데이터를 넣는 작업

팝 (pop) : 스택에서 데이터를 꺼내는 작업

꼭대기 (top) : 푸시와 팝을 하는 위치

바닥 (bottom) : 스택의 가장 아랫부분

 

 

스택의 push(), pop()

 

 

 

1. 스택 구현

 

int[] stk : 스택 본체용 배열. index 0인 요소가 스택의 bottom 

int max : 스택 용량. 스택에 저장할 수 있는 최대 데이터 수

int ptr : 스택 포인터. 다음 push()를 실행할 위치. 현재 스택에 저장되어 있는 데이터 수. 스택이 비어있으면 num == 0, 스택이 가득 차 있으면 num == max

 

- Stack() : 생성자

public Stack(int capacity) {
	ptr = 0;
	max = capacity;
	try {
		stk = new int[max];
	} catch (OutOfMemoryError e) {
		max = 0;
	}
}

• 매개변수 : 생성할 스택의 용량
• 스택을 생성하면 비어있으므로 ptr은 0
• 매개변수로 전달받은 capacity를 스택 용량을 나타내는 max에 복사
• 요소 수가 max인 배열 stk 생성
• try-catch문을 사용하여 배열 본체 생성에 실패할 경우, max를 0으로 설정하여 다른 메서드가 존재하지 않는 배열에 잘못 접근하는 것을 막음

 

 

- push() : 스택에 데이터를 푸시

public int push(int x) throws OverFlowStackException {
	if(ptr >= max) {
		throw new OverFlowStackException();
	}
    stk[ptr++] = x;
	return x;
}

• 매개변수 : 푸시할 값
• 스택이 가득 차서 푸시할 수 없는 경우, 미리 작성한 OverFlowStackException 을 throw
• 스택에 매개변수로 전달받은 데이터를 추가한 후, 스택 포인터를 증가
• 반환값 : 푸시한 값

 

 

- pop() : 스택에서 데이터를 팝

public int pop() throws EmptyStackException {
	if(ptr <= 0) {
		throw new EmptyStackException();
	}
    int x = stk[--ptr];
	return x;
}

• 스택의 꼭대기에서 데이터를 제거
• 데이터를 실제로 제거하는 것이 아니라 ptr을 감소시킴으로써 다음 push()시 데이터가 덮어씌워짐
• 스택이 비어있어 팝 할 수 없는 경우, 미리 작성한 EmptyStackException 을 throw
• 반환값 : 팝한 값

 

 

- peek() : 스택의 꼭대기 값, 스택에서 다음에 꺼낼 데이터

public int peek() throws EmptyStackException {
	if(ptr <= 0) {
		throw new EmptyStackException();
	}
	return stk[ptr-1];
}

• 스택이 비어있으면 미리 작성한 EmptyStackException 을 throw
• stk[ptr-1]의 값을 확인만 하고 데이터를 변경하지 않으므로 ptr 값은 변하지 않음
• 반환값 : 스택의 꼭대기 값

 

 

- indexOf() : 스택 데이터 탐색

public int indexOf(int x) {
	for(int i = ptr - 1; i >= 0; i--) {
		if(stk[i] == x) {
			return i;
		}
	}
	return -1;
}

• 매개변수 : 검색할 데이터
• 스택에 x와 같은 값의 데이터가 포함되어있는지 탐색 ( 먼저 팝 되는 데이터를 찾기 위해 꼭대기에서 바닥 방향으로 선형 탐색 수행 )
• 반환값 : 존재하면 찾은 데이터의 index, 존재하지 않으면 -1

 

 

- dump() : 스택 안의 모든 데이터 출력

public void dump() {
	if(ptr <= 0) {
		System.out.println("스택이 비어있습니다");
	} else {
		for(int i = 0; i < ptr; i++) {
			System.out.println(stk[i] + " ");
		}
		System.out.println();
	}
}

• 스택에 푸시 된 num개의 데이터를 바닥에서 꼭대기 순으로 모두 출력
• 스택이 비어있으면 "스택이 비어있습니다" 출력

 

 

- 기타 메소드

public void clear() {
	ptr = 0;
}

public int capacity() {
	return max;
}

public int size() {
	return ptr;
}

public boolean inEmpty() {
	return ptr <= 0;
}

public boolean inFull() {
	return ptr >= max;
}

• clear() : 현재 스택의 모든 요소를 삭제. 스택의 배열 요소 값을 변경할 필요 없이 스택포인터 ptr 값만 0으로 변경해주면 됨
• capacity() : 스택의 용량 max값 반환
• size() : 스택의 현재 데이터 수 ptr을 반환
• isEmpty() : 스택이 비어있는지 확인. 비어있다면 true, 아니면 false
• isFull() : 스택이 가득 찼는지 확인. 가득 찼으면 true, 아니면 false