Computer Science/자료구조15 [자료구조] 큐 (Queue) 큐 (Queue) 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조 FIFO (First In First Out, 선입선출) 저장된 자료들은 선후 관계가 모두 1:1 front : 큐의 제일 앞, 자료가 반환되는 곳 rear : 큐의 제일 뒤, 자료가 추가되는 곳 enqueue() : 큐에 자료를 삽입하는 함수 dequeue() : 큐에서 자료를 빼내는 함수 peek() : 큐에 맨 위에 있는 자료 반환하는 함수 (큐에서 삭제는 하지 않는다) 큐의 크기 : 큐가 저장할 수 있는 최대 자료의 개수 → 이 갯수를 넘어버리면 오버플로우(Overflow) 발생 ex) 은행 업무 처리 대기열, 프린터 대기 문서 //배열로 구현한 선형 큐 public class Main { stati.. 2020. 8. 31. [자료구조] 스택 (Stack) 스택 (Stack) 자료를 한 방향으로만 쌓는 자료구조 LIFO (Last In First Out 후입선출 : 마지막에 들어온 것이 가장 먼저 나간다) push : 스택에 data를 넣는 것 pop : 스택 맨 위의 data를 빼는 것 peek : pop과 유사하게 맨 위의 data를 반환하지만 스택에서 제거하지는 않는다. top : 가장 마지막에 추가된 data의 위치 (가장 맨위) 가장 마지막에 push 한 data가 가장 먼저 pop 된다. 오버플로우 (Overflow) : 자료가 스택 크기를 넘어서서 더 이상 push 하지 못할 때 발생 언더플로우 (Underflow) : 스택에 자료가 남아있지 않아서 더 이상 pop하지 못할 때 발생 배열로 구현해보기 public class Main { stat.. 2020. 8. 26. [자료구조] Trie 트라이 트라이 (Trie) retrieval Tree에서 온 단어 문자열들을 트리 구조로 저장하여 O(log n) 속도로 빠르게 문자열을 탐색할 수 있게 해준다. 알고리즘 문제에선 주로 문자열의 '접두어', '~로 시작하는', '접미어', '~로 끝나는' 등의 키워드가 나오는 접두어, 접미어 판별 문제에서 사용된다. ※ 참조 문제 코딩테스트 연습 - 가사 검색 programmers.co.kr 자바로 트라이 구현하기 1. 노드 (Node) 클래스 import java.util.HashMap; public class Node { //해당 node 밑의 서브트리 총 node 개수 (옵션 : 즉 필요에 따라 넣는 요소) int count = 0; // isLast = true면 해당 문자열 존재 boolean isLa.. 2020. 8. 26. [자료구조] 연결 리스트의 종류 1. 단순 연결 리스트 (Singly Linked List) 단방향 링크 이전 노드에 접근하기 위해선 첫 번째 노드부터 다시 순회해야함 2. 원형 연결 리스트 (Circular Linked List) 단방향 링크 마지막 노드와 첫 번째 노드가 연결된 원형 구조 이전 노드에 접근하기 위해서 계속 한 방향으로만 순회하면 됨 3. 이중 연결 리스트 (Doubly Linked List) 양방향 링크 각 노드가 앞 뒤로 연결됨 이전 노드에 직접 접근 (Direct Access) 가능 2020. 8. 25. 이전 1 2 3 4 다음
