목록Programing & Coding (86)
S E P H ' S
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가지..
스택(Stack) 구현 클래스 및 생성자 구성 resize 메소드 구현 push 메소드 구현 pop 메소드 구현 peek 메소드 구현 search, size, clear, isEmpty 메소드 구현 ArrayList를 상속한 Stack Stack 클래스 및 생성자 구하기 public class Stack implements StackInterface{ private static final int DEFAULT_CAPACITY = 10; // 최소 용적 크기 private static final Object[] EMPTY_ARRAY = {}; // 빈 배열 private Object[] array; // 요소를 담을 배열 private int size; // 요소 개수 public Stack() { th..
Stack Interface 스택은 먼저 들어온 데이터가 마지막에 나가게 되는 후입선출(LIFO = Last In First Out) 구조를 가지는 자료구조이다. 코딩을 하다가 자주 만나게 되는 'java.lang.StackOverFlowError'가 이 스택에서 나는 것이다. 메소드를 호출할 때마다 메소드 내에 정의된 변수들의 값이 stack 메모리에 쌓이게 되는데 재귀가 깊어지면 stack 메모리에 이 값들이 쌓이면서 해당 총량이 할당된 메모리보다 커질 때 내뱉게 된다. 자바 내부에서는 스택은 Vector 클래스를 상속받아 사용한다. Vector는 ArrayList와 크게 다르지 않다. 내부 구조는 Object[] 배열로 데이터들을 관리하며 전체적인 메소드 구조도 많이 유사하다. 다만 차이점은 동기화..