CS/DataStructure4 [자료구조] 트리 트리란? 트리는 1개 이상의 노드를 갖는 노드의 집합으로 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용하는 비선형 자료구조입니다. 트리는 디렉터리 구조등 계층적인 구조를 갖는 데이터일때 사용됩니다. 트리는 다음과 같은 조건을 만족합니다. 트리에 최상위에 루트노트라는 노드가 존재합니다. 한 노드는 하나의 노드만 가르키고 있습니다. (1 : n 관계) 트리는 사이클을 그리지 않으며, 계층적인 구조를 가집니다. 다음과 같은 구조는 트리가 아닙니다. 위의 경우는 C 노드를 A와 F가 가르키고 있기 때문에 트리가 아닙니다. 위의 경우에는 노드들이 사이클을 그리고 있기 때문에 트리가 아닙니다. 트리 용어 트리는 다음과 같은 용어를 사용합니다. 루트 노드(root node) : 부모가 없는 노드를 의.. 2021. 12. 13. [자료구조] Deque Deque? Deque(덱)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 입니다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있으며, 큐와 스택을 합친 형태로 생각할 수 있습니다. deque는 양방향으로 삽입삭제를 할 수 있기 때문에 단방향으로만 삽입 삭제가 이루어지는 queue와 stack에 비해 삽입 삭제를 좀 더 간편하게 할 수 있습니다. 삽입과 삭제시 O(1)로 굉장히 빠르지만 deque 중간에 있는 데이터에는 접근하기 어렵다는 단점이 있습니다. Deque의 구현 Deque는 최소한 다음과 기능을 수행할 수 있도록 구현했습니다. create : deque를 생성 insertFront : deque의 맨앞에 원소를 추가 deleteFront : deque의 맨앞의 원소를 .. 2021. 12. 11. [자료구조] Queue Queue란? Queue는 선형구조를 가진 자료구조로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말합니다. 나중에 집어 넣은 데이터가 먼저 나오는 stack과는 반대되는 개념입니다. 보통 프린터의 출력 처리나, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 사용됩니다. Queue의 구현 Queue의 구현해야할 기능은 다음과 같습니다. create : Queue를 생성하는 함수입니다. front로 가장 앞의 인덱스를 가르키고 rear로 가장 끝의 인덱스를 가르킵니다. enQueue : 큐에 Element(요소)를 추가합니다. deQueue : 큐에서 맨앞의 요소를 빼냅니다. peek : 큐에서 맨앞의 요소를 가져.. 2021. 12. 11. [자료구조] Stack 스택이란? 스택은 선형구조를 가진 자료구조로 한 쪽 끝에서만 자료를 넣거나 빼는 후입 선출(Last-in First-out)의 형태로 동작합니다. 스택은 기본적으로 다음과 같은 연산을 합니다. push push 연산을 하면 스택에 지정한 데이터를 맨 끝에 넣습니다. pop pop 연산을 하면 스택에 맨 끝에 있는 데이터를 가져오고 스택에서 제거합니다. peek peek 연산을 하면 스택에 맨 끝에 있는 데이터를 가져옵니다. 스택의 활용 스택은 이전 상태로 되돌리는 경우에서 많이 사용됩니다. 예를 들어, 터미널에서 이전에 사용했던 명령들을 확인하고 사용할 수 있는 히스토리 기능이나 브라우저에서 이전 페이지로 되돌아가고 싶을 때 사용됩니다. 스택의 구현 (C) 스택은 배열 또는 링크드 리스트로 구현이 가능합.. 2021. 12. 1. 이전 1 다음
