[자료구조/알고리즘] - 스택

자료구조를 배우게 되면 가장 많이 보게 되는 자료형이 아닐까 생각이 듭니다. 운영체제에서도 나오고 다른 CS 지식을 배우는 과정에서도 자주 나오는 자료형이라고 생각이 됩니다.

다음 글로 Queue에 대한 부분도 작성하겠지만 스택의 경우에는 Last-In-First-Out, LIFO(후입선출)에 해당 합니다. 1학년 때 자료구조를 들으면서 들었던 좋은 예시로는 테니스공이나 배드민턴 공을 넣는 통이 생각이 납니다. 

흔히 셔틀콕을 담기 위해 사용하는 통

위의 그림과 같이 제일 마지막에 넣은 셔틀콕을 우리가 셔틀콕을 사용하기 위해서 제일 먼저 꺼내게 됩니다. 

파이썬에서는 스택 자료형을 별도로 제공하지는 않지만 리스트를 통해서 거의 대부분의 연산을 사용할 수 있습니다. 예를 들어서 pop()과 같은 기능을 제공받아서 일일히 스택에서 필요한 기능들을 구성하지 않아도 됩니다. 

스택 추상 자료형 + 메모리 구현

위의 그림에서 스택의 경우에는 왼쪽 그림 처럼 데이터가 접시 쌓듯이 쌓인다면, 실제로 연결리스트로 스택을 구현하게 되면 이와 스택에 들어온 순서와는 관계 없이 포인터를 통해서 가르키게 됩니다. 

[참고자료]

참고 서적 : 파이썬 알고리즘 인터뷰

파이썬 알고리즘 인터뷰