자료구조 | 스택(Stack)

스택(Stack)이란?

Stack의 사전적인 의미는 쌓다이다. 말 그대로 데이터를 쌓아 올린 형태의 자료구조이다.

예를 들면, 주방에 같은 모양의 접시들을 아래부터 차곡차곡 쌓아 두고, 가장 위에 있는 접시부터 꺼내어 사용하는 것과 같다.

가장 마지막에 들어간 데이터를 가장 먼저 빼내는 형태로 후입선출(LIFO : Last In First Out)의 특징을 가지고있다.

 

스택의 특징

맨 위에 있는 가장 마지막에 들어온 데이터에만 접근이 가능하다.

따라서 맨 위에서만 데이터를 삽입(push)할 수 있고, 맨 위의 데이터만 삭제(pop)할 수 있다.

이때, 맨 위의 원소를 top이라고 하고 가장 아래에 있는 시작부분을 bottom이라고 한다.

 

스택의 활용

백스페이스 : 최근 입력 데이터 지우기.

ctrl+z : 최근 실행한 작업 취소

뒤로가기 : 마지막으로 열었던 페이지로 이동.

 

시간복잡도

Insert(push), Delete(pop): O(1)

스택은 항상 가장 맨 위의 데이터만을 삽입하고 삭제하기때문에 O(1)이다.

Search: O(n)

데이터를 찾을때의 시간복잡도는 해당 데이터를 찾을때까지 수행하기 때문에 O(n)이다.