queue
-
Graph BFS with queueC 자료구조/Graph 2020. 7. 8. 19:05
내용 1. 개념 너비 우선 탐색( BFS )은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 너비 우선 탐색을 위해서는 방문한 정점들을 차례로 저장한 후, 꺼낼 수 있는 자료 구조인 큐가 필요하다. 큐는 앞에서 만든 것을 이용할 것이다. 즉, 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우에는 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 된다. 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될 때까지 계속한다. 여기에서도 pVisit배열을 쓴다. 너비 우선 탐색을 그림으로 보자. 아래에 임의의 그래프가 주어졌다고 가정하자. [그림 1] 위의..
-
Queue 만들기C 자료구조/4. 큐( Queue ) 2020. 6. 28. 13:18
1. 개념 Queue는 먼저 들어온 데이터가 먼저 나가는 구조로 되어있다. 이러한 특성을 선입 선출 ( FIFO : First-In First-Out ) 이라고 한다. 큐는 뒤에서 새로운 데이터가 추가되고, 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다. 큐에서 삽입이 일어나는 곳을 Rear 라고 하고 삭제가 일어나는 곳을 Front라고 한다. 그림으로 보자. 2. 구현 메인 함수 3. 실행결과 헤더 파일 및 소스 파일