DataStructure(54)
-
비선형 데이터구조, 트리(Tree) #1 이진 트리의 소개
1. 트리(Tree)란 무엇인가? 트리(Tree)란 배열과 연결리스트, 스택, 큐와 같은 선형 데이터 구조와는 다르게 계층적인 구조를 가지는 데이터 구조입니다. 트리 노드란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조입니다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나분인 그래프를 트리라고 부릅니다. 2. 이진 트리(Tree)란 무엇인가? 이진 트리(Binary Tree)란 각각의 노드가 최대 2개의 자식 노드를 가지는 트리 자료 구조입니다. 자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 합니다. 3. 이진 트리(Binary Tree)의 용어 루트 노드(Root Node) : 트리의 가장 꼭대기에 존재하는 노드 부모 노드(Parent Node) : 자식 노..
2021.09.22 -
선형데이터구조, 연결리스트(LinkedList) #4 LinkedList Collection Framework
1. LinkedList Collection Framwork LinkedList는 java.util 패키지에서 Collection Framework 중 하나이다. LinkedList 클래스는 연결리스트(LinkedList) 데이터 구조를 구현한 클래스입니다. 대표적인 특징으로는 선형 데이터 구조이지만 메모리상의 연속적인 위치에 저장되지 않고 노드를 구성합니다. 노드는 값을 담을 수 있는 데이터 변수와 다음 노드를 가리킬 수 있는 주소 노드로 구성됩니다. LinkedList 데이터 구조는 삽입과 삭제가 쉽고 크기가 동적이기 때문에 이부분에서는 배열보다 성능이 좋습니다. 하지만 단점으로는 배열은 직접적으로 특정 위치에 접근이 가능한 반면 LinkedList는 head부터 탐색할 수 밖에 없습니다. 즉, 탐색..
2021.09.17 -
선형데이터구조, 큐(Queue) #2 Queue Collection Framework (JAVA)
1. Queue Collection Framework Queue 인터페이스는 java.util 패키지안에 존재하고 Collection 인터페이스를 상속받습니다. Queue 인터페이스는 리스트의 시작으로부터 요소들을 삭제하고 리스트의 끝에 요소를 추가하는 객체들의 순서화된 리스트입니다. Queue 인터페이스는 FIFO(First-In-First-Out) 원칙을 따릅니다. Queue 인터페이스는 객체를 생성시 PriorityQueue 클래스나 LinkedList와 같은 콘크리트 클래스(Concrete Class)로 생성이 필요합니다. Declaration public interface Queue extends Collection Queue 객체 생성 Queue는 인터페이스이기 때문에 Queue 타입으로 객체..
2021.09.16 -
선형데이터구조, 큐(Queue) #1 큐 소개 및 배열기반 구현
1. 큐(Queue) 데이터구조란 무엇인가? 스택(Stack) 데이터 구조와 비슷하게 큐(Queue) 구조는 FIFO(First In First Out) 순서로 데이터를 저장하는 선형 데이터 구조입니다. 큐의 좋은 예시로는 계산대에서 물건을 계산하기 위해서 한 줄로 줄을 서는 손님들이 좋은 예시입니다. 스택과 큐의 차이점은 제거하는 방식이 차이가 존재합니다. 스택 구조같은 경우 가장 최근에 추가된 데이터가 제거되는 방식에 비해 큐 구조는 가장 빨리 추가된 데이터가 제거되는 방식입니다. 이것은 마치 먼저 음식을 주문한 손님이 먼저 음식을 받아가는 것과 마찬가지입니다. 2. 큐의 연산 Enqueue : 큐에 데이터를 추가합니다. 만약 큐가 가득차있다면 추가되지 않습니다. Dequeue : 큐에 데이터를 제거..
2021.09.16 -
선형데이터구조, 스택(Stack) #2 Stack Collection Framework (JAVA)
개요 자바의 컬렉션 프레임워크(Collection Framework)는 데이터 구조인 스택을 구현한 Stack 클래스를 제공합니다. 이 Stack 클래스는 LIFO(Last-In-First-Out) 원칙에 기반하여 수행됩니다. 기본적인 push, pop 연산뿐만 아니라 empty, search, peek 연산도 제공합니다. Stack 클래스는 Vector 클래스로부터 상속되었습니다. 아래의 그림은 Stack 클래스의 상속관계를 알려줍니다. 위의 그림을 보면 Stack 클래스는 Vector 클래스로부터 상속(Extend)받은 것을 알 수 있으면 부모 클래스인 Vector 클래스는 List 인터페이스로부터 구현됨을 알 수 있습니다. Declaration public class Stack extends Vec..
2021.09.16 -
선형데이터구조, 스택(Stack) #1 스택 구조 소개 및 구현
1. 스택(Stack) 소개 스택 자료구조는 스택의 연산들이 수행되어 특정한 순서를 따르는 선형 데이터 구조입니다. 특정한 순서란 LIFO(Last In First Out) 또는 FILO(First In Last Out)라고 부릅니다. LIFO(Last In First Out) : 마지막에 들어온 데이터가 먼저 나가는 순서 FILO(First In Last Out) : 먼저 들어온 데이터가 나중에 나가는 순서 2. 스택의 연산(operations) Push : 스택 자료구조에 데이터를 추가하는 연산, 만약 스택이 가득차있다면 데이터를 추가할 수 없습니다. Pop : 스택 자료구조에 데이터를 제거하는 연산, 제거되는 순서는 제일 늦게 추가된 데이터가 스택으로부터 제거됩니다. 만약 스택이 비어있다면 데이터를..
2021.09.15