[자료구조] 스택(Stack)

Stack이란?

Stack은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 자료구조입니다.

추상자료형( abstract data type, ADT )이며, 이는 논리적인 기능을 명시해 놓은 것이라 볼 수 있고, 이는 구현체가 이를 상속받아 구현하는 방식으로 자료형은 Stack이지만 구현은 여러 방법으로 구현할 수 있음을 의미합니다.

 

Stack은 Vector를 상속받아 구현을 하고 있는데 이는 Vector를 구현되 LIFO방식으로 데이터를 다룰 수 있게 다루기 위해 Stack이란 자료형이 존재한다 생각해 볼 수 있습니다.

 

우선 기본적인 기능을 확인해 보겠습니다.

Stack은 Vector를 상속한 ADT이기 때문에 기본적으로 Object []인 elementData로 데이터를 관리하고 있습니다.

 

배열의 크기는  기본적으로 10의 크기로 생성하고 있으며, resizing을 통해 많은 데이터가 들어오더라도 수용할 수 있습니다. 이렇듯 대부분의 기능은 동일하지만, 외부에서 접근할 수 있는 pop메서드를 확인해 보면 elemtnData의 Size를 확인하여 맨 마지막 데이터만을 추출할 수 있도록 구현되어 있는 것을 확인할 수 있습니다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

 

제공하는 기능

Method	기능
push	item을 추가합니다.
pop	최근 들어온 Element를 추출합니다.
peek	최근 들어온 Element를 확인합니다.
search	element를 조회합니다. ( Index를 반환합니다. )

사용처

그럼 Stack은 어떤 곳에서 사용하게 될까요??

웹브라우저 History 즉 뒤로가기 앞으로가기 와 같은 기능처럼 history를 쌓아두고 이를 최신 것부터 접근하는 상황이 있다면 이럴때는 Stack을 사용함으로써 편하게 관리할 수 있습니다.

 

또한 재귀함수와 같이 연산이 루프를 도는 방향의 알고리즘을 구현을 한다면,

최근 접근 한 것들을 접근 할 수 있는 Stack을 통해 쉽게 최근에 넣은 데이터를 꺼내 연산을 하면서 손쉽게 구현할 수 있습니다. 백준 코딩 테스트

References

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html