스택 (Stack)

출처 : 파이썬 알고리즘 인터뷰

스택(Stack)은 후입선출(Last-In-First-Out, LIFO) 방식으로 자료를 저장하는 선형 자료구조 입니다. 쉽게 말하면, 데이터를 쌓는 상자라고 생각하면 됩니다. 맨 위에 데이터가 추가되고, 가장 위에 있는 데이터부터 차례로 제거됩니다.

 

스택은 보통 push와 pop 두 가지 기본 연산을 제공합니다. push 연산은 스택의 맨 위에 데이터를 추가하는 것이며,

pop연산은 스택의 맨 위에 있는 데이터를 제거하고 반환하는 것 입니다. 그 외에도 스택에서는 top 연산이 지원되며, 이는 스택의 맨 위에 있는 데이터를 반환하지만, 데이터를 제거하지는 않습니다.

 

스택은 컴퓨터 과학에서 광범위하게 사용되며, 여러 가지 알고리즘에서 활용됩니다. 예를들어, 함수 호출 시 함수 내부에서 사용하는 지역 변수나 함수 호출 스택 등 스택을 이용하여 구현할 수 있습니다. 또한, 스택을 이용하여 중위 표기법으로 작성된 수식을 후위 표기법으로 변환하거나 후위 표기법으로 작성된 수식의 계산을 수행하는 등의 다양한 용도로 활용 됩니다.

 

스택은 배열 또는 연결 리스트로 구현할 수 있으며, 구현 방법에 따라 성능이나 기능이 달라질 수 있습니다. 배열 기반 스택은 구현이 간단하고, 인덱스를 이용하여 데이터에 바로 접근할 수 있기 때문에 접근 시간이 빠릅니다. 스택이 가득 차면 새로운 데이터를 추가할 수 없는데, 이를 해결하기 위해선 배열의 크기를 동적으로 늘려야 합니다.

 

반면에 연결 리스트 기반 스택은 크기 제한이 없으며, 데이터 추가와 삭제가 빠르지만, 데이터 접근 시 포인터를 이용하여 연결 리스트를 따라 이동해야 하기 때문에 인덱스를 이용한 접근보다 느릴 수 있습니다.