큐 (Queue) / 스택(Stack) / 트리(Tree)
2023. 4. 4. 15:50ㆍ카테고리 없음
큐는 선입선출(FIFO : First In First Out)
Enqueue] 데이터가 뒤(Rear)에서 들어오고,
Dequeue] 데이터가 앞(Front)으로 나간다.
데이터가 들어오고 나가는 것은 한 번에 동작 = O(1)
데이터를 조회하는 것은 전체를 확인해야함 = O(n)
=> 데이터의 입력과 출력이 잦을 때, 가장 오래된 데이터를 찾을 때 유리함!
스택은 후입선출(LIFO : Last In First Out)
Push] 데이터가 위에서 들어오고
Pop] 데이터가 위에서 나간다.
데이터가 들어오고 나가는 것은 한 번에 동작 = O(1)
데이터를 조회하는 것은 전체를 확인해야함 = O(n)
=> 데이터의 입력과 출력이 잦을 때, 가장 최근 데이터를 찾을 때 유리함!
트리는 데이터 사이의 계층 관계를 노드로 나타낸 자료구조
- 노드는 부모와 자식, 그리고 형제(sibling)의 관계를 가지고 있음.
- 트리는 형태(ex. 한 부모 당 자식의 수)가 다양할 수 있고
, 탐색방법(BFS, DFS)이 다양할 수 있음.
- 따라서 트리의 탐색, 생성, 삭제 등의 과정도 Big-O가 다 달라지게 됨.
=> 문제를 읽고 적절한 구현 방법과 적적한 알고리즘 방법을 찾는 것이 매우 중요함!