Stack
스택의 삭제(pop) 연산의 시간복잡도는 맨 위의 원소를 제거하는 것 이기 때문에 O(1) 입니다.
검색의 경우 full scan을 해서 특정 데이터를 찾는 것 이므로 O(n)의 시간복잡도를 가집니다.
Queue
큐의 삭제(Dequeue) 연산의 시간복잡도는 가장 먼저 들어온 원소를 제거하는 것 이므로 O(1) 입니다.
검색의 경우 Stack과 마찬가지도 데이터를 찾을 때 까지 full scan을 해야하므로 O(n)의 시간복잡도를 가집니다.
정리
Stack 시간복잡도
- 삭제: O(1)
- 검색: O(n)
Queue 시간복잡도
- 삭제: O(1)
- 검색: O(n)
