Algorithm/Stack & Queue4

• 

  [자료구조] 자바 덱(Deque)의 클래스 사용하기 카프카의 소스코드를 보던 중 내부에서 Deque 클래스를 사용한 부분을 보게 되었다. Deque(덱 혹은 데크)은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다. 참고 : 월급쟁이의 경제적 사유 덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다. 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다. Java에서의 Deque 자바에서의 덱은 인터페이스로 구현되었다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 Ar.. Algorithm/Stack & Queue 2022. 7. 7.

• 

  [자료구조] 자바 우선순위 큐(Priority Queue)의 클래스 사용하기 Priority Queue 일반적인 큐의 구조 FIFO (First In First Out)을 가진다. 우선순위를 먼저 결정하고, 우선순위가 높은 데이터가 먼저 나가는 구조이다. 우선순위 큐를 사용하기 위해 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다. Comaprable Interface 구현 시 compareTo method 를 override 하여 처리할 우선순위 조건을 리턴하면, 우선순위 큐가 우선순위가 높은 객체를 추출해준다. (기본적으로 낮은 숫자부터 큰 숫자 오름차순이다) Heap을 이용하여 구현하는 것이 일반적이다. 데이터 삽입 시 우선순위 기준으로 최대 힙, 최소 힙을 구성한다. 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈.. Algorithm/Stack & Queue 2022. 7. 5.

• 

  [자료구조] 자바 스택(Stack)의 클래스 사용하기 스택(Stack)의 특징 1. 먼저 들어간 데이터가 나중에 나오는 후입선출, LIFO (Last In First Out) 구조로, 마트용 음료수 진열대와 같은 구조이다. 2. 한 쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료 구조여서 데이터를 쌓는 형식으로 저장하며 조회, 추가, 삭제 등 모두 가장 위에 있는 (가장 마지막에 삽입된) 값에서 이루어진다. 이 데이터를 Top이라고한다. 3. 그래프(Graph)의 깊이 우선 탐색(DFS)에 사용된다. 4. 재귀적(Recursion) 함수를 호출할 때 사용한다. 스택(Stack) 클래스 선언 import java.util.Stack; Stack stack = new Stack(); 메서드 public Element push(Element item);// 데이터 .. Algorithm/Stack & Queue 2022. 6. 19.

• 

  [자료구조] 자바 큐(Queue)의 클래스 사용하기 큐(Queue)의 특징 1. 먼저 들어간 데이터가 먼저 나오는 선입선출, FIFO(First In First Out) 구조로, 줄을 서서 기다리는 구조와 같다. 2. 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행한다. 3. 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행한다. 4. 그래프(Graph)의 넓이 우선 탐색(BFS)에 사용된다. 큐(Queue) 클래스 큐(Queue) 선언 자바에서 큐(Queue)는 LinkedList를 활용해서 사용한다. import java.util.Queue; import java.util.LinkedList; Queue queue = new LinkedList(); 큐(Queue) 동작 및 메서드 Enqueue 동작 큐에 데이터를 추가하는 동작으로 o.. Algorithm/Stack & Queue 2022. 6. 19.