1. 정의
- LIFO(Last In First Out : 마지막에 입력된 자료가 제일 먼저 내보내짐) 형태의 자료구조
2. 특징
- 자료입력(push), 출력(pop)
- 자료크기(size), 현재위치(ptr)
3. 시간복잡도
자료구조 비교
Data Structures Average Case Worst Case SearchInsert DeleteSearch InsertDelete
Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
4. Algorithm 깃헙 (계속 업데이트 예정)
github.com/h232ch/DataStructureAndAlgorithm
댓글