[Algorithm] 검색, 스택과 큐 실습 (자바)

03. 검색

03-1. 검색 알고리즘

• 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행
• 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
• 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행 (체인법/오픈 주소법)

=> 용도나 목적, 실행속도, 자료구조 등을 고려하여 알고리즘을 선택하여야 함

03-2. 선형 검색

실습 3-1

실습 3-3 / 보초법 사용

03-3. 이진 검색

=> 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

실습 3-4

04. 스택과 큐

스택

: 데이터를 일시적으로 저장하기 위해 사용하는데이터 입력 순서는 LIFO(Last In First Out)

• push: 데이터를 넣는 작업
• pop: 데이터를 꺼내는 작업

 

출처: https://muckycode.blogspot.com/2015/01/stack.html

스택 만들기

예외클래스를 생성하고 생성자에는 스택 본체용 배열을 생성하는 등 준비작업을 수행한다.

 

스택 푸시 메소드 생성

 

스택 팝, 피크 메소드 생성

그 외 메소드들 생성

05. 큐

: 데이터를 일시적으로 쌓아 두기 위한 자료구조. 예)마트에서 계산을 기다리는 대기열

• FIFO(First In First Out). 스택과는 달리 선입선출을 한다.
• 인큐(enqueue) :데이터를 넣는 작업
• 디큐(dequeue): 데이터를 꺼내는 작업

 

 

링버퍼

: 배열요소를 앞쪽으로 옮기지 않는 큐. 배열의 처음이 끝과 연결되었다고 보는 자료구조이다.

• 프런트: 첫번째 요소
• 리어: 마지막 요소

 

링버퍼 활용