JAVA Queue Stack Hash

- Queue의 개념

데이터 큐는 말 그대로 줄서기 자료구조다. 먼저 줄을 선 데이터가 먼저 처리된다.

이것을 선입 선출 (FIFO First in First Out) 이라 부른다.

첫번째와 마지막 위치를 알아야한다.

 

Enqueue

데이터를 큐에 넣는 동작

 

Dequeue

큐에서 데이터를 거내는 동작

 

원형 Queue

원형 큐는 선형큐의 반복적 데이터 이동의 단점을 보완한 알고리즘이다.

그림과 같이 front와 rear가 큐 사이즈 내에서 회전한다.

Front = (Front + 1) % SIZE;
Rear = (Rear + 1) % SIZE;

숙제 = 원형큐를 만들어라

 

너비우선탐색 (BFS)

물결이 퍼지듯 가까운 경로 후보부터 탐색하는 방법

깊이우선탐색 (DFS)

숙제 = 예제를 만들어라

 

숙제 = 중위, 후위 예제 만들어라

---

Stack

push = 스택에 자료를 넣는 동작

pop = 스택에서 자료를 꺼내는 동작

---

재귀 호출의 개념(복잡한 알고리즘에서 효과적이다.)

재귀호출은 어떤 함수가 자기 자신을 반복적으로 호출하는 것을 말한다.

팩토리얼은 자기 자신보다 같거나 작은 모든 수를 곱한 값이다.

 

재귀호출의 특징

장점 : 반복문을 이용한 알고리즘에 비해 프로그램이 명확하고 간결하다.

단점 : 함수 호출을 반복하므로 시간이 더 걸리며 스택 overflow가 발생할 수 있다.

---

이진 검색의 개념

이진 검색은 정렬된 배열 또는 리스트에서 특정 값을 빠르게 찾는 알고리즘이다.

중간값부터 비교하여 찾고자 하는 값과의 크고 작음에 따라 범위를 좁혀간다.

 

장점 : 대량의 자료를 log 성능으로 검색이 가능하다.

단점 : 자료를 항상 정렬된 상태로 유지해야한다.

---

Hash의 개념

해시는 불특정 형태의 아이템을 특정 형태로 변경하는 알고리즘이다.

 

Separate Chaining

해시 함수의 결과의 충돌이 발생했을 경우 충돌한 아이템을 별도 리스트로 구성하여 해결한다.

검색 효율이 좋으나 구현이 복잡하고 메모리 효율이 떨어진다.

---

- 전위 표기법과 후위 표기법 계산방법