[자료구조] Stack에 대해 알아보고 구현해보기 (Swift)

Stack이란?

Stack 자료구조는 후입선출(Last In First Out)LIFO 의 특성을 갖는 자료구조 입니다.
즉, 나중에 들어온 것이 가장 먼저 나가는 구조입니다.

예를 들어 1, 2, 3이란 원소가 Stack에 들어왔다면

스택에 요소들이 이러한 식으로 들어와져 있을 것입니다.

pop을 하게 된다면?

element 3이 삭제될 것입니다.

시간 복잡도

• 삽입 : $O(1)$
• 삭제 : $O(1)$
• 검색 : $O(n)$

스택의 활용

• 실행 취소 (undo)
• 웹 브라우저에서의 뒤로가기
• 재귀함수

구현

스택을 어떻게 구현할 수 있을까요?

연결리스트를 사용하여 구현할 수도 있지만 Array를 사용해서 구현해보겠습니다.

삽입 연산은 Swift의 Array의 append 메서드를 사용할 수 있습니다.
단순히 Array의 Element를 마지막에 삽입하는 연산이고, append 메서드는 $O(1)$ 이기 때문에 스택 자료구조의 삽입 연산과 동일합니다.

삭제 연산은 removeLast or popLast 메서드를 사용해 구현해 주면 되겠네요.
가장 나중에 들어온 element를 삭제시켜줘야 하기 때문입니다.
두 메서드 모두 $O(1)$이기 때문에 스택 자료구조의 삭제 연산과 동일합니다.

제네릭을 사용해서 구현해주면 자료형에 의존하지 않고 범용적으로 사용할 수 있기 때문에 제네릭을 사용했습니다.

top, isEmpty, count, push, pop 정도의 메서드만 구현해보았습니다.

후기

스택 자료구조를 구현해보았는데, Array를 사용해 쉽게 구현할 수 있었습니다.