본문 바로가기
728x90

넓고 얕은 자료구조 & 알고리즘/자료구조론12

Deque(Double Ended Queue) Deque(Double Ended Queue) 양방향 대기열이라고도 한다. 양방향으로 열려있는 구조로, LIFO, FIFO와 같은 순서에 구속되지 않는다. 실의 양쪽에 구슬을 꿰어 넣는 것과 같이 Stack과 Queue의 특성을 동시에 이용할 수 있다. Deque의 특징 Stack과 Queue를 이용한 경우의 수 한쪽에서만 데이터 추가가 가능하고, 양쪽에서 모두 데이터 삭제가 가능한 경우 양쪽에서 모두 데이터 추가가 가능하고, 한쪽에서만 데이터 삭제가 가능한 경우 양쪽에서 모두 데이터 추가와 삭제가 가능한 경우 임의의 데이터를 임의의 인덱스에 추가, 삭제는 불가능하다. 2022. 9. 27.
그래프(graph)와 트리(tree) 그래프(graph) 여러 개의 점들이 서로 연결되어 있는 관계를 표현한 자료구조 그래프에서 하나의 점을 정점(vertex), 하나의 선을 간선(edge)라고 한다. 인접 행렬 [1] = [0, 0, 1, 0, 1] // 간선이 있으면 1, 없으면 0 [2] = [0, 0, 0, 1, 0] // 무방향 그래프 [3] = [1, 0, 0, 0, 0] [4] = [0, 1, 0, 0, 0] // ex) 4 -> 5처럼 한 방향만 있으면 방향 그래프 [5] = [1, 0, 0, 0, 0] 두 정점을 이어주는 간선이 있을 때, 이 두 정점을 인접하다고 한다. 예를 들어 A, B, C라는 서로 다른 정점이 있고 A와 B가 서로 이어져 있다면 1(true), 이어져 있지 않다면 0(false)을 표시한다. 한 개의 .. 2022. 9. 26.
큐(queue) 구현해보기 큐(queue) 선입선출(FIFO: First In First Out)의 구조를 갖는 자료구조이다. // 배열을 이용한 원형 큐 구현하기 public class RingQueue { private int[] que; // 큐용 배열 private int capacity; // 큐 용량 private int front; // 맨 앞의 요소의 인덱스 private int rear; // 맨 뒤의 요소에서 하나 뒤 인덱스(인큐할 때 저장될 요소의 인덱스를 미리 준비) private int num; // 현재 데이터 개수 // front와 rear 값이 같을 때 큐가 비어있는지, 가득찼는지 구분하기 위해 만든 변수 // 실행 시 예외 : 큐가 비어있는 경우 public class EmptyQueueExcepti.. 2022. 9. 23.
스택(Stack) 구현해보기 스택 데이터를 일시적으로 쌓아 놓는 구조로, 후입선출(LIFO: Last In First Out) 순서를 가진다. 나중에 넣은 데이터가 가장 먼저 나오는 구조이다. 스택 구현을 통해 공부해보면 쉽게 이해할 수 있다. // 배열을 이용한 인트형 고정 길이 스택 구현하기 public class IntStack { private int[] stack; // 스택용 배열 private int capacity; // 스택 용량 private int pointer; // 스택 포인터 // 실행 시 예외 : 스텍이 비어있는 경우 public class EmptyStackException extends RuntimeException { public EmptyStackException() {} } // 실행 시 예외 :.. 2022. 9. 23.
728x90

티스토리툴바