낢이 사는 이야기

우선 순위 큐 우선 순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아닌 우선 순위에 따라서 순서가 결정된다. ADT 객체 n개의 element 형의 우선 순위를 가진 요소들의 모임 연산 push(data) : 우선 순위 큐에 데이터를 추가한다. (시간 복잡도 : O(log2n)) pop() : 우선 순위 큐에서 가장 우선순위가 높은 요소를 삭제한다. (시간 복잡도 : O(log2n)) empty() : 우선 순위 큐가 비었는지 확인한다. size() : 우선 순위 큐의 크기를 구한다. top() : 우선 순위 큐에서 가장 우선순위가 높은 요소를 반환한다. #include #include typedef int element; using namespace std; class priorityQueue{ p..

이진트리 모든 노드가 최대 2개의 서브 트리를 가질 수 있는 트리 높이가 h일 때 최소 h개의 노드, 최대 2^h-1개의 노드를 가짐 노드의 개수가 n개일 때 간선의 개수는 n-1 이진트리 종류 포화 이진트리 : 트리의 모든 레벨에 노드가 모두 차있는 이진트리 완전 이진트리 : 높이가 h일 때 레벨 1부터 h-1까지는 노드가 모두 채워져 있고 마지막 레벨 h에서는 왼쪽부터 오른쪽의 순서로 노드가 채워져 있는 이진트리 연결리스트를 이용한 이진트리 #include using namespace std; typedef int element; typedef struct Node{ element data; Node* left; Node* right; }Node; class BinaryTree{ public: Bin..

Double-Ended Queue 큐의 front와 rear에서 모두 삽입 삭제가 가능한 큐 연산 create : 덱을 생성한다 init : 덱을 초기화한다. is_empty(dq) : 덱이 비어있는지 검사한다. is_full(dq) : 덱이 가득찼는지 검사한다. add_front(dq, e) : 덱의 앞에 요소를 추가한다. add_rear(dq, e) : 덱의 뒤에 요소를 추가한다. delete_front(dq) : 덱의 앞에 요소를 반환하고 삭제한다. delete_rear(dq) : 덱의 뒤에 요소를 반환하고삭제한다. get_front(dq) : 덱의 앞에 요소를 반환한다. get_rear(dq) : 덱의 뒤에 요소를 반환한다. 이중연결리스트를 이용한 구현 #include typedef int ele..

선입선출(FIFO : First-In First-Out) 먼저 들어온 데이터가 먼저 나가는 것. 맛집 웨이팅처럼! 연산 create : 큐를 생성한다 init : 큐를 초기화한다. is_empty(q) : 큐가 비어있는지 검사한다. is_full(q) : 큐가 가득찼는지 검사한다. enqueue(q, e) : 큐의 뒤에 요소를 추가한다. dequeue(q) : 큐의 앞에 있는 요소를 반환한 다음 삭제한다. peek(q) : 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다. 배열을 이용한 선형큐 front : 첫번째 요소 하나 앞의 인덱스 rear : 마지막 요소의 인덱스 #include #define MAX_QUEUE_SIZE 3 typedef int element; typedef struct { ele..

후입선출(LIFO : Last-In First-Out) 가장 최근에 들어온 데이터가 가장 먼저 나가는 것. 각티슈에서 가장 위에 있는 것부터 뽑아 쓰는 것처럼! 입력과 출력이 역순으로 필요한 경우 사용한다. (ex. undo, 함수 호출 스택) 연산 init(stack) : 스택을 초기화한다. create() : 스택을 생성한다. push(stack, data) : 데이터를 스택 가장 위에 삽입한다. pop(stack) : 스택 가장 위의 데이터를 삭제한다. is_empty(stack) : 스택이 비어있는지 검사한다. is_full(stack) : 스택이 가득 찼는지 검사한다. peek(stack) : 스택의 맨 위에 있는 요소를 삭제하지 않고 반환한다. 배열을 이용한 스택 #include #define..