자료구조 : Stack

이번 포스팅에서는 자료구조 중 가장 유명하다고 해도 과언이 아닌 스택에 대해서 알아보도록 하겠습니다. 

 

Stack

 

스택은 가장 전형적인 LIFO (Last In First Out) 구조로서 개발자들에게 사랑받는 자료구조 중 하나입니다. 

 

스택이 사용되는 것은 가장 대표적으로 홈페이지의 뒤로가기 버튼과 ctrl + z인 undo 기능 계산기의 계산알고리즘 등이 있습니다. 

 

하지만 요즘은 스택을 사용하기 보단 Deque (이하 데크)를 사용하는 것을 더 추천하긴 합니다. Deque는 Double Ended Queue의 약자로 상황에따라 해당 컬렉션을 스택으로 쓸 수도 큐로 쓸 수도 있는 인터페이스입니다. 

 

데크는 LIFO 실행에 있어서 더 완벽하고 일관성있기 때문에 최근에는 스택 대신 사용하게 되었습니다. 하지만 레거시 프로젝트와 같은 곳에서 스택이 사용될 수도 있기 때문에 이번 포스팅에선 스택을 위주로 다뤄보도록 하겠습니다. 데크는 다음 포스팅인 큐에서 좀 더 자세히 다뤄보겠습니다. 

 

출처 : https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95

 

스택의 구조는 지겹도록 보셨겠지만 워낙 유명하니 저도 한번 첨부하고 넘어가겠습니다. 

 

Stack 생성

스택을 선언할 때는 아무런 인자값 없이 기본 생성자로 생성해주면 됩니다. 

 

Stack<Integer> stack = new Stack<>();

 

이렇게 생성된 스택은 디폴트 저장용량이 10으로 설정됩니다. 만약 삽입되는 element의 수가 10을 넘어가면 그 순간 용량을 두배로 늘립니다. 그렇게 두배, 두배 늘려가면서 스택의 용량을 뻥튀기 시키는 것이죠

 

하지만 저장 공간이 두배 늘어나서 20이 되었더라도 값이 제거됐을 때 다시 10으로 돌아가지는 않습니다. 

 

 

Stack의 동기화

스택은 Vector의 직계자손이기 때문에 Vector의 특성을 그대로 가지고 있습니다. Vector는 동기화가 되어있는 구현체로 유명하죠. 따라서 스택도 Vector와 마찬가지로 동기화가 되어있습니다. 

 

하지만 동기화가 항상 필요한것은 아닐테지요. 만약 필요하다면 위에서 언급했듯이 데크를 사용하면 됩니다. 

 

 

Stack의 메서드

스택의 대표적인 메서드는 push() 와 pop()이 있죠 push는 말 그대로 배열에 밀어넣는 것이고 pop은 가장 위에있는 값을 하나 꺼내는 것입니다. 

 

이외에도 해당 값을 찾아주는 search(), 해당 값의 인덱스 위치를 알려주는 indexOf(), 제일 위에서 가장 가까이 있는 값의 인덱스를 알려주는 lastIndexOf(), 제일 위의 값을 꺼내지않고 반환만 해주는 peek() 등이 있습니다. 

 

 

Stack과 반복자

스택은 Iterator를 지원합니다. 따라서 enhanced for문에서 사용할 수도 있습니다. 또한 Iterator에서 지원하는 메서드인 hasNext() 또한 사용할 수 있습니다. 

 

@Test
public void whenAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual() {
    Stack<Integer> intStack = new Stack<>();
    List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
    intStack.addAll(intList);
    
    ListIterator<Integer> it = intStack.listIterator();
    
    Stack<Integer> result = new Stack<>();
    while(it.hasNext()) {
        result.push(it.next());
    }

    assertThat(result, equalTo(intStack));
}

 

 

Stack과 Stream API

스택은 컬렉션입니다. 그리고 이것은 자바 8에서 지원하는 Stream API를 사용할 수 있다는 것인데요. Stream API를 이용해서 다른 컬렉션과 같이 map, flatmap, filter 등을 사용할 수 있습니다. 

 

@Test
public void whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded() {
    Stack<Integer> intStack = new Stack<>();
    List<Integer> inputIntList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 10);
    intStack.addAll(inputIntList);

    List<Integer> filtered = intStack
      .stream()
      .filter(element -> element <= 3)
      .collect(Collectors.toList());

    assertEquals(3, filtered.size());
}

 

자 여기까지 스택에 대해서 알아봤습니다. 가장 기본이 되는 자료구조이기도 하고 개념도 쉬워서 슥슥 보면서 이해했네요. 다음 포스팅은 스택의 오랜 친구인 큐에 대해서 알아보도록 하겠습니다. 

 

긴 글 읽어주셔서 감사합니다. 오늘도 즐거운 하루 보내세요!

 

 

출처

https://www.baeldung.com/java-stack

=> 스택 공식 문서