8/23 [자료구조]-선형구조,비선형구조

[큐] 

먼저 들어온 것이 먼저 나가는 자료구조

- 가장 먼저 넣은 데이터를 가장 먼저 꺼냄 -> 선입선출(FIFO: First in First out)

- Enqueue와 Dequeue를 통해 데이터를 다룸

package 큐;

import java.util.LinkedList;
import java.util.Queue;

public class Ex01큐생성 {

	public static void main(String[] args) {
		
		//1. 큐생성(LinkedList)
		//인터페이스로는 객체 생성이 불가능하다
		Queue<Integer>que = new LinkedList<>();
		
		//2. 요소 삽입(add/ offer)
		que.add(1); //boolean (여유공간이 없으면 Exception(예외상황-(런타임(실행) 시 오류 발생) 발생)
		que.offer(2); //boolean (여유공간이 없으면 false 리턴)
		
		//3. 맨 앞에 값 확인(element / peek)
		System.out.println(que.element()); //큐가 비어있으면 Excaption 발생
		System.out.println(que.peek()); // 큐가 비어있으면 null 리턴

		
		//4. 맨 앞에 요소 삭제(remove / poll)
		que.remove();// 큐가 비어있으면 Exception 발생
		que.poll(); // 큐가 비어있으면 null 리턴
	}

}

[4.데크]

삽입과 삭제가 리스트 양쪽 끝에서 모두 발생할 수 있는 자료구조

가장 먼저 넣은 데이터가 빨리 나갈수도 늦게 나갈수도 있음

스택과 큐의 장점을 모두 가지고 있는 방식

한 쪽에서 삽입, 삭제 동시에 -> 스택

한 쪽에서 삽입 한 한 쪽에서 삭제 ->큐

Vector(부모) -> 상속(중간삽입,삭제) ->Stack(자식)

package 데크;

import java.util.ArrayDeque;
import java.util.Deque;

public class Ex01데크생성 {

	public static void main(String[] args) {
		
		//1. 데크로 스택 생성
		Deque<String>stack = new ArrayDeque<>();
		
		// 데크에 요소 삽입(앞으로만 삽입)
		stack.addFirst("apple");
		stack.addFirst("banana");
		stack.addFirst("kiwi");
		
		// 데크에 요소 삭제(앞에서만 꺼내기)
		System.out.println(stack.removeFirst());
		System.out.println(stack.removeFirst());
		System.out.println(stack.removeFirst());
		
		//2. 데크로 큐 생성
		Deque<String> queue = new ArrayDeque<>();
		
		//데크에 요소 삽입(맨 앞에서만 추가)
		queue.addFirst("peach");
		queue.addFirst("grape");
		
		//데크에 요소 삭제(맨 끝에서만 삭제)
		System.out.println(queue.removeLast());
		System.out.println(queue.removeLast());

	}

}

 

[5.링크드 리스트]

3을 볼때 1번을 보고 싶을때 다시 1로 돌아가야 한다

각노드가 주소가 2개씩 있다 1번은 2번 주소가 있다, 2번은 1,3주소 가지고 있다, 3번은 2,4주소 가지고 있다. 4번은 3번주소 알고 있다

마지막 노드가 첫번째 주소를 알고 있다

package 링크드리스트;

import java.util.LinkedList;

public class Ex01링크드리스트생성 {

	public static void main(String[] args) {
		
		//1. 링크드리스트 생성
		LinkedList<String> llist = new LinkedList<>();
		
		//2.요소 삽입
		llist.add("apple");
		llist.add("banana");
		
		//3. 요소 삭제
		System.out.println(llist.remove());
		
		//3.요소 전체 삭제
		llist.clear();
		

	}

}

[비선형구조]

1.그래프

그래프 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 구조

정점(Node)과 간선(Link)의 집합

경로: 하나의 정점에서 다른 하나의 정점까지 가는 길

사이클: 한 노드에서 시작해서 간선에 따라 다시 시작한 정점으로 돌아오는 경로

경로길이: 경로를 구성하는 간선의 수

차수: 하나의 노드에 연결되어 있는 간선의 수

단순 경로: 한 정점에서 다른 정점에 이르거나 경로를 탐색할 때 하나의 노드를 두 번 거치지 않는 경로()

 

2.방향 그래프: 간선에 방향이 있는 그래프(화살표대로만 갈수 있다)

3. 무방향 그래프 : 간선에 방향이 없는 그래프

4. 가중치 그래프: 간선에 비용이나 가중치가 있는 그래프(최저비용 알고리즘)

비선형구조 

2.트리

트리: 부모-자식관계로 이루어진 계층적인 구조

- 정점(Node)과 선분(Branch)을 이용해 순환하지 않도록 구성한 그래프의 특수한 형태

- Node는 하나의 기억 공간이며 Node 간을 연결하는 선을 링크(Link)라고 함

- 임의의 노드에서 다른 노드로 가는 경로는 유일함

- Cycle이 존재하지 않음

- 모든 노드는 서로 연결되어 있음

 

트리는 한개로 시작해서 마지막으로 가는게 딱 한개 있어야 한다.

 

[트리]

-노드(Node): 기본요소

A,B,C,D,E,F,G,H,I

-근노드(RootNode): 처음 시작 노드 F

-차수(Degree):각 노드의 가지 수

(* 트리의 차수: 가장 큰 차수)

F=2, B=2, G=1, D=2

트리의 차수 =2

- 단말노드(Terminal Node):자식이 하나도 없는 노드, 차수가 0인 노드 A,C,E,H

- 자식노드(Son Node): 어떤 노드에 연결된 노드

  F의 자식노드: B,G

 

- 부모노드(Parent Node): 어떤 노드에 연결된 이전 레벨 노드

  D의 부모 노드:B

- 형제노드(Brother Node): 동일한 부모를 가지는 노드 

   A의 형제노드: D

- 레벨(level), 깊이(Depth): 근노드로부터 level1부터 1씩 증가

   D의 레벨:3

 

-이진트리: 모든 노드들이 둘 이하의 자식을 가진 트리

-전 이진트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

- 완전 이진트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리

완쪽부터 본다/ 왼쪽에 있는  노드기 없으면 완전 이진트리가 아니다

포화 이진트리(Perfect Binary Tree): 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 단말 노드가 동일한 깊이 또는 레벨을 가짐

균형 이진트리(Balanced Binary Tree): 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리

 

[트리의 순회방법]

전위순회(Preorder): 뿌리(root)를 먼저 방문 

중위순회(Inorder): 왼쪽 하위 트리를 방문 후 뿌리를 방문

후회순회(Postorder): 하위 트리 모두 방문 후 뿌리를 방문

(위 트리그림 순서도 : 7-8-3-9-10-4-1-11-5-6-2-0)

층별 순회(levelorder): 위 쪽 node들 부터 아래방향으로 차례로 방문

(위 트리그림 순서도: 0-1-2-3-4-5-6-7-8-9-10-11)

package 트리;

import java.util.TreeSet;

public class Ex01트리생성 {

	public static void main(String[] args) {
		
		//1. 이진트리 생성
		TreeSet<Integer> ts = new TreeSet<>();
		
		//2. 요소삽입
		ts.add(7);
		ts.add(4);
		ts.add(9);
		ts.add(1);
		ts.add(5);
		
		//작으면 왼쪽으로 크면 오른쪽으로/비교는 루트부터 비교한다
		//5가 root 7보다 작으니 왼쪽으로->4 ->왼쪽1보다 크므로 오른쪽에 5를 넣는다
		
		//3. 이진트리의 크기(요소 갯수)
		System.out.println(ts.size());   // console 값->5
		
		//4. 이지트리의 최솟값, 최댓값
		System.out.println(ts.first()+","+ts.last());
		
		//5. 특정값보다 큰 데이터 중 최솟값 찾기
		System.out.println(ts.higher(3));
		
		//6. 특정값보다 작은 데이터 중 최대값 찾기
		System.out.println(ts.lower(3));
	}

}

 

 

시간복잡도, 공간복잡도가 있다/ O:빅 오/ n: 숫자가 클수로 늘어난다/ log: 처음에는 빠르지만 시간이 갈수록 느려진다/

package 스택;

import java.util.Stack;

public class Ex01스택생성 {

	public static void main(String[] args) {
		
		//1. 스택생성
		Stack<String>st = new Stack<>();
		
		//boolean, int -> reference type 이 아님!
		// <> : primitive Tyoe ->Reference Type
		//정수형?
		//int ->Integer
		//char -> Character
		//"123" => 123(String -> int)
		//Integer.parseInt("123");
		Stack<Character>st1 = new Stack<>();
		
		//2. 요소 삽입 (push)
		st.push("apple");
		st.push("banana");
		st.push("kiwi");
		st.push("peach");
		
		
		//3. 가장 위(top)에 있는 데이터 확인
		String s = st.peek();
		System.out.println(s);
		
		//4. 가장 위(top)에 있는 데이터 삭제(꺼내기)
		String s1 = st.pop();
		System.out.println(s1);
		
		System.out.println(st.peek());
		
		//5. 요소 조회(search)
		//특정 데이터가 몇번째에 존재하는지 -> 정수형    스택은 0이 아니라1부터 시작한다  위에서 부터가1번이다
		int n = st.search("banana");
		System.out.println(n); 
		
		//6. 스택이 비어있는지 확인(empty)
		//비어있으면 true 비어있지 않으면 false
		System.out.println(st.empty());
		
		//스택이 빌때까지 요소를 꺼내기
		while(!st.empty()) {//스택이 비어있지 않으면
			//요소를 꺼내기
			System.out.println(st.pop());
		}
		
		
	}

}

<오후수업>

mvc패턴 -> 디자인 패턴 중 가장 기본적이고 많이 사용되는 패턴

 

M: Model -> 데이터를 관리하기 위한 클래스 (설계도)

V: View -> 사용자가 볼수 있는 기능을 정리한 클래스

C: Controller -> view 와 model이 서로 정보를 주고 받을 수 있도록 연결해 주는 클래스

 

[플레이리스트 만들기]

import java.util.Scanner;

public class Mp3View {

	public static void main(String[] args) {
		
		//view 역할을 할 수 있는 클래스!
		
		// [1]재생 [2]정지 [3]다음곡 [4]이전곡 [5]종료
		// - 사용자가 5번을 선택할 경우에만 프로그램이 종료되는 반복문 만들기!
		
		Scanner sc = new Scanner(System.in);
		
		//Controller 접근을 위한 객체 생성!
		MusicController mc = new MusicController();
		
		while(true) {
				System.out.print("[1]재생 [2]정지 [3]다음곡 [4]이전곡 [5]종료 >> ");
				int menu = sc.nextInt();
				
				if(menu==5) {
					System.out.println("프로그램 종료");
					break;
				}else if(menu ==1) {
					//controller에게 요청할 메소드 호출! -> 메세지 요청!
					mc.play();
				}else if(menu ==2) {
					mc.stop();
				}else if(menu ==3) {
					mc.next();
				}else if(menu ==4) {
					mc.pre();
				}
			}
			
		}

	}

import java.util.ArrayList;

import javazoom.jl.player.MP3Player;

public class MusicController {
	// Cotroller 역할을 할 수 있는 클래스 !
	// Model과 view를 연결하는 목적!
	
	// 4개의 곡을 담을 수 있는 ArrayList 생성!
	ArrayList<Music> musiclist = new ArrayList<>();
	
	// 노래를 재생하거나 정지할 수 있는 기능 불러오기!
	MP3Player mp3 = new MP3Player();
	
	// musiclist에 있는 노래 순서를 관리할 수 있는 변수 생성
	int index = 0;
	
	// Controller가 호출 되자 마자 셋팅되어 있는 Mp3를 사용할 수 있도록
	// Controller용 생성자 메소드를 만들어 노래정보 저장하기!
	
	public MusicController() {
		musiclist.add(new Music("라일락", "아이유", 40, "music/lilac.mp3"));
		musiclist.add(new Music("On the ground", "로제", 90, "music/on the ground.mp3"));
		musiclist.add(new Music("peaches", "저스틴비버", 10, "music/peaches.mp3"));
		musiclist.add(new Music("rollin", "브레이브걸스", 117, "music/rollin.mp3"));
	}

	public void play() {
		// 노래 재생을 위한 메소드
		// 호출시 musiclist에 있는 노래를 play!
		 
		if(mp3.isPlaying()) { //실행되는 노래가 있다면 멈추고 다시 재생!
			mp3.stop();
		}
		mp3.play(musiclist.get(index).getMusicpath());		
		show();
	}
	
	public void stop() {
		mp3.stop();
	}
	
	//다음곡 재생을 위한 메소드
	public void next() {
		if(mp3.isPlaying()) {
			mp3.stop();
		}
		
		//index 번호가 3일 때 다시 0으로 돌아갈수 있는 작업 진행!
		if(index < musiclist.size()-1) {
			index++;
		}else {
			//마지막 인덱스에서 다시 다음버튼을 눌렸을 경우!
			index=0;
		}
		
		mp3.play(musiclist.get(index).getMusicpath());
	}
	
	//선택시 이전으로 노래를 play 하는 기능 만들기
	public void pre() {
		if(mp3.isPlaying()) {
			mp3.stop();
		}
		
		if(index > 0) {
			index--;
		}else {
			index = musiclist.size()-1;
		}
		mp3.play(musiclist.get(index).getMusicpath());
		show();
	}
	
	
		public void show() {
			System.out.println(musiclist.get(index).getSongName()+"-"+musiclist.get(index).getSongName());
		}
	}

public class Music {
	
	//뮤직플레이어에 대한 설계도를 작성하는 Model 부분!
	//Model == Value Object (VO)== Data Transfer Object (DTO)

	private String songName;
	private String singer;
	private int playTime;
	private String musicPath;
	
	//생성자 메소드
	public Music(String songName, String singer, int playTime, String musicPath) {
		this.songName = songName;
		this.singer = singer;
		this.playTime = playTime;
		this.musicPath = musicPath;
		
	}
	public String getMusicpath() {
		return musicPath;
	}

	public String getSongName() {
		return songName;
	}

	public void setSongName(String songName) {
		this.songName = songName;
	}

	public String getSinger() {
		return singer;
	}

	public void setSinger(String singer) {
		this.singer = singer;
	}

	public int getPlayTime() {
		return playTime;
	}

	public void setPlayTime(int playTime) {
		this.playTime = playTime;
	}
	
	
	
	
	}