[JAVA 기초] 스택(Stack), 큐(Queue), 트리(Tree)

Explain

스택 (Stack)

: 하노이탑에 개체를 쌓듯 데이터가 LIFO(Last-In First-Out) 구조로 쌓이는 자료구조

<특징>
- 배열이나 연결리스트 둘다 구현가능
- 중간에서 데이터의 수정이 일어나지 않음
- 맨 위의 위치를 top, 맨 아래의 위치를 bottom 이라 칭함
- LIFO (후입선출) 구조로 가장 나중에 넣은것이 가장 먼저 나오는 자료구조
- push() = 데이터 삽입, pop() = 데이터 빼기 처럼 사용가능
- 실무 사용 예로 게임개발에서 두 수 무르기, 왔던 곳을 되돌아가기 등의 기능을 구현할때 사용
- 자바 JDK에서는 Stack 클래스로 구현하거나 ArrayList로 구현이 가능
- Peek() : 일종의 get()으로 스택의 맨 위에 있는 원소를 반환 (=실제로 꺼내진 않고 그 값이 무엇인지 확인)

 

---

큐 (Queue)

: 가로형태의 원통형 구조라고 가정할 수 있고, 맨 좌측 front, 맨 우측 rear(꼬리) 의 자료구조
: 데이터가 FIFO(First-In First-Out) = 가장 먼저 들어간 것이 가장 먼저 나오는 구조

<특징>
- FIFO(선입선출)구조로 데이터가 가장 먼저 들어간 것이 가장 먼저 나오는 구조
- 한 쪽으로만 데이터가 추가되는 스택과 달리 큐는 앞 뒤 2개가 존재
- add() = 데이터가 맨 뒤(rear)로 들어감
- remove(0) = 맨 앞(front)에서 꺼냄 (큐처럼 꺼내는 것)
- remove (size() - 1) = 맨 뒤(rear)에서 꺼내는 것
- 큐는 중간에서 데이터는 꺼내지 못하고 앞이나 뒤에서 데이터 관리

---

트리 (Tree)

: 자료구조의 한 형태로, 자료의 검색 시 사용되는 자료구조이다.

이 중 '이진 검색 트리(Binary Search Tree)' 공부 = BST

<이진검색트리(BST) 특징>
- 가지 치듯이 계층형으로 이루어진 자료구조이며, Parent 노드 밑에 Child 노드 들이 위치하는 방식
- Parent노드는 Root노드라고도 하며, 이 루트노드를 중심으로 좌측은 루트노드보다 작은 수, 우측은 루트노드보다 큰 수여야함
- 데이터의 중복을 허용하지 않음
- 이진검색트리도 균형있는 트리, 불균형한 트리로 나눠지는데, 두 갈래로 나뉘어지는 이진검색트리 특성 상
균형있는 트리의 경우에는 검색 속도가 효율적이고 빠르다는 장점이 있음
>> 불균형한 트리의 경우 한 쪽으로만 검색을 해야하므로 검색 속도에 있어 비효율적이라는 단점이 있음
>> 이 밸런스를 맞춰주기 위한 트리로 AVL, RedBlack 트리가 존재

- 트리를 순회하는 방법은 크게 3가지가 있는데,

in-order 방식 = 중위 순회
: 루트노드가 항상 가운데에 위치함
: 왼쪽 -> 루트노드 -> 오른쪽 검색방식으로 결과적으로 "오름차순"정렬이 됨
: 대칭 순회 라고도 함

pre-order 방식 = 전위 순회
: 루트노드부터 탐색 후 왼쪽 -> 오른쪽으로 검색하는 방식임
: 깊이 우선 순회 라고도 함

post-order 방식이 있음 = 후위 순회
: 왼쪽 -> 오른쪽 탐색 후 루트노드로 검색하는 방식