스택

스택(Stack)

스택은 먼저 들어온 데이터가 나중에 나가는(FILO, 선입후출) 자료 구조입니다.

흔히 박스가 쌓인 형태를 스택(Stack)이라고 비유합니다.

 

스택 자료 구조의 중요성

스택은 가장 기본적인 자료 구조 중 하나입니다.

기계 학습 분야뿐만 아니라 다양한 프로그램을 개발할 때도 필수적으로 사용됩니다.

 

스택 자료의 시간 복잡도

	연산	시간 복잡도	설명
1	삽입(Push)	O(1)	스택에 원소를 삽입하는 연산
2	추출(Pop)	O(1)	스택에서 원소를 추출하는 연산
3	최상위 원소(Top)	O(1)	스택의 최상위 원소(마지막에 들어온 원소)를 확인하는 연산
4	Empty	O(1)	스택이 비어 있는지 확인하는 연산

 

 

연결 리스트로 스택 구현

스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장 할 수 있다.

연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다.

머리(head) : 남아 이쓴 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인트

삽입 : 머리 위치에 데이터를 넣는다

삭제 : 머리 위치에서 데이터를 꺼낸다.