자바로 구현하는 스택 (Stack) - 1차 수정

스택 (Stack) ?

 

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조(FILO - First In Last Out) 입니다.

 

 

<그림> 스택(Stack)

 

 

스택은 데이터가 들어오는대로 맨 아래로 부터 순서대로 차곡차곡 데이터가 쌓입니다.

그리고, 데이터를 추출한다면 가장 상위 마지막에 들어온 데이터가 먼저 나가게 됩니다.

데이터를 밀어 넣는 행위 를 'Push' 라 하고, 데이터를 빼는 행위 를 'Pop' 이라고 합니다.

그리고 스택의 위치를 'Top' 이라 합니다. (가장 최근 데이터를 가르키는 위치)

스택의 응용분야는 정말 무수히 많습니다.

우리가 간단히 생각하는 브라우져의 뒤로가기 역시 스택이라고 보시면 됩니다.

브라우져에서 다양한 웹사이트를 타고 들어가다가 뒤로가기 버튼을 누르면 가장 처음 내가 들어갔던 페이지가 나올 겁니다.

예를 들어 데이터를 1,2,3,4 순으로 삽입했다면 스택에서 데이터를 추출할 때에는

가장 최근 삽입한 데이터 순서대로 4,3,2,1 의 데이터가 추출됩니다.

자 이제 그럼, 스택이 무엇인지 알아 보았으니 구현 방법에 대해 알아 보도록 하겠습니다.

 

 

(자바에서 java.util.Stack 을 사용하면 JDK 1.0 부터 스택을 사용 할 수 있습니다.)

 

 

참고

[1] 위키백과 (http://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D)

 

 

 

스택의 주요 API

 

push : 스택에 데이터를 삽입한다. (스택의 사이즈를 초과할경우 Overflow 발생)

pop : 스택의 가장 위에 있는 데이터를 추출한다. (스택에 데이터가 없는 경우 Underflow 발생)

empty : 스택이 비어있는지 확인한다.

 

 

 

 

수도코드

 

(1) push 연산 수도코드

push (S, x)
 
  if(top > STACK_SIZE) then Overflow;
  else
    top <- top+1;
    S(top) <- x;

end push()

 

Push 연산시 top 이 스택 사이즈를 초과하는 경우 Overflow (오버플로우) 발생 하며,

스택사이즈를 초과하지 않는 다면 삽입 연산을 수행합니다.

이때 top의 위치는 기본 값은 -1을 가정 하였을때 (배열의 시작은 0 이기 때문)

스택[0] 에 데이터를 삽입합니다.

 

(2) pop 연산 수도코드

pop (S)
 
  if (top == 0) then Underflow;
  else {
     return S(top);
     top <- top-1;
  }

end pop()

 

 

pop 연산시 최근 데이터의 위치를 가르키는 top 이 0 인경우 오버플로우가 발생하며, (데이터 없는 경우)

(실제 소스코드 작성시 배열은 0부터 시작이니 top이 -1 이 되어야 합니다.)

데이터가 스택에 존재한다면 스택[1] 위치에 있는 데이터를 리턴합니다.

그리고 데이터의 위치를 가르키는 top은 스택[1] 에 있는 데이터가 빠져 나갔으므로,

top - 1 연산을 수행하여 빠져나간 데이터의 아래 위치를 가르키도록 합니다. 

 

 

(3) Empty 연산 수도코드

empty ()

  if (top == 0) then
    return true;
  else 
    return false;

end empty()

empty 연산은 스택의 최근 데이터를 위치를 가르키는 top 이 0 인경우 true 를 리턴 하고,

데이터가 존재하면 false 를 리턴 합니다.

 

 

※ 주의

수도코드에서는 스택의 최근 데이터 위치를 가르키는 top 이 0 인경우 데이터가 없다는 것으로 간주 합니다.

하지만 실제 소스코드 작성시 배열을 사용한다면 배열의 시작은 0 이기 때문에

top 을 -1 로 초기화 해야 합므로 주의 하세요!

 

 

 

소스코드

public class Stack {
	 
		private int top = -1;
	    private Object[] stack;
	    private int size = 0;
	     
	    public Stack(int size) {
	        //사이즈 만큼 스택 생성
	        this.stack = new Object[size];
	    }
	 
	    public void push(Object element) {
	         
	        if (top >= stack.length) { // 사이즈를 넘어가면
	            throw new StackOverflowError();
	        }
	         
	        size++;
	        stack[++top] = element; 
	    }
	     
	    public Object pop () {
	         
	        if (top == -1) { // 데이터 없음
	            throw new StackUnderflowError();
	        }
	        
	        size--;
	        return stack[top--];
	    }
	     
	    public boolean isEmpty() {
	        return top == -1 ? true : false;
	    }
	     
	    public int getStackSize() {
	        return size;
	    }
	     
	    class StackUnderflowError extends RuntimeException {
	         
	    }
	     
}

    public static void main(String[] args) {

        Stack s = new Stack(5);
        s.push(10);
        s.push(11);
        s.push(12);
        s.push(13);
        s.push(14);
        
        System.out.print("데이터 추출 순서 : ");
        for(int i=0;i<s.getStackSize();i++) {
            System.out.print(s.pop() + " ");
        }
        System.out.println("\n스택 isEmpty : " + s.isEmpty());
    }
}

 

 

 

위 코드를 그림으로 표현하자면 아래와 같습니다.

 

10, 11, 12, 13, 14 의 데이터를 순서대로 Push 하는 경우

아래 에서 부터 10, 11, 12, 13, 14 순으로 데이터가 삽입이 되며,

Pop 하는 경우 14, 13, 12, 11, 10 순으로 Pop 이 됩니다.

그리고 Top은 그림에서는 현재 배열이 모두 꽉 차 있고, 가장 최근에 삽입된 위치는 4 입니다.

만약 여기서 14를 Pop 한경우 Top 은 3이 됩니다.

 

 

결과

 

 

[2014-11-02]

size 감소에 대한 문제 수정했습니다.

그와 동시에 Object 로 받도록 했는데 제네릭 쓰려다 행여나 코드 해독이 불가능 하실거 같은 분들이 계실까봐

오브젝트로 받도록 했습니다.

POP 할때 캐스팅이 필요한데, 이는 곧 박싱에 대한 오버헤드가 발생하므로 제네릭으로 바꿔보시길!