Java 자료구조 - Stack

- Stack(스택)

Stack 자료구조는 위 그림 처럼 아래가 막혀있는 통에 위에서부터 값이 들어오는 구조이다. 그렇기 때문에 가장 늦게 들어온 값이 가장 먼저 나가는 LIFO (Last In First Out) 구조이다.

 

다음 코드는 Stack 구조를 배열을 이용하여 구현한 것이다.

public interface InterStack {
	void push(Object data);
	Object pop();
}

public class TestStack implements InterStack{
	int top = -1; // 스택 포인터
	private Object[] elementData;
	
	public TestStack (int size) {
		elementData = new Object[size];
	}
	
	@Override
	public Object pop() {
		if (top == -1) {
			return null;
		} else {
			return elementData[top--];			
		}
	}
	
	@Override
	public void push(Object data) {
		elementData[++top] = data;
		
	}
	
	public static void main(String[] args) {
		TestStack ts = new TestStack(5);
		ts.push(11);
		ts.push(22);
		ts.push(33);
		ts.push(44);
		System.out.println("test : " + ts.pop());
		System.out.println("test2 : " + ts.pop());
	}

}

push를 하면 Stack 구조의 가장 Top위치를 증가시키고 pop을 Top위치를 감소시크는 간단한 구조이다 물론 실제 Java 에서는 이것 보다 좀더 복잡하게 구현되있지만 기본적인 방봅은 위 코드와 동일하다.

 

저또한 좀더 궁굼해서JAVA 쪽 코드를 까보았습니다.

 

Stack은 Vertor을 상속받아 구현한 자료구조이다.  그리고 66라인을 보면 push를 하면 Vector의 addElement 함수를 실행시킵니다. addElement 함수를 보면 elementData 배열 protected Object[] elementData에 elementCount 를  1씩 증가시켜 값을 할당하는 것을 볼 수 있다. 그리고 반대로  pop은 1씩 줄이고 null로 초기화 한다. 그러니 위 구현해본 코드의 top과 elementCount는 같은 기능으로 사용한 것이다.