Algorithm/Data structure3 Queue ADT 정의, Java 구현 일단 Queue ADT부터 정의해보자. Queue는 선형 자료구조 일종으로 FIFO 구조로 작동하고, 양 쪽 끝에서 각각 삽입, 삭제가 이루어진다. 따라서 삽입을 위한 enqueue(data) - O(1), 삭제를 위한 deque() - O(1) 연산이 있다. 이를 이용하여 bfs탐색, 혹은 대기열 버퍼, 캐싱 등을 할 때 사용할 수 있다. Queue를 응용한 Deque 구조가 있는데 양쪽에서 삽입,삭제가 모두 일어난다. C++에는 std::deque, Java에서는 Deque 인터페이스를 상속한 ArrayDeque 클래스가 있다. Stack과 마찬가지로 데이터를 저장하는 부분을 배열 혹은 링크드리스트로 구현을 할 수 있고, 이에 따라 resize 연산을 추가로 구현해야한다. 여기서는 단방향 링크드리스트.. 2022. 4. 26. Stack ADT 정의, Java 구현 일단 Stack의 ADT부터 정의해보자. 스택은 대표적인 LIFO 나열 구조로서 한 쪽 끝에서만 자료를 넣고 빼는 선형구조이다. 따라서 최상단에 자료를 추가 - O(1), 최상단 자료를 삭제 - O(1), 최상단 자료를 조회 - O(1), 비었는지 확인 - O(1) 하는 연산이 존재한다. 또한 자료를 정적 배열에 저장하는지 혹은 LinkedList로 저장하는 지에 따라 resizing을 해주는 연산이 필요할 수도, 필요하지 않을 수도 있다. 여기서는 단방향 링크드리스트 구조로 정의 하였다. 1. Stack과 Node에 필요한 필드를 정의한다. public class Stack { private Node top; private class Node { Object data; Node link; Node(Ob.. 2022. 4. 26. Doubly linkedList (이중 연결리스트) Java 구현 일단 LinkedList의 ADT부터 정의해보자. 연결된 노드들이 서로의 메모리 위치를 가리키면서 요소를 저장하고 검색해야한다. 배열이나 리스트처럼 연속된 주소에 저장되어있지 않고 노드주소들이 떨어져있기 때문에 인덱스값을 통해서 조회할 수 없어, 특정 값이나 인덱스를 조회 시에 O(N) 시간복잡도가 소요된다. 각 노드들은 두 개의 포인터(prev, next)와 데이터를 가지고, DoublyLinkedList는 맨 처음과 맨 마지막을 가리키는 포인터(head, tail)이 있다. 이 것들을 이용해서 노드를 추가 - O(1), 조회 - O(N), 삭제 - O(1) 하는 연산이 있어야 한다. C++의 경우에는 STL의 list container가 이미 doubly-linkedlist로 작성되어 있어서 양방향 .. 2022. 4. 26. 이전 1 다음
