3일차 정리(스택 자료구조, 큐 자료구조, 데크 자료구조, 트리 자료구조, 이진 트리)

1. 스택 자료구조

- 데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조

- LIFO(Last In First Out)형

- 스택에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'

- 자바로 구현한 스택 자료구조

-> 결과 :

- 파이썬으로 구현한 스택 자려구조

-> 결과 : 

- 컴퓨터가 사용하는 수식(후위 표기법)으로 변환과 연산

(2) (( 괄호 무시하고 A 출력

(3) * 스택 PUSH

(4) B 출력

(5) * 스택 POP

(6) - 스택 PUSH, C 출력

(7) / 스택 PUSH, D 출력

(8) )) 괄호 무시하고  / , - 순으로 POP

(2) A, B 순서대로 스택 PUSH

(3) A, B POP해서 * 계산후 결과 X를 스택 PUSH

(4) C, D 순서대로 스택 PUSH

(5) C, D POP해서 / 계산후 결과 Y를 스택 PUSH

(6) X, Y POP해서 - 계산후 결과 Z를 스택 PUSH

(7) 최종 결과 Z를 출력

2. 큐(Queue) 자료구조

- 데이터가 입력되면 입력되는 순서대로 쌓고, 먼저 들어온 것부터 먼저 사용하는 자료구조

- FIFO(Fist In First Out)형

- 큐의 구현은 배열을 이용하거나(순환 큐), 또는 연결 리스트를 이용(링크드 큐)

- 자바로 구현한 큐 자료구조

-> 결과 :

- 파이썬으로 구현한 큐 자료구조

-> 결과 : 

3. 데크(Deque) 자료구조

- 데크는 리스트의 양쪽 끝에서 삽입과 삭제가 모두 이루어지는 자료구조이며, 스택과 큐를 혼합한 구조로 하나의 배열을  선언한 후, 2개의 포인터로 양쪽 끝을 가리키고, 이것을 이용하여 양쪽에서 삽입, 삭제 연산을 수행

- 데크 자료구조의 종류)

 가. 입력제한데크(스크롤) : 삽입이 한쪽에서만 일어나는 데크

 나. 출력제한데크(셀프) : 삭제가 한쪽에서만 일어나는 데크

4. 트리(Tree) 자료구조

- 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 것을 트리(Tree) 자료구조라고 한다.

- 트리 자료구조는 노드 중에서 단 하나의 루트 노드(Root Node), 루트 노드에서 하위 노드(Sub Node)들이 연결된 비선행 계층 구조

- 다음 데이터를 가리키는 것이 2개인 단방향 트리 구조를 이진 트리 구조라고 부른다.

- 트리 자료구조의 구현은 배열이나 연결 리스트를 사용하며, 운영체제의 파일 시스템에서 사용

6. 이진 트리(Binary Tree)

- 트리 자료구조 중에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조

- 왼쪽 서브 트리의 값은 루트의 값보다 작고, 오른쪽 서브 트리의 값은 루트보다 큰 값을 가지도록 구성

- 주로 빠른 검색이 필요한 곳에 사용

- 이진 트리 모양에 따른 분류)

 가. 포화 이진 트리(Full Binary Tree) : 레벨의 노드가 꽉 차 있는 트리

 나. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨 전까지는 노드가 꽉차 있고, 마지막 레벨의 왼쪽에서 오른쪽으로 노드가 채워져 있는 트리(즉, 마지막 레벨이 다 채워지지 않아도 됨)

 다. 편향 이진 트리(Skewed Binary Tree) : 왼쪽 혹은 오른쪽 서브 트리만을 가지는 트리

- 자바로 구현한 이진 트리 프로그램

-> 결과 : 

---

지금보니 자료구조 공부하기에 부적합한 책인것같습니다.

이유로써는 자료구조에대해 무엇이다 라고 설명은 되어있으나 소스코드에서의 상세한 설명이 부족해보입니다.

다른책으로 다시 공부해보도록 하겠습니다.