스택(Stack)


스택(Stack)

데이터 구조의 한 종류, 물건을 세로로 쌓는다고 생각하면 이해하기 쉬운 구조이다.
세로로 쌓인 물건들 중에 하나를 꺼내려면 위에서부터 차례대로 꺼내야한다.

스택에 데이터를 추가할 때는 가장 위에 추가된다.
스택에 데이터를 추가하는 작업을 푸시(push)라고 한다.


push

push

스택에서 데이터를 꺼내는 경우 가장 위, 즉 가장 최근에 추가된 데이터부터 차례대로 꺼낸다.
스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다.


pop

pop

이처럼 나중에 넣은 것을 먼저 꺼내는 구조를 "Last In First Out"이라고 하며, 앞글자만 따서 "LIFO"라고 한다.

시간복잡도

OperationAverageWorst
AccessO(n)O(n)
SearchO(n)O(n)
InsertO(1)O(1)
DeleteO(1)O(1)

ref