스택
스택
자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 이며,
‘스택’의 경우, 가장 먼저 ‘삽입(push) 된 데이터가,
제일 마지막에 삭제(Pop) 된다
(선입후출, FILO 등으로도 표현된다)
(‘쌓여있는 책’ 등으로 비유되기도)
스택 자료구조의 시간 복잡도
- 삽입 (Push)
- O(1)
-> 스택의 제일 ‘위’에 놓기만 하면 되므로 - 제거 (Pop)
- O(1)
-> 스택의 제일 ‘위’에서 삭제만 하면 되므로
=> 보통 Pop으로 가장 위의 요소를 반환하며 제거한다 - 검색
- O(N)
-> 제일 위부터 찾을때까지 뒤진다
다만 개념적으로 ‘push,pop’ 만 제거하는 자료구조 이므로,
실제 ‘검색’을 시도하는 경우,
모든 요소를 다 꺼내서(Pop) 확인한 후,
다시 넣어(Push) 준다
(모든 요소를 제거했다가,
다시 집어넣으므로 정확히는 O(2N))
스택 자료구조의 주 용도
일련의 자료의 순서를 뒤집는 경우,
스택은 유용한 자료구조
(ex : reverse)
또한 ‘재귀’를 제거하는 용도로도 유용하다
재귀는 함수를 스택 프레임에 담아두며, 진행되는데
이를 실제 ‘스택’에 중간 결과를 저장함으로서
반복문으로 구현할 수 있게 만든다
댓글남기기