[data structure] 자료구조 스택(stack) 알고리즘 이란 ?? (java 로 구현)

Q. 스택에 대해 알아보자.

1. 스택(Stack) ??

2. 스택과 함께하는 대표적인 기능들(push, pop, isEmpty, isFull)과 SP

3. 심화 : 동적배열을 사용하는 스택

1. 스택(Stack) ??

흔히 자료구조를 배울때 항상 나오는것이 스택입니다.

스택은 데이터를 (임시)저장하는 저장방식입니다.

스택은 일반적으로 아래와 같은 모습을 지니고 있습니다.

[그림] 위키백과 스택

http://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

스택을 표현할때 접시를 쌓아올린것과 같은 형태를 지니게 되는데,

이 형태를 갖는 이유는 메모리의 가장 끝(가장 아래쪽)에서부터 사용하기 때문이라고 합니다.

(확실하지 않을수 있음)

스택은 접시를 쌓아올린것과 같은 모습이기 때문에,

가장 상위 것만 접근이 가능한 제한적으로만 접근할수 있는 나열 구조입니다.

가장 상위, 가장 최근 것만 넣고 빼고 할 수 있기 때문에,

후입선출(LIFO, Last-In First-Out) 이라고 합니다.

스택은 가장 상위에서만 빼고 넣을수 있는 선형구조로 되어 있습니다.

접근 방법은 가장 상위의 목록만 가능하며,

데이터를 넣을때는 푸시(push),

데이터를 꺼낼때는 팝(pop) 이라고 합니다.

아래 표는 push와 pop을 했을 때의 결과입니다.

			"D"
		"C"	"C"	"C"
	"B"	"B"	"B"	"B"
"A"	"A"	"A"	"A"	"A"
push("A");	push("B");	push("C");	push("D");	pop();

스택은 push나 pop을 할때의 해당 값의 위치를 알고 있어야 하는데,

그 위치를 기억하고 있는 것이 스택 포인터 (SP, Stack Pointer) 라고 합니다.

스택 포인터는 다음 값이 들어갈 위치를 가르킵니다. (SP 의 기본 값은 -1 입니다.)

	<- SP(스택 포인터) 위치
"C"
"B"
"A"
스택(Stack)	스택포인터(Stack Pointer)

2. 스택과 함께하는 대표적인 기능들(push, pop, isEmpty, isFull)과 SP

스택이 필요한 대표적인 기능(메소드) 에는 4가지가 있습니다.

스택에 데이터를 넣는 push

스택의 최 상위 값을 가져오는 pop

스택이 비어있는지를 확인하는 isEmpty

스택이 꽉차 있는지를 확인하는 isFull

이렇게 대표적인 기능(메소드) 들이 있고,

부가적으로 스택 포인터 SP가 있습니다.

가장 먼저 push는 아래와 같이 구성됩니다.

public void push( Object o ) { if( isFull( sp ) ) { System.out.println( "Overflow" ); return; } stack[sp++] = o; }

SP(스택 포인터)가 스택의 isFull() 을 호출하여 최대크기와 같다면 오류를 발생시키고,

그외의 경우에는 스택의 최상위 위치에 값을 집어 넣습니다.

두번째로 pop 은 아래와 같이 구성됩니다.

public Object pop() { if( isEmpty( sp ) ) { System.out.println( "Underflow" ); return null; } Object o = stack[--sp]; stack[sp] = null; return o; }

SP 가 0으로 초기값과 같다면, Underflow 를 발생시키고,

그외의 경우에는 stack[--sp] 하여 스택의 최상위 위치의 값을 꺼내옵니다.

세번째로 isEmpty 는 아래와 같이 구성됩니다.

private boolean isEmpty( int _cnt ) { return _cnt == 0 ? true : false; }

입력된 값이 최초 값과 같다면 true 를 리턴하고,

그외의 경우에는 false 를 리턴 합니다.

마지막으로 isFull 은 아래와 같이 구성됩니다.

private boolean isFull( int _cnt ) { return _cnt == MAX_SIZE ? true : false; }

SP 의 값이 MAX_SIZE 와 같다면 true 를 리턴하고,

그외의 경우에는 false 를 리턴 합니다.

그리고 부가적으로 스택의 위치를 담당하는 SP(스택포인터) 는,

private int sp = 0;

0 을 기본값으로 가지고 생성 됩니다.

3. 심화 : 동적배열을 사용하는 스택

위와 같이 구성하였을 경우 스택에는 MAX_SIZE 라는 최대 크기가 존재해야 합니다.

그래야 SP(스택포인터) 와 MAX_SIZE 를 비교하여 isFull 오류를 내야 하기 때문입니다.

그럼 최대 크기가 없는 스택을 만들어 보겠습니다.

바로 java 의 arraycopy 를 사용하면 쉽게 만들수 있습니다.

public void push( Object o ) { if( isFull( sp ) ) { Object[] arr = new Object[MAX_SIZE * 2]; System.arraycopy( stack, 0, arr, 0, MAX_SIZE ); stack = arr; MAX_SIZE *= 2; } stack[sp++] = o; }

가장 먼저 기존 스택보다 확장된 배열을 생성합니다.

이때 크기는 통상적으로 기존 스택의 2배 크기만큼으로 생성합니다. (보라색)

그리고, System.arraycopy 를 활용하여 스택의 0번째부터, MAX_SIZE 만큼을

arr 배열에 0번째부터 복사합니다. (빨간색)

복사를 마치고 arr 의 참조값을 stack 에 덮어씌웁니다. (녹색)

마지막으로 MAX_SIZE를 2배 만큼 증가 시켜줍니다.

이렇게 해서 스택이 가득 차면 자동으로 확장되는 스택을 만들어 보았습니다.

쉽게 이해가 되시나요 ??

참조 : 위키백과 http://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

참조 : C로 쓴 자료구조론 2nd Edition 113 page ~ 127 page