S E P H ' S

Deque (Using Array) Deque는 Double-ended queue의 줄임말이다. 두 개의 종료지점이 있는 queue라는 뜻이다. 덱의 장점은 스택처럼 사용할 수도 있고 큐처럼 사용할 수 있는 자료구조이다. 덱의 구조를 큐의 구조와 한번 비교해보자 Deque는 삽입, 삭제가 총 12 종류가 있다. offer 계열과 poll 계열의 경우 삭제 과정에서 저장공간이 넘치거나 삭제할 원소가 없을 때 특정 값(null, false 등)을 반환하지만, add 계열과 remove 계열은 예외를 던진다. ArrayDeque 구현 클래스 및 생성자 구성 resize 메소드 구현 offer 계열 메소드 구현 poll 계열 메소드 구현 peek 계열 메소드 구현 size, isEmpty, contains, c..

Queue (Using LinkedList) 7. 배열 큐(Array Queue) 와는 다르게 LinkedList를 기반으로 구현한다. 기본적으로 LinkedList에 대한 이해가 필요하다. 자바에서는 대중적으로 LinkedList로 구현한 큐를 많이 사용한다. 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고 있기 때문에 요소가 들어있는 배열의 용량에 따라 resize()를 해주어야 하고 선형 큐로 구현한 경우 요소들이 뒤로 쏠리는 문제가 있기 때문에 이러한 문제를 효율적으로 극복하고자 원형으로 구현하는데 이 구현이 고려해야 할 점도 많고 복잡하다. 배열 대신 연결리스트로 구현할 경우 많은 단점들이 해결된다. 각 데이터들을 노드 객체에 담고 노드 간 서로 연결하기 때문에 배열처럼 요소 개수..

Queue 선입선출의 대표적 자료구조인 Queue를 구현하고자 한다. java에서 제공하고 있는 Queue는 인터페이스이고 이 Queue 인터페이스를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다. 대개는 LinkedList로 구현한 큐가 쓰이지만, 상황에 따라 ArrayDeque나 PrioirityQueue처럼 내부적으로 배열을 사용해 구현하는 큐 자료구조도 있다. 기본적으로 배열을 사용하여 구현되는 자료구조 클래스는 내부에서 최상위 타입인 Object[] 배열을 사용하여 데이터들을 관리하고 있다. 큐의 삭제가 계속된다면 뒤에 있던 원소들을 앞으로 땡겨오지는 않는다. 결국 원소들이 뒤로 치우치게 되는 경우가 발생하는데 삭제가 발생할때마다 모든 원소..

Queue Interface Queue는 '대기열'이라고 생각하면 된다. 흔히 리그오브레전드의 '큐 잡는다' 할때의 큐가 이 Queue를 의미한다. 큐는 스택과는 다르게 선입선출(First in First Out)의 구조를 가진다. 먼저 들어온 것이 가장 먼저 구조를 빠져나가는 것이다. 보통 시간 순으로 작업이나 데이터를 처리할 때 사용하고 대표적으로 알고리즘에서 BFS(너비 우선 탐색)에 사용된다. Queue Interface에 선언할 메소드 메소드 리턴 타입 설명 offer(E e) boolean 큐의 마지막에 요소를 추가한다. poll() E 큐의 첫 번째 요소를 제거하고 제거된 요소를 반환한다. peek() E 큐의 첫 번째 요소를 제거하지 않고 반환한다. 큐 같은 경우는 실제로 자바에서도 6가지..