bdfgdfg

우선순위 큐 간단하게 말해서 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다" 이 우선순위의 판단 근거는 프로그래머가 결정할 일이다. 즉 목적에 맞게 우선순위를 결정하면 된다. 따로 우선순위정보를 넣어줄 수 있고, 저장할 데이터를 근거로 우선순위를 판단할 수 있다.(ex 사전순서) 우선순위 큐를 구현하는 방법은 여러가지가 될 수 있지만 순수 배열을 통한 구현을 할 시 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다. 그리고 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야할 수 있다. -> 이 문제점은 연결리스트도 마찬가지. 그렇기에 우선순위 큐를 구현한다고 하면 '힙(heap)'이라는 자료구조를 ..

트리 앞서 배운 자료구조들(리스트,스택,큐,덱등)은 모두 선형 자료구조이다. 이번에 배울 트리는 비선형 자료구조. 트리는 계층적 관계를 표현하는 자료구조이다. 트리와 관련된 용어를 정의해본다. 1. 노드 : node - 트리의 구성요소에 해당하는 A,B,C,D,E,F등 2. 간선 : edge - 노드와 노드를 연결하는 선 3. 루트 노드 : root node - 트리 구조에서 최상위에 존재하는 노드 (위 그림에선 A노드) 4. 단말 노드 : terminal node - 아래로 또 다른 노드가 연결되어 있지 않은 E,F,C,D와 같은 노드. (다른말로 리프(leaf)노드라고도 함) 5. 내부 노드 : internal node - 단말 노드를 제외한 모든 노드로 A, B와 같은 노드. (비단말 노드라고도 불..

큐(Queue) 스택이 가장 나중에 저장된 값을 먼저 뽑아오는 후입선출(LIFO)의 구조였다면 큐는 가장 먼저 저장된 값을 먼저 뽑아오는 선입선출(FIFO)의 구조이다. 큐를 배열기반으로 구현했을때 선입선출의 구조가 되기 위해서는 1. 데이터가 들어갈(enqueue) 인덱스값을 기억할 rear변수. 2. 데이터를 뽑아(dequeue)올 인덱스값을 기억할 front변수. 처음 FR이 0번째 인덱스를 가리킬때 데이터가 들어오면 R이 가리키는 인덱스에 요소를 집어넣고 한칸 오른쪽으로 옮긴다. 그리고 데이터를 뽑아올땐 F가 가리키는 인덱스에 요소를 빼오고 한칸 오른쪽으로 옮긴다. 이것이 배열기반 큐의 구조. 하지만 이렇게 단순히 끝낼수는 없는게 위의 그림과 같이 분명히 배열에 데이터를 저장할 공간이 남아있지만 ..

스택 LIFO(Last In First Out). 후입 선출방식의 자료구조이다. 앞서 재귀함수를 공부할 때도 자기 자신을 호출하면서 빠져나올 땐 역순으로 빠져나오는 스택의 방식. 간단하게 설명하면 쌓여있는 상자를 생각하면 쉽다. 상자를 밑에서부터 위로 하나하나 차곡차곡 쌓고 뺄 때는 위에서부터 아래로 하나하나씩 뺀다. 이것이 스택의 구조 간단하니 바로 코드를 통해 확인한다. #pragma once template class Stack { public: Stack(); ~Stack(); inline T GetTop() const; inline bool Push(const T& item); inline bool Pop(); inline bool Empty() const; private: enum { MAX ..