12월 4일 - 자료구조(datastructure)
// USF(university of sanfrancisco) visualization 사이트 들어가면 자료구조 그림으로 이해할수있게 참고가능!
1. 스택 : 후입선출(LIFO) 방식. 가장 최근에 들어 온 데이터가 가장 먼저 나감
데이터를 삽입 삭제하는 연산이 한쪽에서만 진행됨
데이터를 여러개 저장가능(여러개 저장가능한것들=배열,리스트,맵)
- top 제일 마지막에 저장된 값 확인
0) 생성자
크기를 전달받아서 해당 크기만큼 정수를 저장할 수 있는 배열 생성
top에 -1저장
1) isEmpty
스택에 값이 모두 비어있는지 확인
top이 -1이면 비어있다 -> true를 반환
그렇지 않으면 false를 반환
2) isFull
스택에 값이 모두 저장되어있는지 확인
top이 배열의 크기보다 1작으면 true 반환
그렇지 않으면 false를 반환
3) peek
제일 마지막에 저장된 값 확인
제일 마지막에 저장된 값을 반환(메소드니까 반환해야함)
4) push
데이터를 저장하는 연산
저장할 데이터를 전달받고
스택이 가득차 있지 않으면(메소드를 사용해보면 됨)
top을 1증가하고 해당 인덱스 번호의 배열에 데이터 저장
5) pop
데이터를 삭제하는 연산
top 인덱스 번호의 배열에 값을 꺼내고
top 인덱스 번호의 배열에 값을 비워주고
top 을 1감소
6) display
스택에 저장된 모든 데이터를 출력하는 기능
- 큐 : 선입선출('FIFO') 방식. 가장 먼저 들어온 데이터가 가장 먼저 나감
데이터를 삽입하는 연산과 삭제하는 연산이 양쪽에서 진행됨
배열에 직접 접근해서 숫자를 저장할 수 있으면 안되기 때문에 접근 제어자로 제어
- 맨 앞에 데이터가 어디에 저장된건지 가리킬 front 변수 생성
- 다음 데이터가 어디에 저장될건지 가리킬 rear 변수 생성
- 현재 저장된 데이터의 수를 저장할 num 변수 생성
0) 생성자
크기를 전달받아서 해당 크기만큼 정수를 저장할 수 있는 배열 생성
front 및 rear는 0 을 저장
1) isEmpty
num가 0이면 true 반환
그렇지 않으면 false 반환
2) isFull
배열의 크기가 num랑 같으면 true 반환
그렇지 않으면 false 반환
4) enQueue
데이터를 저장하는 연산
저장할 숫자를 하나 전달받고
큐가 가득 찼으면 가득찼다고 출력
그렇지 않으면 현재 rear의 위치의 배열에 전달받은 숫자를 저장하고 rear 1증가 후 num 1 증가
5) deQueue
데이터를 삭제하는 연산
큐가 비어있으면 비어있음 이라고 출력
그렇지 않으면 현재 front의 위치의 배열의 값을 꺼내고 front 1증가 후 num 1 감소
6) display
큐에 저장된 모든 데이터를 출력하는 기능
1. 재귀 (Factorial = ex. 5! = 54321)(// ~안에서 ~호출)
: 메소드가 자기 자신을 자기 안에서 실행하는 형태
// 피보나치 함수 = 1 1 2 3 5 8 13 21 ...(앞에 2개 수를 더해서 나온 값이 계속...)
- 재귀 활용
1) 최대공약수(유클리드 호제법)---------(EuclidGCD)22, 8
- 큰 수를 작은 수로 나누었을 때 나머지가 0이면 작은 수가 최대공약수이다.
- 나머지가 0이 아니면 나머지와 작은 값으로 다시 반복
2) 하노이 탑(Hanoi)
3개의 기둥이 있고 원반을 옮길 때 작은 원반이 항상 큰 원반 위에 오게 옮기는 방법
원반은 하나씩만 옮길 수 있다.
