다음주에 시험 또볼예정...................
방이 선택되어 남은 방개수가 줄어드는 것은 LinkedList의 stack과 큐로 구현하기(큐로 구현하기)
Stack클래스
Queue인터페이스
Algorithm - stack
노드 : 데이터 통신망에서, 데이터를 전송하는 통로에 접속되는 하나 이상의 기능 단위
<Stack>-한쪽막힌 원통
package Algorithm;
public class Stack<T> {
class Node<T>{ //T는 데이터타입
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
}//한개의 노드가 가질 수 있는 내용
}
private Node<T> top;
public void push(T item) {
Node<T> t = new Node<T>(item);//새로운 숫자등장
t.next = top;////4 입장에서 t가 나인데 t.next가 3이길 바래 얘가 원래 top이었자나. t.next자체가 나보다 원래 먼저 들어가있던애이다.
top = t; //얘가 탑으로 올라감.
}
//현재의 top이 나의 다음 노드가 되었으면 좋겠어~
//그리고 내(t)가 탑으로 갈거야~
public T pop() { //실제데이터값도 뽑아줘야 함.
if(top == null) {
System.out.println("empty");
}
T item = top.data; //top에 있는 data값을 뽑아서 T item에 저장
top = top.next; //그 아래값이 top이 됨
return item;
}
public T peek() { //맨 위의 값 출력
if(top == null) {
System.out.println("empty");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}
public static void main(String[] args) {
Stack<Integer> s = new Stack<Integer>();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.peek());
System.out.println(s.isEmpty());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.isEmpty());
}
<Queue>
package Algorithm;
import java.util.NoSuchElementException;
import Algorithm.Queue.Node;
public class Queue<T> { //큐는 원통형
class Node<T>{
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
}//한개의 노드가 가질 수 있는 내용
}
private Node<T> first;
private Node<T> last;
public void enqueue(T item) {//나보다 먼저 있던 애가 나보다 앞에있고 내 뒤에 들어오는애가 내 뒤에 있었으면 좋겠다.
Node<T> t = new Node<T>(item);
if(last!=null) {
last.next = t;
}
last = t;
if(first == null) {
first = last;
}
}
public T dequeue() {
if(first == null) {
throw new NoSuchElementException();
}//예외강제발생
T item = first.data;
first = first.next;
if(first ==null) {
last = null;
}
return item;
}
public T peek() {
if(first == null) {
throw new NoSuchElementException();
}//예외강제발생
return first.data;
}
//throws : 예외 던져버리기
public boolean isEmpty() {
return first == null;
}
}
package Algorithm;
public class QueueTest {
public static void main(String[] args) {
Queue<Integer> q = new Queue<Integer>();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(q.peek());
System.out.println(q.isEmpty());
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(q.isEmpty());
}
}
-Tree
이진 트리 검색
in-order방식 -1>2>3>4>5>6>7
package Algorithm;
/* 4
* / \
* 2 6
* /\ /\
* 1 3 5 7
*/
//잎 구조 binary tree search
public class BSTSearch {
class Node{ //타입이 없다.
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
Node root; //모든이의 뿌리 제일 위에 있는 숫자
public void insert(int data) {
root = insert(root,data);
}
public Node insert(Node root, int data) {
if(root == null) {
root = new Node(data);//4
return root;
}
if(data<root.data) {
root.left=insert(root.left,data);//재귀함수
}else if(data>root.data) {
root.right = insert(root.right,data);
}
return root;
}
public void inorder() {
inorder(root);
}
public void inorder(Node root) {
if(root!=null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
public Node search(Node root, int key) {
if(root==null || root.data == key)return root;
if(root.data>key) {
return search(root.left,key);
}else {
return search(root.right,key);
}
}
public static void main(String[] args) {
BSTSearch tree= new BSTSearch();
tree.insert(4);
tree.insert(2);
tree.insert(1);
tree.insert(3);
tree.insert(6);
tree.insert(5);
tree.insert(7);
tree.inorder();
Node node = tree.search(tree.root,5);
if(node==null) {
System.out.println("찾을 수 없습니다.");
}else {
System.out.println(node.data);
}
}
}
++삭제구현(어려움) -> 해당하는 숫자 삭제하기
//삭제
//1. no child : 부모의 링크를 끊는다.
//2. one child : 부모의 링크를 조정
//3. two child : 왼쪽뿌리에서 가장 큰값이 올라오던지 오른뿌리에서 가장 작은값이 올라오던지 올라오는 해당노드는 삭제
public Node delete(Node root,int data) {
if(root == null) return root;
if(data<root.data) {//삭제하고자 하는 값을 찾아감
root.left = delete(root.left,data);
}else if(data > root.data) {//삭제하고자 하는 값을 찾아감
root.right = delete(root.right,data);
}else { //data = root.data
if(root.left==null && root.right == null)return null;//자식이 없을때 그냥 그 root바로 삭제
else if(root.left==null) return root.right;//자식이 하나밖에 없을때
else if(root.right==null)return root.left;
else {//자식이 두명일때(오른쪽의 가장 작은값을 찾아 올려주는 방법)
root.data = findMin(root.right); //오른쪽의 가장 왼쪽에 있는 걸 올려서 40을 찾아라
root.right = delete(root.right,root.data);//그 40을 삭제시켜서 해당하는 값을 right에 붙여줘라.
}
}return root;
}
public int findMin(Node root) {
int min = root.data;
while(root.left != null) {
min = root.left.data;
root = root.left;
}
return min;
}
TreeTest구현해보기
(배열로 바이너리서치 구현하기)
TreeTest
package Kosta.Algorithm;
//import Kosta.Algorithm.BSTSearch.Node;
/*
* 4
* / \
* 1 7
* / \ / \
* 0 2 5 8
* \ \
* 3 9
*/
class Tree{
class Node{
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
Node root;
public void makeTree(int arr[]){
root = makeThreeR(arr, 0, arr.length-1);
}
public Node makeThreeR(int arr[], int start, int end){
if(start > end) return null;
int mid = (start + end)/2;
Node node = new Node(arr[mid]);
node.left = makeThreeR(arr, start, mid-1);
node.right = makeThreeR(arr, mid+1, end);
return node;
}
public void searchBTree(Node n, int find){//노드 n, 찾는값 find
if(find < n.data){
System.out.println("Data is smaller than " + n.data);
searchBTree(n.left, find);
}else if(find > n.data){
System.out.println("Data is bigger than " + n.data);
searchBTree(n.right, find);
}else{
System.out.println("Data found");
}
}
}
public class TreeTest {
public static void main(String[] args) {
int arr[] = new int[10];
for(int i=0;i<arr.length;i++) {
arr[i] = i;
}
Tree t = new Tree();
t.makeTree(arr);
t.searchBTree(t.root, 3);
}
}
Data is smaller than 4
Data is bigger than 1
Data is bigger than 2
Data found
'FULLSTACK > JAVA' 카테고리의 다른 글
| JAVA PROJECT (0) | 2020.11.13 |
|---|---|
| JAVA 20차시 - 알고리즘 (0) | 2020.11.13 |
| JAVA 18차시 - Test , 호텔예약프로그램 (프로젝트) (0) | 2020.11.13 |
| JAVA 17차시 - 네트워크 통신 프로그래밍 (0) | 2020.11.13 |
| JAVA 16차시 - File, Thread (0) | 2020.11.12 |