자료구조

[JAVA] Priority Queue

우선 순위 큐는 가장 높은 우선 순위 요소의 효율적인 검색을 지원하는 자료구조이다. 요소에는 대기열에서 액세스하거나 제거하는 순서를 결정하는 우선 순위가 할당된다. 우선순위 대기열은 FIFO(First-In-First-Out) 동작을 나타내어 우선순위가 가장 높은 요소가 항상 대기열의 맨 앞에 오도록 한다. Priority Queue의 특징 1. 높은 우선순위의 요소를 하나씩 꺼내서 처리하는 구조 2. 보통 바이너리 힙으로 Priority Queue를 구현하고, 이는 이진트리 구조로 이루어져 있다. 3. 삽입, 삭제에 대해 시간 복잡도가 O(NLogN)이다. Java Priority Queue 구현 import java.util.PriorityQueue; public class PriorityQueueE..

힙(heap)

완전 이진 트리의 일종 우선순위 큐를 위해 만들어진 자료구조 느슨한 정렬 상태 유지 큰 값이 상위 레벨에 있는 동시에 하위 레벨에도 존재 가능 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 큰 이진 트리 힙 트리에서는 중복된 값 허용 힙의 종류 최대 힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 힙 구현 자료구조 배열 사용(표준) 0번 인덱스 사용 x 부모 노드 자식 노드 관계 왼쪽 자식 노드 = (부모 인덱스) *2 오른쪽 자식 노드 = (부모 인덱스) *2 +1 부모 노드 = (자식 인덱스)/2 활용 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석..

덱(deque)

덱 Double-Ended Queue 앞쪽과 뒤쪽에서 모두 삽입과 삭제가 가능한 큐 덱 연산 push_front: 덱의 가장 앞에 값을 삽입 push_back: 덱의 가장 뒤에 값을 삽입 pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 반환한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 반환한다. size: 덱에 들어있는 정수의 개수를 출력한다. isEmpty: 덱이 비어있으면 true, 그렇지 않으면 false 반환 isFull: 덱이 가득차면 true, 그렇지 않으면 false 반환 front: 덱의 가장 앞에 있는 정수를 출력한다. back: 덱의 가장 뒤에 있는 정수를 출력한다. 덱 구현(배열 사용) public class Deque{ int deque[] = n..

큐

큐 입구와 출구가 각각 하나씩 있는 자료구조 FIFO(First In First Out) 큐 연산 enQueue : 큐의 가장 마지막 아이템 뒤에 새로운 아이템을 추가한다. deQueue : 큐의 맨앞에 있는 아이템을 빼면서 반환한다. isEmpty : 큐가 비어있는지 확인한다. isFull : 큐가 꽉 찾는지 확인한다. 큐 구현(배열 사용) public class Queue{ int queue[] = new int[10]; int front = 0; int rear = 0; public void enQueue(int item){ if(isFull()){ System.out.println("큐가 꽉 차있습니다."); return; } queue[rear] = item; rear = (rear + 1)%1..

스택

스택 입구와 출구가 하나밖에 없는 자료구조 LIFO(Last In First Out) 스택 연산 pop() : 스택의 가장 위에 있는 데이터를 제거하면서 반환한다. push(item) : item을 스택의 가장 윗부분에 추가한다. isEmpty() : 스택이 비었는지 확인한다. 스택 구현(배열 사용) public class Stack{ private int stack[50]; private int top=-1; public int pop() { if(isEmpty()){ System.out.println("스택이 비었습니다."); return -1; } return stack[top--]; } public void push(int item){ stack[top++] = item; } public bool..