[Swift] 자료구조 - stack
자료구조는 5년전..공부할 때 다뤄본 적이 있지만
새로운 언어를 배울 때
자료구조를 c#의 형식이 아닌 swift로 작성해보고 싶고 구현해보고 싶어서 남겨본다
stack
기본적으로 게임에서 많이 사용했다
네임스페이스를 using System.Collection으로 사용하여
stack클래스를 만들어 push pop형식으로 메서드를 호출하여 object 형식으로
데이터를 저장(push)하거나
데이터를 꺼내는 형식(pop)으로
사용이 가능하도록 짰던 기억이있다
우선 stack은 한국어로 번역해보면
'쌓는다' 라는 뜻이라고 알 수 있다
선형 자료 구조 배열과 같지만 특정 기능에 특화된 배열이라고 할 수 있다
LIFO : stack 활용은 어떤걸 쌓고 맨 위의 것을 빼는 구조인데
Last In First Out 나중에 들어간 object가 제일 처음으로 나온다라는 의미로 알고 있으면 된다고 생각해요
Pixabay로부터 입수된 Mohamed Hassan님의 이미지 입니다.
예를 들어서 여러개의 택배박스를 들고 있을 때 제일 아레 부분을 건들지 못하기 때문에
윗부분의 택배 박스를 먼저 꺼내야하는 것 처럼
사용한다고 생각하면 이해가 빠르다고 생각이 들어요!
그리고 제일 중요한 stack의 키워드라고하면
LIFO, push, pop, peek 이 네개만 알면 마스터 한거라고 할 수 있어요
다시 말하지만 stack은 오브젝트를 추가할 때마다 저 택배상자처럼
제일 마지막에 추가되고 오브젝트가 사라질 때는
제일 마지막 오브젝트가 사라진다고 했던것 처럼
LIFO는
Last In First Out 나중에 들어간 오브젝트가 제일 먼저 나온다
push는 오브젝트를 추가하는것이고 pop은 마지막에 얹어진 오브젝트를 삭제하는것이고
peek은 top이라고도 말하는데 맨 마지막의 오브젝트를 가지고 옵니다
이걸 swift 코드로 만든다면
아래로 만들 수 있다
하지만 코드를 봐도 이해가 안되는 경우 그림으로 알려드릴게요!
push의 경우 새로운 데이터를 하나 추가한다고 생각하면됩니다
그리고 peek의 경우 데이터를 삭제하지않고 마지막 데이터를 가지고 옵니다!
pop의 경우 마지막 인덱스를 삭제해버린답니다
마치 배열에서 사용하는 removeLast와 동일한 기능이라고 생각이 들죠?
시간 복잡도를 생각하면
늘 마지막에 추가되고 삭제되기 때문에 시간 복잡도는 O(1)
그래서 오버헤드가 발생하지않는답니다 :)
배열을 그냥 사용해도 되겠는데 굳이 스택을 사용하는 이유는 뭘까?
라고 GPT에게 물어봤습니다
아주 쉬운 자료구조인 stack에 대해서 끝!
다음엔 Queue에 대해서 정리해볼까 싶습니다 :)