개념/자료구조4 [Java] 큐(Queue) 자료구조에서 큐는 FIFO(First In First Out) 구조의 자료이다. 처음 들어간 데이터를 출력한다. 구현방식에 따라 다양한 종류가 존재한다. 자바의 util 에는 기본적으로 큐를 제공하기 때문에 해당 부분을 이용하면 된다. ArrayDeque 를 이용하면 되는데 주의할 점이 하나 있다. * 데이터를 입력하는 방법에 offer(), push() 두가지 메소드가 있는데 push는 데이터를 앞으로 입력하고, offer는 데이터를 뒤로 입력한다. push 만을 이용하여 데이터를 입력하면 스택처럼 동작하고, offer 만을 이용하여 데이터를 입력하면 큐로 동작한다. 따라서 데이터를 입력할 때 메소드를 잘 선택하여 입력해야 한다. import java.util.ArrayDeque; public clas.. 2016. 6. 10. [JAVA] 스택(Stack) 스택은 자료구조에서 LIFO(Last In First Out) 구조를 가지는 자료구조이다. 구현하는 방식에 따라 종류가 많이 있다. 자바의 util 에 기본적으로 스택을 제공해주기 때문에 따로 구현하지 않고 이 클래스를 사용하면 된다. import java.util.Stack; public class StackExample { public static void main(String[] args) { Stack stack = new Stack(); // 데이터 입력 stack.push(5); stack.push(4); stack.push(3); stack.push(2); stack.push(1); // 데이터 출력 System.out.println("마지막에 넣은 데이터부터 출력.."); System.ou.. 2016. 6. 10. [자료구조] 힙과 힙소트 힙 힙은 자료구조의 하나로 최대값, 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로한다. l 최대힙 : 부모노드의 값이 자식노드보다 크다. l 최소힙 : 자식노드의 값이 부모노드보다 크다. 부모와 자식 노드간의 대소관계만 정해지고, 자식 노드간의 대소관계는 정해지지 않는다. 힙정렬 힙을 구성하여 정렬을 수행하는 것을 힙정렬이라 한다. 최대힙을 이용하여 정렬을 수행하는 방법은 다음과 같다. 1. 최대힙을 구성한다. 2. 최대힙의 루트값을 배열의 맨뒤로 보내고 배열의 사이즈를 하나 줄인다. 3. 변경된 배열에 대해서 최대힙을 다시 구성한다. 4. 2 ~ 3의 과정을 배열의 길이가 1이 될때까지 반복한다. 소스코드[Java] public class MaxHeapSort { public.. 2015. 6. 8. [자료구조] 배열과 링크드 리스트 배열과 링크드 리스트 배열 - 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. - 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 접근 속도가 매우 빠르다. - 그러나 배열은 데이터의 삽입/삭제에는 취약하다. n 배열의 특성상 데이터 삽입/삭제가 이루어지면, 다음 위치의 모든 데이터의 위치를 변경해야 하기 때문이다. 링크드 리스트 - 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주소는 순차적이지 않다. - 현재 위치 이전 및 다음 위치를 기억하고 있다. n 따라서 한번에 데이터에 접근할 수 없고, 순차적으로 링크를 따라가야만 접근이 가능하다. - 링크드 리스트의 종류 n 링크드 리스트(Simple Linked List) u .. 2015. 6. 4. 이전 1 다음